Generation of Intersection Information by a Mapping Service

• US 20150149080A1
• Filed: 02/02/2015
• Published: 05/28/2015
• Est. Priority Date: 06/05/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: McCarthy, Paul S.
• Granted Patent: US 9,880,019 B2
• Time in Patent Office: Days
• US Class Current: 701/430
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/28 with correlation of data from several navigational instruments
• CPC Class Codes: G01C 21/3635 Guidance using 3D or perspective road maps
• CPC Class Codes: G01C 21/3638 including 3D objects and buildings three dimensional [3D] modelling, e.g. data description of 3D objects G06T17/00; geographic models G06T17/05
• CPC Class Codes: G06F 16/2291 User-Defined Types; Storage management thereof
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 19/20 Editing of 3D images, e.g. changing shapes or colours, aligning objects or positioning parts
• CPC Class Codes: G06T 2219/2016 Rotation, translation, scaling
• CPC Class Codes: G06T 2219/2024 Style variation
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

Some embodiments provide a method for generating intersection data for paths in a map region. The method receives a set of junctions at which paths intersect in the map region. For a particular junction of at least two paths, the method automatically determines whether any of the other junctions in the map region satisfy criteria to be part of a single intersection with the particular junction. When at least one of the other junctions satisfies the criteria, the method automatically combines the other junctions that satisfy the criteria with the particular junction into a single intersection for use in performing mapping operations.

Claims

1-7. -7. (canceled)

8. A method for generating and storing intersection data for a map region, the method comprising:

identifying an intersection within the map region as a location in the map region at which at least two road segments intersect;

for each particular road segment that either (i) exits the intersection or (ii) enters the intersection and is separate from all of the road segments that exit the intersection, calculating an angle associated with the road segment; and

storing the calculated angles associated with the road segments in order to define the intersection.

9. The method of claim 8, wherein the calculated angles are based on angular distance from North.

10. The method of claim 8, wherein the road segments are defined as a series of vertices at locations.

11. The method of claim 10, wherein calculating the angle for a particular road segment comprises calculating the angle of a straight line from a vertex of the path segment at the intersection to a vertex of the path segment a particular distance away from the intersection.

12. The method of claim 8, wherein the stored angular intersection data is for use in generating navigation data for routes requested by users.

13. A machine readable medium storing a program which when executed by at least one processing unit generates navigation data for a route, the program comprising sets of instructions for:

receiving a route from a first location to a second location, the route comprising a series of intersections;

for each intersection along the route, retrieving data that comprises a set of angles, each angle defining a possible exit path for the intersection; and

for each retrieved set of angles, rotating the angles such that a particular path on which the route enters the intersection is at a specific angle.

14. The machine readable medium of claim 13, wherein the program further comprises a set of instructions for designating one of the angles as an exit path for the route.

15. The machine readable medium of claim 13, wherein the received route is generated in response to a user request.

16. The machine readable medium of claim 15, wherein the intersection data with rotated angles is transmitted to the user along with the route in order to provide turn-by-turn navigation information.

17. The machine readable medium of claim 13, wherein the intersections for which data is retrieved comprise only intersections at which the route requires a maneuver other than continuing straight through the intersection.

18. The machine readable medium of claim 13, wherein the intersections for which data is retrieved comprise all junctures including those through which the route continues straight.

19-22. -22. (canceled)

23. A method for generating navigation data for a route, the method comprising:

receiving a route from a first location to a second location, the route comprising a series of intersections;

for each intersection along the route, retrieving data that comprises a set of angles, each angle defining a possible exit path for the intersection; and

for each retrieved set of angles, rotating the angles such that a particular path on which the route enters the intersection is at a specific angle.

24. The method of claim 23 further comprising designating one of the angles as an exit path for the route.

25. The method of claim 23, wherein the received route is generated in response to a user request.

26. The method of claim 25, wherein the intersection data with rotated angles is transmitted to the user along with the route in order to provide turn-by-turn navigation information.

27. The method of claim 26, wherein the intersection data further comprises a designation of an exit path for each intersection.

28. The method of claim 23, wherein the intersections for which data is retrieved comprise only intersections at which the route requires a maneuver other than continuing straight through the intersection.

29. The method of claim 23, wherein the intersections for which data is retrieved comprise all junctions including those through which the route continues straight.

30. The method of claim 23, wherein the angles in the retrieved data are calculated based on angular distance from North.