Method for streamlined representation of roads in a geographic database

• US 6,836,781 B2
• Filed: 09/16/2002
• Issued: 12/28/2004
• Est. Priority Date: 09/16/2002
• 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): Rones, Charles
• Assistant Examiner(s): Abel-Jalil, Neveen
• Application Number:
  US10/244,269
• Publication Number:
  US 20040054687A1
• Time in Patent Office: 834 Days
• Field of Search: 707/1-10, 707/100-104, 701/117-119, 701/200-202, 701/209, 701/212, 705/14
• US Class Current: 707/803
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G09B 29/10 Map spot or coordinate position indicators; Map reading aids optical projection apparatus per se G03B
• CPC Class Codes: Y10S 707/919 Geographic
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method of representing a road network in a geographic database that facilitates determining routes between locations along the road network. In the geographic database, the road network is represented using transition point pair data. Each transition point pair data record indicates an entry point, an arm (or road segment) leading away from the entry point, an exit point, routing attributes (such as a travel cost or time), and possibly other data. Except for certain exceptions, such as multi-segment restricted driving maneuvers, the entry point and the exit point of a transition point pair are adjacent decision point intersections. A decision point intersection is an intersection at which a driver is required to make a decision which one of two or more possible road segments to take leading away from the intersection. The transition point pair data are used when calculating a route between two locations.

Claims

1. A method of determining a route with a geographic database that represents a road network, wherein the method comprises:

using a subset of the geographic database that includes transition point pair data to determine a skeleton solution route between an origin and a destination;

wherein the transition point pair data include data entities, each of which indicate an entry point, a road segment leading away from the entry point, an exit point, and attributes that indicate a cost of travel between the entry point and the exit point;

and further wherein each entry point and exit point correspond are decision point intersections, wherein a decision point intersection is an intersection of at least three road segments at which a driver entering the intersection along one of said at least three road segments has a choice of legally exiting the intersection along at least two other of said at least three road segments; and

using another subset of the geographic database to determine each road segment that corresponds to the skeleton solution route.

2. The method of claim 1 wherein said other subset includes data that indicate nominal paths through intersections, wherein each nominal path indicates one default road segment along which an intersection can be exited for each road segment along which the intersection can be entered.

3. A method of representing a network of road segments located in a geographic region to facilitate calculation of routes along said road segments, wherein the method comprises:

forming and storing data representations of transition point pairs,

wherein each transition point pair includes an entry point and an exit point,

wherein the entry point corresponds to a decision point intersection,

wherein a decision point intersection is an intersection of at least three road segments wherein a vehicle entering the intersection on one of the road segments can legally exit the intersection on at least two other road segments, and

wherein the exit point corresponds to the first eligible decision point intersection along a path of one or more connected road segments in a single legal direction of travel from the entry point; and

continuing to form and store the data representations of transition point pairs until all the transition point pairs are represented that include entry points corresponding to intersections used as entry points for at least two transition point pairs.

4. The method of claim 3 further comprising:

forming data representations of transition point pairs to represent multi-segment restricted driving maneuvers, wherein each data representation of a transition point pair involving a restricted driving maneuver represents only the legal paths of travel across the multi-segment restricted driving maneuver.

5. The method of claim 3 further comprising:

storing said data representations of transition point pairs in a subset of a database used for determining routes between locations along said network of road segments.

6. The method of claim 3 further comprising:

storing data representations of end points of road segments.

7. The method of claim 3 further comprising:

storing said data representations of transition point pairs in a first subset of a database, wherein the first subset is used for determining routes between locations along said network of road segments; and

forming a second subset of the geographic database, wherein the second subset includes data that represent individual road segments, and wherein said second subset is used to determine which of said individual road segments correspond to transition point pairs.

8. The method of claim 3 further comprising:

forming and storing nominal path data in a database with said data representations of transition point pairs, wherein said nominal path data indicate nominal paths through intersections, wherein each nominal path indicates one default road segment along which an intersection can be exited for each road segment along which the intersection can be entered.

9. The method of claim 3 further comprising:

forming and storing nominal path data in a database with said data representations of transition point pairs, wherein said nominal path data indicate nominal paths through intersections, wherein each nominal path indicates one default road segment along which an intersection can be exited for each road segment along which the intersection can be entered; and

storing in the data representations of those transition point pairs that deviate from nominal paths through intersections located between entry points and exit points thereof, data indicating the nodes at which such deviations occur and which road segments to follow from such nodes.

10. The method of claim 3 wherein an eligible decision point intersection is a decision point intersection that is not part of a restricted driving maneuver, a start of a one-way condition in a direction opposite to the direction toward the exit point, a start of a timed one-way condition, or a start of a no-through-traffic condition.

11. The method of claim 3 further comprising:

storing the data representations of transition point pairs on a computer-readable storage medium.

12. A geographic database that represents a road network located in a geographic area, wherein the geographic database comprises:

data entities that represent transition point pairs,

wherein each of said data entities that represents a transition point pair comprises data that indicate an entry point, a road segment leading away from the entry point, an exit point, and a travel cost for traveling from the entry point to the exit point along the road segment leading away from the entry point,

wherein each entry point and exit point are decision point intersections,

wherein a decision point intersection is an intersection of at least three road segments at which a driver entering the intersection along one of said at least three road segments has a choice of legally exiting the intersection along one at least two other of said at least three road segments;

wherein the exit point corresponds to the first eligible decision point intersection along a path of one or more connected road segments in a single legal direction of travel from the entry point along the identified road segment leading away from the entry point; and

node data entities that represent end points of individual road segments.

13. The invention of claim 12 wherein said geographic database is stored on a computer-readable medium.

14. The invention of claims 12 further comprising:

nominal path data that indicate for each road segment along which each intersection can be legally entered one and only one default road segment from which the intersection can be exited.

15. The invention of claim 14 wherein said transition point pairs include a nominal type and a variant type,

wherein the nominal type of transition point pair corresponds to road segments that follow the nominal path from the entry point thereof to the exit point thereof;

and

wherein the variant type of transition point pairs correspond to road segments that do not follow the nominal path at each intersection between the entry point thereof and the exit point thereof.

16. The invention of claim 15 wherein each data entity that represents a variant transition point pair includes data that identify each intersection at which a path of travel along road segments from the entry point thereof to the exit point thereof deviates from the nominal path defined therefor and further that identify the road segment to follow from said intersection to reach the exit point.

17. A geographic database that represents a road network located in a geographic area, wherein the geographic database comprises:

a first subset of data used for route calculation comprising;

data entities that represent transition point pairs, wherein each of said data entities that represent a transition point pair comprises data that indicate an entry point, a road segment leading away from the exit point, an exit point, and a travel cost for traveling from the entry point to the exit point along the road segment leading away from the entry point, wherein each entry point and exit point are decision point intersections, wherein a decision point intersection is an intersection of at least three road segments at which a driver entering the intersection along one of said at least three road segments has a choice of legally exiting the intersection along one at least two other of said at least three road segments; and

node data entities that represent end points of individual road segments; and

a second subset of data used to determine road segments that correspond to transition point pairs, wherein said second subset of data includes nominal path data that indicate for each road segment along which each intersection can be legally entered one and only one default road segment from which the intersection can be exited.

18. The invention of claim 17 wherein said geographic database is stored on a computer-readable medium.

19. The invention of claim 17 wherein said transition point pairs include a nominal type and a variant type,

wherein the nominal type of transition point pairs correspond to road segments that follow the nominal path from the entry point to the exit point; and

wherein the variant type of transition point pairs correspond to road segments that do not follow the nominal path at each intersection between the entry point and the exit point.

20. The invention of claim 19 wherein each data entity that represents a variant transition point pair includes data that identify each intersection at which a path of travel along road segments from the entry point to the exit point deviates from the nominal path defined therefor and further that identify the road segment to follow from said intersection to reach the exit point.

21. The invention of claim 17 wherein each data entity that represents a transition point pair includes data that identify the road segment which corresponds to the transition point pair and which is connected directly to the exit point.