System and method for calculating a navigation route based on adjacent cartographic map databases

• US 6,574,553 B1
• Filed: 10/11/2001
• Issued: 06/03/2003
• Est. Priority Date: 12/11/2001
• Status: Expired due to Term

• Current Assignee: Garmin Limited
• Original Assignee: Garmin Limited
• Inventors: Childs, Michael, Beesley, Darin J.
• Primary Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US10/015,148
• Time in Patent Office: 600 Days
• Field of Search: 701/200, 701/201, 701/208, 701/209, 701/212, 701/210, 701/23, 340/988, 340/990, 340/995
• US Class Current: 701/209
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

A method and apparatus are provided for calculating potential paths through a roadway network defined at least partially by separate, but adjacent data maps. First and second data maps are provided that are indicative of roadway networks for different geographic regions bounded by region edges, at least one of which is common to both geographic regions. The data maps are adjacent, and one data map contains the first location while the other data map contains a roadway segment over which the potential paths may travel. Potential paths are planned from the first location through the first data map. When a current potential path intersects an edge of the first data map, the intersection is identified by coordinate data. A transition point is located in an adjacent data map based on the location where the current potential path intersects the edge of the first data map. The calculation method and apparatus continue from the transition point through the second data map toward the second location.

Claims

1. A method for calculating a route between first and second locations, comprising:

providing first and second data maps of different first and second geographic regions, respectively, having region edges;

planning potential paths from a first location through said first geographic region toward a second location outside of said first geographic region based on said first data map;

determining when at least one of said potential paths intersects a region edge of said first geographic region;

identifying a transition point in said second data map for said at least one of said potential paths based on a location at which said at least one of said potential paths intersects said region edge of said first data map; and

planning potential paths from said transition point through said second geographic region toward said second location based on said second data map.

2. The method of claim 1, wherein said first and second data maps constitute first and second map databases including data indicative of a roadway network in said first and second geographic regions, respectively.

3. The method of claim 1, wherein said first and second data maps constitute first and second map databases including data indicative of nodes at which roads in a roadway network intersect said region edges of respective first and second geographic regions.

4. The method of claim 1, further comprising locating node coordinates of said location at which said at least one of said potential paths intersects an edge of said first data map, said identifying step identifying said transition point based on said node coordinates.

5. The method of claim 1, further comprising comparing data indicative of node coordinates at which roads intersect region edges of said first and second geographic regions to identify said transition point.

6. The method of claim 1, further comprising searching an edge table associated with said second data map for node coordinates matching said location at which said at least one of said potential paths intersects said region edge of said first geographic region.

7. The method of claim 1, further comprising:

locating data maps corresponding to geographic regions that are adjacent to said first geographic region; and

selecting one of said data maps as said second data map.

8. The method of claim 1, further comprising organizing multiple data maps into a bounded box layout identifying adjacent data maps, said first and second data maps being adjacent one another.

9. The method of claim 1, further comprising performing a node expansion during said second planning step by identifying nodes in said second data map linked to said transition point to continue planning said potential paths through said second data map.

10. A map database recorded on a computer readable medium, comprising:

nodal records stored in a linked structure, said nodal records containing data indicative of nodes in a roadway network, for a geographic region within defined boundaries and data indicative of roads intersecting and joining said nodes; and

edge markers stored in said linked structure, said edge markers containing data indicative of points at which said roads intersect said boundaries of said geographic region defined by said nodal records, said edge markers being configured to be matched between adjacent map databases.

11. The map database of claim 10, further comprising an edge table containing longitude and latitude coordinates at which said roads intersect said boundaries.

12. The map database of claim 10, further comprising an edge table containing data identifying each road intersecting said boundaries.

13. The map database of claim 10, further comprising edge/route coordinates, at which roads intersect said boundary, stored in a searchable format.

14. The map database of claim 10, further comprising edge/route coordinates at which roads intersect said boundary, said edge/route coordinates for one of said boundaries matching edge/route coordinates stored in a map database for an adjacent boundary from an adjoining geographic region.

15. The map database of claim 10, wherein said nodal records further comprise node data organized by nodes, identifying adjacent nodes, a distance to said adjacent nodes and speed data for roads connecting said nodes.

16. A portable electronic device, comprising:

memory storing data maps of roadway networks for geographic regions surrounded by edges;

a processor calculating potential paths through a first data map, said processor automatically shifting calculation of a current potential path to a second data map when said current potential path intersects an edge of said first data map; and

an output unit presenting a route through said first and second data maps to a user based on said potential paths.

17. The portable electronic device of claim 16, further comprising a display presenting maps to the user of said route.

18. The portable electronic device of claim 16, wherein said processor identifies a transition point to said second data map based on a location at which said current potential path intersects said edge of said first data map.

19. The portable electronic device of claim 16, wherein said memory stores data indicative of roads in the roadway networks and data indicative of nodes at which said roads intersect said edges of said geographic regions.

20. The portable electronic device of claim 16, wherein said processor locates node coordinates of a location at which said current potential path intersects said edge of said first data map, said processor utilizes said node coordinates to identify a transition point to said second data map.

21. The portable electronic device of claim 16, wherein said processor compares data indicative of node coordinates at which roads intersect edges of said first and second data maps.

22. The portable electronic device of claim 16, wherein said processor searches an edge table associated with said second data map for node coordinates matching said location at which said current potential path intersects said edge of said first data map.

23. The portable electronic device of claim 16, wherein said processor organizes multiple data maps into a bounded box layout identifying adjacent data maps, said first and second data maps being adjacent one another.

24. The portable electronic device of claim 16, wherein said processor performs a node expansion during said second planning step by identifying nodes in said second data map that are linked to said transition point to continue planning said potential paths through said second data map.

25. The portable electronic device of claim 16, wherein said processor identifies an edge node in said first data map at which said current potential path intersects said edge of said first data map, said processor analyzing adjacent nodes in said second data map to shift calculation of said current potential path to said second data map, said adjacent nodes constituting nodes in said second data map directly connected by roads to said edge node in said first data map.

26. A navigation system for calculating a route between first and second locations, comprising:

an input unit configured to accept from a user first and second locations;

memory storing at least first and second map databases containing data indicative of first and second geographic regions, said first geographic region differing from, and being positioned adjacent to, said second geographic region; and

a route planner calculating potential paths from said first location through said first geographic region based on said first map database, when a current potential path intersects an edge of said first geographic region, said route planner accessing said second map database to continue calculating said current potential path toward said second location through said second geographic region based on said second map database.

27. The navigation system of claim 26, wherein said first and second geographic regions partially overlap one another, said memory storing edge tables containing coordinates identifying nodes along edges of said first geographic region that overlap said second geographic region.