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

• US 6,708,112 B1
• Filed: 04/25/2003
• Issued: 03/16/2004
• 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/423,748
• Time in Patent Office: 326 Days
• Field of Search: 701/200, 701/201, 701/208, 701/209, 701/210, 701/212, 701/23, 340/988, 340/990, 340/995.1
• 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 firs 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 at least partially different first and second geographic regions, respectively;

planning a first partial route partially extending between a first location in said first geographic region and a second location in said second geographic region based on first data map; and

planning a second partial route partially extending between said second location in said second geographic region and said first location in said first geographic region based on said second data map.

2. The method of claim 1, further comprising combining said first and second partial routes to form a complete route between said first and second locations.

3. The method of claim 1, further comprising identifying a transition point between said first and second data maps.

4. The method of claim 1, further comprising determining an intersection of at least one of said first and second partial routes with an edge of at least one of said first and second data maps.

5. The method of claim 1, wherein said first and second data maps represent subsets of a common cartographic data block.

6. The method of claim 1, wherein at least one of said first and second partial routes cross a region edge of at least one of said first and second data maps.

7. The method of claim 1, wherein at least one of said planning steps includes analyzing multiple potential paths through a corresponding one of said first and second data maps.

8. The method of claim 1, wherein said planning steps for said first and second partial routes perform a bidirectional search.

9. The method of claim 1, further comprising transmitting from a mobile unit, an instruction notifying a remote server to perform at least a portion of said planning steps, and receiving, at said mobile unit, a route between said first and second locations.

10. A portable electronic device, comprising:

an input unit for receiving first and second locations in first and second data maps of roadway networks representing at least partially different first and second geographic regions, respectively;

a processor for at least partially planning a first partial route, based on said first data map, said first partial route having an end at said first location in said first geographic region, said processor at least partially planning a second partial route, based on said second data map, said second partial route having an end at said second location in said second geographic region; and

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

11. The portable device of claim 10, wherein said processor combines said first and second partial routes to form a complete route between said first and second locations.

12. The portable device of claim 10, wherein said processor identifies a transition point between said first and second data maps.

13. The portable device of claim 10, wherein said processor determines an intersection of at least one of said first and second partial routes with an edge of at least one of said first and second data maps.

14. The portable device of claim 10, wherein said input unit includes memory that simultaneously stores said first and second data maps.

15. The portable device of claim 10, wherein said input unit includes a receiver that receives said first and second data maps from a remote server.

16. The portable device of claim 10, wherein at least one of said first and second partial routes cross a region edge of at least one of said first and second data maps.

17. The portable device of claim 10, wherein said input unit includes memory in said portable device that simultaneously stores both of said first and second data maps.

18. The portable device of claim 10, wherein said processor performs a bidirectional search for said first and second partial routes simultaneously from both of said first and second locations.

19. The portable device of claim 10, further comprising a transmitter instructing a remote server to perform at least a portion of said planning functions, said input unit including a receiver receiving from said remote server a route between said first and second locations.

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

an input for receiving first and second locations in first and second data maps of roadway networks representing at least partially different first and second geographic regions, respectively;

a route planner for at least partially planning a first partial route, based on said first data map, said first partial route having an end at said first location in said first geographic region, said route planner at least partially planning a second partial route, based on said second data map, said second partial route having an end at said second location in said second geographic region; and

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

21. The system of claim 20, wherein said route planner identifies a transition point between said first and second data maps.

22. The system of claim 20, wherein said route planner determines an intersection of at least one of said first and second partial routes with an edge of at least one of said first and second data maps.

23. The system of claim 20, wherein said input includes memory that stores simultaneously said first and second data maps.

24. The system of claim 20, wherein said route planner performs a bidirectional search for said first and second partial routes simultaneously from both of said first and second locations.