Method and system for compact representation of routes

• US 6,526,348 B1
• Filed: 08/25/2000
• Issued: 02/25/2003
• Est. Priority Date: 08/25/2000
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: McDonough, William
• Primary Examiner(s): LOUIS JACQUES, JACQUES H
• Application Number:
  US09/649,715
• Time in Patent Office: 914 Days
• Field of Search: 701/207, 701/208, 701/209, 701/210, 701/211, 340/988, 340/990, 340/995, 342/357.13
• US Class Current: 701/209
• CPC Class Codes: G01C 21/34 Route searching; Route guidance

Abstract

A method for representing a route along a road network in a geographic region is disclosed. A database includes data representations of intersections of roads in the geographic region. Associated with the data representation for each intersection of roads are data indicating one or more nominal paths through the intersection. The nominal paths through an intersection identify, for each road segment by which the represented intersection can be entered, one and only one road segment from which the represented intersection is exited. The route is represented by indicating each intersection at which the route deviates from the nominal path into the intersection.

Claims

1. A method of representing a route comprising:

using a database that defines nominal paths through intersections located in a geographic region, wherein a nominal path defines, for each road segment by which an intersection can be entered, one and only one road segment from which the intersection is exited; and

representing the route in the geographic region by identifying each intersection at which the route deviates from a nominal path through said intersection.

2. The method of claim 1 wherein said step of representing also comprises:

identifying a location associated with an end of the route.

3. The method of claim 1 wherein said step of representing also comprises:

identifying a location associated with a beginning of the route.

4. The method of claim 1 wherein said step of representing also comprises:

identifying a new exit at each intersection at which the route deviates from a nominal path through said intersection.

5. A database that represents geographic features located in a region, the database comprising:

data representations of intersections of roads located in the region; and

for each data representation of an intersection, data that represent nominal paths through the intersection, wherein a nominal path defines, for each road segment by which an intersection can be entered, one and only one road segment from which the intersection is exited.

6. The invention of claim 5 further comprising:

for each data representation of an intersection, data that indicate the geographic coordinates of the intersection.

7. The invention of claim 5 wherein the exit road segment associated with an entrance road segment is that road segment onto which a motorist is most likely to travel from the entrance road segment.

8. A method of operation for a navigation system comprising:

calculating a route to a destination;

representing the route by identifying each intersection along the route at which the route deviates from a nominal path through the intersection, wherein nominal paths though intersections are defined in a geographic database, and wherein a nominal path defines, for each road segment by which an intersection can be entered, one and only one road segment from which the intersection is exited; and

providing a representation of the route formed by the representing step to an application that uses the representation to provide a navigation-related function.

9. The method of claim 8 wherein the navigation-related function is guidance for following the route.

10. The method of claim 8 wherein the navigation-related function is a map display with the route highlighted thereon.

11. The method of claim 8 wherein the navigation system maintains only a portion of the representation of the route in memory while using the representation to provide the navigation-related function.

12. The method of claim 8 further comprising:

sending the representation from a server to a vehicle.

13. The method of claim 8 wherein said steps of calculating and providing are performed in a vehicle.

14. The method of claim 8 wherein said step of representing further comprises:

identifying an exit path at each intersection at which the route deviates from a nominal path through said intersection.

15. A navigation system comprising:

a first navigation application that forms a representation of a route by identifying each location at which the route deviates from nominal paths defined through intersections of roads located in a geographic region, wherein a nominal path defines, for each road segment by which an intersection can be entered, one and only one road segment from which the intersection is exited; and

a second navigation application that uses the representation of the route formed by the first navigation application to provide a navigation-related function to a user of the navigation system.

16. The invention of claim 15 wherein the first navigation application calculates the route to a destination.

17. The invention of claim 15 wherein the navigation-related function comprises route guidance.

18. The invention of claim 15 wherein the navigation-related function comprises map display.

19. The invention of claim 15 wherein the navigation-related function is a map display with the route highlighted thereon.

20. The invention of claim 15 wherein said first navigation application and said second navigation application are both located in a vehicle.

21. The invention of claim 15 wherein said first navigation application is located on a remotely located server and said second navigation application is located in a vehicle.

22. The invention of claim 15 further comprising a wireless communications system by which said representation of the route is transmitted from said first navigation application to said second navigation application.

23. The invention of claim 15 wherein the first navigation application also identifies a new path at each an intersection at which the route deviates from the nominal path therethrough.

24. A method of forming a geographic database comprising:

storing data representations of intersections of roads located in a geographic region; and

for each data representation of an intersection, associating therewith data that indicate nominal paths through the intersection, wherein a nominal path defines, for each road segment by which an intersection can be entered, one and only one road segment from which the intersection is exited.

25. The method of claim 24 wherein the road segment from which the intersection can be exited on a nominal path is that road segment onto which a motorist is most likely to travel from the associated road segment via which the intersection can be entered.

26. The method of claim 24 further comprising:

for each data representation of an intersection, associating therewith data that indicates the geographic coordinates of the intersection.