System and method for calculating a navigation route based on non-contiguous cartographic map databases

• US 6,574,554 B1
• Filed: 12/11/2001
• Issued: 06/03/2003
• Est. Priority Date: 12/11/2001
• Status: Active Grant

• Current Assignee: Garmin Limited
• Original Assignee: Garmin Limited
• Inventors: Childs, Michael, Beesley, Darin J.
• Primary Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US10/015,153
• Time in Patent Office: 539 Days
• Field of Search: 701/200, 701/201, 701/208, 701/209, 701/210, 701/212, 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/34 Route searching; Route guidance
• 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 between source and destination locations. First and second map databases are provided that are indicative of roadway networks for geographic regions bounded by region edges and containing source and destination locations. The first and second map databases, are non-adjacent, non-contiguous such that the region edges of the first map database are separate and distinct from region edges of the second map database. Potential paths are calculated through the roadway network of the first map database up to a node or segment at which each potential path intersects a region edge of the first map database, thereby defining a node/edge coordinate. A transition location is obtained in the second map database that geographically corresponds to the node/edge coordinate at which a given potential path intersected the region edge of the first map database. The calculation continues from the transition location through the roadway network of the second map database. The method and apparatus may include organizing the map databases into a map hierarchy to define tiers for the map databases. The calculation process searches potential paths utilizing the tier-one map databases until each potential path intersects a map edge of the tier-one map, databases. Thereafter, the search through potential paths continues automatically based on the lower tier map databases.

Claims

1. A method for calculating potential paths through nodes in a roadway network between source and destination locations, comprising:

providing a first map database indicative of a roadway network for a first geographic region bounded by first region edges and containing one of a source location and a destination location;

providing a second map database indicative of a roadway network for a second geographic region bounded by second region edges, second geographic region at least partially overlapping said second geographic region said first region edges being separate and distinct from said second region edges;

first calculating potential paths though the roadway network of said first map database until a current potential path intersects one of said first region edges of said first map database at a node/edge coordinate;

obtaining a transition location in said second map database geographically corresponding to said node/edge coordinate at which said current potential path intersects said first region edge of said first map database; and

second calculating a second potential path from said transition location through the roadway network of said second map database.

2. The method of claim 1, further comprising:

organizing at least said first and second map databases in first and second map tiers based on a data supplier of said first and second map databases; and

performing said first calculating step based on map databases in said first map tier before performing said obtaining and second calculating steps with respect to said second map database in said second map tier.

3. The method of claim 1, further comprising:

organizing multiple map databases into first and second map tiers based on an amount of detailed feature information held in said first and second map databases concerning corresponding first and second geographic regions, said first and second map databases being organized into said first and second map tiers, respectively; and

performing said first calculating step based on said map databases in said first map tier that are adjacent to said first map database before performing said obtaining and second calculating steps with respect to said map databases in said second map tier.

4. The method of claim 1, further comprising;

organizing multiple map databases in first and second map tiers;

when said first potential path reaches said region edge of said first map database, determining whether said first map tier includes another map database indicative of a roadway network for a geographic region adjacent to said first map database; and

performing said obtaining step only after said first calculating step accesses all adjacent map databases in said first map tier.

5. The method of claim 1, wherein said obtaining step searches said second map database for transition locations within a bounded box surrounding said node/edge coordinate.

6. The method of claim 1, wherein said providing steps include providing said first map database with data indicative of a low-level detailed map of the geographic region surrounding said source location, providing said second map database with data indicative of a high-level base map of the geographic region encompassing both of said source and destination locations, and providing a third map database with data indicative of a low-level detailed map of the geographic region surrounding said destination location, said first and third map databases being non-overlapping and non-contiguous.

7. The method of claim 1, wherein said first map database includes data indicative of a detailed map of the roadway network for a first metropolitan area and said second map database includes data indicative of a base map of the roadway network for a large geographic region at least partially encompassing the first metropolitan area.

8. The method of claim 1, wherein said first map database includes data indicative of a detailed map of the roadway network for a small geographic region and said second map database includes data indicative of a base map of the roadway network for a large geographic region at least partially encompassing the small geographic region.

9. The method of claim 1, further comprising organizing the first and second map databases in a tiered map hierarchy with the first and second map databases being assigned to different tiers.

10. A method for calculating a potential path from a first point toward a second point, comprising:

providing a plurality of map databases indicative of an equal plurality of roadway networks for geographic regions, each map database being surrounded by map edges;

organizing said plurality of map databases into a map hierarchy by assigning at least one map database to a first level of said map hierarchy to define at least one tier-one map database and by assigning at least one map database to a second level of said map hierarchy to define at least one tier-two map database;

utilizing said tier-one map databases to plan potential paths from a first point toward a second point until at least one of said potential paths intersects a map edge of said tier-one map databases; and

when said at least one of said potential paths intersects said map edge of said tier-one map databases, automatically continuing planning said at least one of said potential paths based on said tier-two map databases.

11. The method of claim 10, wherein said map databases include first and second tier-one map databases including data indicative of geographic regions surrounding said first and second points, respectively, said first and second tier-one map databases corresponding to non-overlapping geographic regions.

12. The method of claim 10, wherein said map databases include a tier-one map database including data indicative of a geographic region containing said first point and excluding said second point, said map databases including a tier-two map database including data indicative of a geographic region containing said first and second points.

13. The method of claim 10, wherein said map databases include first and second tier-one map databases including data indicative of a geographic region containing said first and second points, respectively, and a tier-two map database including data indicative of a geographic region partially overlapping said geographic regions identified by data in said first and second map databases, said geographic region identified by data in said tier-two map database excluding said first and second points.

14. The method of claim 10, wherein said map databases include first and second tier-one map databases including data indicative of a geographic region containing detailed maps of areas surrounding said first and second points, respectively, and a tier-two map database including data indicative of a geographic region containing a base map overlapping both of said detailed maps, said base map including said first and second points.

15. The method of claim 10, further comprising:

searching said tier-two map databases for a node in a respective roadway network corresponding to a node at which said at least one of said potential paths intersects said map edge in said tier-one map databases.

16. The method of claim 10, further comprising:

when said at least one of said potential paths intersects said map edge of a first tier-one map database, determining whether any other tier-one map databases exist that have map edges that join said map edge of said first tier-one map database intersected by said at least one of said potential paths.

17. The method of claim 10, further comprising:

determining a translation node in said tier-two map databases based on a location at which said at least one of said potential paths intersects said map edge of said tier-one map databases, said translation node representing a starting point within said tier-two map databases from which said planning step continues.

18. The method of claim 10, further comprising:

identifying, in said tier-one map databases, a tier-one coordinate indicative of a point at which said at least one of said potential paths intersects said map edge; and

searching a geographic region for at least one of said tier-two map databases for a tier-two coordinate corresponding to said tier-one coordinate.

19. The method of claim 10, further comprising:

identifying, in said tier-two map databases, a road having a generally common direction of travel as said at least one of said potential paths at a point of intersection of said at least one of said potential paths with said map edge of said tier-one map database.

20. A navigation system, comprising:

memory storing map databases indicative of roadway networks in respective geographic regions surrounded by region edges, said map databases including first and second map databases, said geographic regions containing first and second navigation points, said first and second map databases corresponding to geographic regions having separate and distinct non-adjacent region edges;

a planner calculating paths between said first and second navigation points based on roadway network information in both of said first and second map databases, said planner switching from calculations based on said first map database to calculations based on said second map database once said planner calculates at least one path through said first map database to a node at which at least one said path intersects a region edge of said first map database; and

a display displaying a final route based on said at least one path calculated by said planner.

21. The navigation system of claim 21, wherein said first map database represents a detailed map of a roadway network surrounding said first navigation point and wherein said second map database represents a base map of a roadway network surrounding both of said first and second navigation points.

22. The navigation system of claim 21, wherein said first map database represents a detailed map of a roadway network surrounding said first navigation point and wherein said second map database represents a base map of a roadway network surrounding said second navigation point and excluding said first navigation point, said base map partially overlapping said detailed map.

23. The navigation system of claim 21, wherein said first and second map databases do not overlap, said memory storing a third map database indicative of a geographic region at least partially overlapping said first and second map databases, said planner jumping directly from said first map database to said third map database and then directly to said second map database.

24. The navigation system of claim 21, wherein said first and second map databases do not overlap, said memory storing a third map database indicative of a geographic region at least partially overlapping said first and second map databases, said planner jumping from said first and second map databases in parallel to said third map database.

25. The navigation system of claim 21, further comprising an organization module that organizes said map databases into a mapping hierarchy by assigning at least said first map database to a first level of said mapping hierarchy to define tier-one map databases and by assigning at least said second map database to a second level of said mapping hierarchy to define tier-two map databases.

26. The navigation system of claim 21, wherein said memory includes a third map database containing said second navigation point, said first and third map databases corresponding to non-overlapping non-adjacent geographic regions, said planner simultaneously calculating paths from said first and second navigation points beginning in said first and third map databases, said planner jumping from said first and third map databases to said second map database when said paths intersect said boundary edges of said first and third map databases.

27. The navigation system of claim 21, wherein said planner calculates a path/edge coordinate at which said at least one path intersects said boundary edge of said first map database, said planner calculated a transition location in said second map database that corresponds to said path/edge coordinate.

28. A navigation device, comprising:

memory storing map databases indicative of roadway networks in respective geographic regions surrounded by region edges, said map databases including first and second map databases, said geographic regions containing first and second navigation points, said first and second map databases corresponding to geographic regions having separate and distinct non-adjacent region edges;

a processor calculating paths between said first and second navigation points based on roadway network information in both of said first and second map databases, said processor moving from operation based on said first map database to operation based on said second map database once said processor calculates at least one path through said first map database to a node at which said at least one path intersects a region edge of said first map database; and

a display displaying a route based on said at least one path calculated by said processor.