Method and system for compact representation of routes

• US 6,763,301 B2
• Filed: 02/24/2003
• Issued: 07/13/2004
• Est. Priority Date: 08/25/2000
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq North America LLC (Nokia Corporation)
• Inventors: McDonough, William
• Primary Examiner(s): LOUIS JACQUES, JACQUES H
• Application Number:
  US10/373,295
• Publication Number:
  US 20030130789A1
• Time in Patent Office: 505 Days
• Field of Search: 340/995.1, 340/995.14, 340/995.18, 382/276, 382/173, 382/232, 382/305, 701/208, 701/209, 701/211, 701/212, 701/25, 342/357.13, 707/1, 707/100, 707/101, 707/102, 707/104.1, 707/103.R
• US Class Current: 701/208
• 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 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 indicate road segments that meet at the intersection; and

data that indicate nominal paths through the intersection, wherein said data

that represent nominal paths associate each entrance road segment into the

intersection with one, and only one, exit road segment.

2. The invention of claim 1 further comprising:

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

3. The invention of claim 1 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.

4. The invention of claim 1 wherein the data that indicate road segments that meet at the intersection indicate, for each road segment into the intersection, each road segment from which the intersection can be exited.

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

data representations of intersections of roads located in the region;

successor data that indicate, for each entrance road segment along which a represented intersection can be entered, each successor road segment from which the intersection can be exited; and

in addition to said successor data,

nominal path data that indicate, for each entrance road segment, one, and only one, of the successor road segments associated with the entrance road segment.

6. The invention of claim 5 wherein the successor data indicate which successor road segments associated with an entrance road segment can be entered legally.

7. The invention of claim 5 wherein the successor road segments associated with an entrance road segment indicate all road segments that connect to the entrance road segment including any road segment that can be entered legally from the entrance road segment and any road segment that connects to, but cannot legally be entered from, the entrance road segment.

8. The invention of claim 5 further comprising:

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

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