Method for displaying a position on a map

• US 9,322,666 B2
• Filed: 07/14/2015
• Issued: 04/26/2016
• Est. Priority Date: 06/30/2014
• Status: Active Grant

• Current Assignee: Direct Cursus Technology LLC
• Original Assignee: Yandex Europe AG (Yandex N.V.)
• Inventors: Korzunov, Anton Vasilyevich
• Primary Examiner(s): ARTHUR JEANGLAUD, GERTRUDE
• Application Number:
  US14/798,819
• Publication Number:
  US 20150377627A1
• Time in Patent Office: 287 Days
• Field of Search: 701/431, 701/435, 701/461, 340/988, 340/990, 340/995.14, 707/999.102
• US Class Current: 1/1
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/367 Details, e.g. road map scale, orientation, zooming, illumination, level of detail, scrolling of road map or positioning of current position marker
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps

Abstract

There is disclosed a method executable by an electronic device for displaying a position on a map. The method comprises appreciating coordinates of position; appreciating coordinates of a map object having a curve near position; identifying a point of curve nearest to position comprising identifying a first segment of curve bounded by a first region and a second segment of curve bounded by a second region, determining that a distance from position to a point of first segment is not greater than a distance from position to a known nearest point of second region, and calculating a shortest distance from position to first segment as a shortest distance from position to either of first segment and second segment without calculating a distance from position to at least one point of second segment other than known nearest point of second region; and causing displaying, on map, of an indication of point of curve nearest to position.

Claims

1. A computer-implemented method for displaying a position on a map, the method executable by an electronic device causing displaying of the map, the method comprising:

appreciating coordinates of the position;

appreciating coordinates of an object having a curve near the position;

identifying a point of the curve nearest to the position, said identifying comprising

identifying a first segment of the curve bounded by a first region and a second segment of the curve bounded by a second region;

wherein

identifying the first segment of the curve bounded by the first region and the second segment of the curve bounded by the second region comprises dividing a monotonic segment of the curve into segments including the first segment and the second segment; and

wherein

dividing the monotonic segment of the curve into segments including the first segment and the second segment comprises dividing the monotonic segment of the curve into segments including the first segment and the second segment such that the second segment monotonically progresses away from the position from a known nearest point of the second region

determining that a distance from the position to a point of the first segment is not greater than a distance from the position to a known nearest point of the second region; and

calculating a shortest distance from the position to the first segment as a shortest distance from the position to either of the first segment and the second segment without calculating a distance from the position to at least one point of the second segment other than the known nearest point of the second region; and

causing displaying, on the map, of an indication of the point of the curve nearest to the position.

2. The method of claim 1, wherein:

dividing the monotonic segment of the curve into segments including the first segment and the second segment comprises dividing the monotonic segment of the curve into segments including the first segment, the second segment, and a third segment bounded by a third region, such that the third segment monotonically progresses away from the position from a known nearest point of the third region; and

identifying the point of the curve nearest to the position further comprises calculating a distance from the position to the known nearest point of the third region as a shortest distance from the position to the third segment without calculating a distance from the position to at least one point of the third segment other than the known nearest point of the third region.

3. The method of claim 1, wherein determining that the distance from the position to the point of the first segment is not greater than the distance from the position to the known nearest point of the second region comprises determining that a distance from the position to a known farthest point of the first region is not greater than the second distance.

4. The method of claim 3, wherein the map is three-dimensional, the first region is a rectangular cuboid, and the known farthest point of the first region is a farthest corner of the first region.

5. The method of claim 3, wherein the map is two-dimensional, the first region is a rectangle, and the known farthest point of the first region is a farthest corner of the first region.

6. The method of claim 1, wherein the map is three-dimensional, the second region is a rectangular cuboid, and the known nearest point of the second region is a nearest corner of the second region.

7. A computer-implemented method for displaying a position on a map, the method executable by an electronic device causing displaying of the map, the method comprising:

appreciating coordinates of the position;

appreciating coordinates of an object having a curve near the position;

identifying a point of the curve nearest to the position, said identifying comprising

identifying a monotonic segment of the curve bounded by a region having a known nearest point to the position;

determining that the monotonic segment monotonically progresses away from the position from the known nearest point;

calculating a distance from the position to the known nearest point of the region as a shortest distance from the position to the monotonic segment without calculating a distance from the position to at least one point of the monotonic segment other than the known nearest point of the region; and

causing displaying, on the map, of an indication of the point of the curve nearest to the position.

8. The method of claim 7, wherein the map is three-dimensional, the region is a rectangular cuboid, and the known nearest point of the region is a nearest corner of the region.

9. The method of claim 7, wherein the map is two-dimensional, the region is a rectangle, and the known nearest point of the region is a nearest corner of the region.

10. The method of claim 7, wherein calculating a distance from the position to the known nearest point of the region as a shortest distance from the position to the monotonic segment without calculating a distance from the position to at least one point of the monotonic segment other than the known nearest point of the region is calculating a distance from the position to the known nearest point of the region as a shortest distance from the position to the monotonic segment without calculating a distance from the position to any point of the monotonic segment other than the known nearest point of the region.

11. A non-transitory computer-readable medium storing program instructions for displaying a position on a map, the program instructions being executable by a processor of an electronic device to effect:

appreciating of coordinates of the position;

appreciating of coordinates of an object having a curve near the position;

identifying of a point of the curve nearest to the position, said identifying comprising

identifying of a first segment of the curve bounded by a first region and a second segment of the curve bounded by a second region;

wherein

identifying of the first segment of the curve bounded by the first region and the second segment of the curve bounded by the second region comprises dividing of a monotonic segment of the curve into segments including the first segment and the second segment;

wherein

dividing of the monotonic segment of the curve into segments including the first segment and the second segment comprises dividing of the monotonic segment of the curve into segments including the first segment and the second segment such that the second segment monotonically progresses away from the position from a known nearest point of the second region;

determining that a distance from the position to a point of the first segment is not greater than a distance from the position to a known nearest point of the second region;

calculating of a shortest distance from the position to the first segment as a shortest distance from the position to either of the first segment and the second segment without calculating a distance from the position to at least one point of the second segment other than the known nearest point of the second region; and

causing displaying, on the map, of an indication of the point of the curve nearest to the position.

12. The medium of claim 11, wherein:

dividing of the monotonic segment of the curve into segments including the first segment and the second segment comprises dividing of the monotonic segment of the curve into segments including the first segment, the second segment, and a third segment bounded by a third region, such that the third segment monotonically progresses away from the position from a known nearest point of the third region; and

identifying of the point of the curve nearest to the position further comprises calculating of a distance from the position to the known nearest point of the third region as a shortest distance from the position to the third segment without calculating a distance from the position to at least one point of the third segment other than the known nearest point of the third region.

13. The medium of claim 11, wherein determining that the distance from the position to the point of the first segment is not greater than the distance from the position to the known nearest point of the second region comprises determining that a distance from the position to a known farthest point of the first region is not greater than the second distance.

14. The medium of claim 13, wherein the map is three-dimensional, the first region is a rectangular cuboid, and the known farthest point of the first region is a farthest corner of the first region.

15. The medium of claim 13, wherein the map is two-dimensional, the first region is a rectangle, and the known farthest point of the first region is a farthest corner of the first region.

16. The medium of claim 11, wherein the map is three-dimensional, the second region is a rectangular cuboid, and the known nearest point of the second region is a nearest corner of the second region.

17. A non-transitory computer-readable medium storing program instructions for displaying a position on a map, the program instructions being executable by a processor of an electronic device to effect:

appreciating of coordinates of the position;

appreciating of coordinates of an object having a curve near the position;

identifying of a point of the curve nearest to the position, said identifying comprising

identifying of a monotonic segment of the curve bounded by a region having a known nearest point to the position;

determining that the monotonic segment monotonically progresses away from the position from the known nearest point;

calculating of a distance from the position to the known nearest point of the region as a shortest distance from the position to the monotonic segment without calculating a distance from the position to at least one point of the monotonic segment other than the known nearest point of the region; and

causing displaying, on the map, of an indication of the point of the curve nearest to the position.

18. The medium of claim 17, wherein the map is three-dimensional, the region is a rectangular cuboid, and the known nearest point of the region is a nearest corner of the region.

19. The medium of claim 17, wherein the map is two-dimensional, the region is a rectangle, and the known nearest point of the region is a nearest corner of the region.

20. The medium of claim 17, wherein calculating of a distance from the position to the known nearest point of the region as a shortest distance from the position to the monotonic segment without calculating a distance from the position to at least one point of the monotonic segment other than the known nearest point of the region is calculating of a distance from the position to the known nearest point of the region as a shortest distance from the position to the monotonic segment without calculating a distance from the position to any point of the monotonic segment other than the known nearest point of the region.