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

• US 20050102101A1
• Filed: 12/03/2004
• Published: 05/12/2005
• Est. Priority Date: 12/11/2001
• Status: Abandoned Application

• Current Assignee: Garmin Limited
• Original Assignee: Garmin Limited
• Inventors: Childs, Michael, Beesley, Darin J.
• Application Number:
  US11/003,313
• Publication Number:
  US 20050102101A1
• Time in Patent Office: Days
• 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 navigation system, comprising:

a portable navigation device for navigating between first and second navigation points, the device including a display for displaying a route between the first and second navigation points; and

a server for calculating the route, the server including—

a memory storing map databases indicative of roadway networks in respective geographic regions surrounded by region edges, the geographic regions containing the first and second navigation points, and

a planner calculating paths between the first and second navigation points based on roadway network information in the map databases.

2. The system as set forth in claim 1, wherein the map databases include first and second map databases.

3. The system as set forth in claim 2, wherein the first and second map databases correspond to geographic regions having separate and distinct non-adjacent region edges.

4. The system as set forth in claim 2, wherein the first and second navigation points are based on roadway network information in both of the first and second map databases.

5. The system as set forth in claim 2, wherein the planner switches from calculations based on the first map database to calculations based on the second map database once the planner calculates at least one path through the first map database to a node at which the path intersects a region edge of the first map database.

6. The system as set forth in claim 1, further including a network for providing communications between the device and the server.

7. The system as set forth in claim 6, wherein the network is the Internet.

8. The system as set forth in claim 6, wherein the network is a wireless communications network.

9. The system as set forth in claim 1, the device further including—

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites; and

a processor for calculating, by triangulation, a position of the device using the signals.

10. The system as set forth in claim 9, wherein the processor determines the first navigation point using the signals and a user provides the second navigation point using an input.

11. The system as set forth in claim 1, wherein the device transmits the first and second navigation points to the server over a communications link and the server transmits the route to the device over the link.

12. The system as set forth in claim 11, wherein the server also transmits a map displaying the route to the device over the link.

13. A navigation system, comprising:

a portable navigation device for navigating between first and second navigation points, the device including a display for displaying a route between the first and second navigation points; and

a server for calculating the route, the server including—

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

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

14. The system as set forth in claim 13, further including a network for providing communications between the device and the server.

15. The system as set forth in claim 14, wherein the network is the Internet.

16. The system as set forth in claim 14, wherein the network is a wireless communications network.

17. The system as set forth in claim 13, the device further including—

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites; and

a processor for calculating, by triangulation, a position of the device using the signals.

18. The system as set forth in claim 17, wherein the processor determines the first navigation point using the signals and a user provides the second navigation point using an input.

19. The system as set forth in claim 13, wherein the device transmits the first and second navigation points to the server over a wireless communications network and the server transmits the route to the device over the network.

20. The system as set forth in claim 19, wherein the server also transmits a map displaying the route to the device over the network.

21. A navigation system, comprising:

a portable navigation device for navigating between first and second navigation points, the device including—

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites,

a processor for calculating, by triangulation, the first navigation point using the signals,

an input for receiving indication of the second navigation point from a user, and

a display for displaying a route between the first and second navigation points; and

a server for receiving the first and second navigation points from the device over a wireless communications network, calculating the route between the first and second navigation points, and transmitting the route to the device over the network, the server including—

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

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

22. The system as set forth in claim 21, wherein the server also transmits a map displaying the route to the device over the network.

23. A navigation server for calculating a route between first and second navigation points and transmitting the route to a portable navigation device for navigating the route, the server comprising:

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

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

24. The server as set forth in claim 23, wherein the server transmits the route to the device over a wireless communications network.

25. The server as set forth in claim 23, wherein the server receives the first and second navigation points from the device over a wireless communications network.

26. The server as set forth in claim 23, wherein the device includes—

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites;

a processor for calculating, by triangulation, the first navigation point using the signals;

an input for receiving the second navigation point from a user; and

a display for displaying the route.

27. The server as set forth in claim 26, wherein the server also transmits to the device a map displaying the route.

28. A portable navigation device for navigating a route between first and second navigation points, the device comprising:

a global positioning system (GPS) receiver for receiving signals transmitted from a plurality of GPS satellites;

a processor for calculating, by triangulation, the first navigation point using the signals;

an input for receiving indication of the second navigation point from a user;

a display for displaying the route between the first and second navigation points; and

a transceiver for receiving the route from a server.

29. The device as set forth in claim 28, wherein the server receives the first and second navigation points from the device over a wireless communications network, calculates the route between the first and second navigation points, and transmits the route to the device over the network.

30. The device as set forth in claim 28, wherein the server includes—

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

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

31. The device as set forth in claim 28, wherein the server also transmits to the device a map displaying the route.