System and method for using a map database with attributed no-outlet and circular segments

• US 6,609,063 B1
• Filed: 10/12/2001
• Issued: 08/19/2003
• Est. Priority Date: 10/12/2001
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Lehman, Laurence P., Chow, Derwin, Bender, Raymond
• Primary Examiner(s): NGUYEN, TAN QUANG
• Application Number:
  US09/976,424
• Time in Patent Office: 676 Days
• Field of Search: 701/201, 701/203, 701/209, 701/210, 701/211, 340/990, 340/995
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3874 Structures specially adapted for data searching and retrieval
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

System and method are provided for route calculation for use with a navigation system and used with a map database with attributed no-outlet and circular segments. A route calculation program adapted to find at least one solution route, between a first location and a second location on a road network, identifies a segment with a first node and a second node in the road network. From an attribute stored in the map database, the program determines whether the first node is connected to the road network and the second node is connected to an isolated portion of the road network. Using the attribute, the route calculation program determines whether to explore the isolated portion of the road network. In some instances, the program refrains from exploring the segment leading into the isolated portion of the road network and the isolated portion of the road network itself. In some other instances, the program suppresses the search from exploring segments inside the isolated portion of the road network, and the program exits the isolated portion by exploring the segment and its successor segments.

Claims

1. An improved method of operation for a route calculation program used with a map database stored on a computer readable storage medium, wherein the route calculation program includes program instructions adapted to find a solution route between a first location on a road network represented by the map database and a second location on the road network represented by the map database, wherein the road network is represented in the map database by data that represent each segment of each road between endpoints thereof, and wherein the program instructions find the solution route by evaluating attributes of the represented segments of roads in order to determine a series of segments connecting the first location and the second location,

wherein the improved method of operation for the route calculation program comprises:

determining from an attribute stored in the map database whether a first segment is connected to an isolated portion of the road network while evaluating attributes of represented segments for inclusion in the solution route; and

upon a determination that the first segment is connected to an isolated portion, determining whether to evaluate additional segments in the isolated portion of the road network for inclusion in the solution route.

2. The method of claim 1 further comprising:

refraining from evaluating the additional segments in the isolated portion of the road network upon the determination that the first segment is connected to an isolated portion.

3. The method of claim 1 wherein the first segment is the only segment that connects a non-isolated portion of the road network with the isolated portion of the road network.

4. The method of claim 3 wherein the attribute indicates that the first segment is a no-outlet segment.

5. The method of claim 3 further comprising evaluating the first segment for inclusion in the solution route if the first segment is encountered from inside the isolated portion of the road network.

6. The method of claim 1 further comprising suppressing evaluation of additional segments located inside the isolated portion of the road network.

7. The method of claim 1 wherein the first segment is one of plural segments that connect the isolated portion of the road network to a non-isolated portion of the road network, wherein all of the plural segments connect to one road at different locations along the one road.

8. The method of claim 7 wherein the attribute indicates that the first segment is a circular segment.

9. The method of claim 1 wherein the isolated portion of the road network is a dead-end road.

10. The method of claim 1 wherein the isolated portion of the road network is represented in the map database as a collapsed node.

11. The method of claim 1 wherein the map database includes a plurality of data structures with attributes, wherein each data structure represents a road segment and its associated nodes.

12. A method for a route calculation search performed by a route calculation program, the method comprising:

retrieving a data structure in a map database that represents a successor segment with a first node and a second node;

identifying an attribute in the data structure that identifies the successor segment as a segment that connects an isolated portion of a road network at the second node thereof to a non-isolated portion of the road network at the first node thereof; and

refraining from evaluating the isolated portion of the road network if the route calculation search retrieved the successor segment at the first node.

13. The method of claim 12 further comprising:

determining a solution route by matching at the first node a first search initiated at an origin located in the non-isolated portion of the road network with a second search initiated at a destination located within the isolated portion of the road network.

14. In a navigation system in which geographic data are used by an end user'"'"'s platform to provide navigation related features to an end user, a method comprising:

using data structures in the end user'"'"'s computing platform, wherein each data structure includes;

a) fields with data that represent a segment of a road in a road network; and

b) a data attribute in one of the fields that identifies the segment as one that connects a non-isolated portion of the road network with an isolated portion of the road network;

wherein the end user'"'"'s computing platform uses the attribute to determine whether to evaluate segments in the isolated portion of the road network for inclusion in a calculated route.

15. The method of claim 14 wherein the end user is located in a vehicle .

16. The method of claim 14 wherein the end user'"'"'s computing platform comprises a navigation system unit in a vehicle.

17. A navigation system comprising:

a map database for storing attributes that characterize segments of roads, including attributes that indicate whether a segment leads to an isolated portion of the road network; and

a navigation program for calculating a route between a first location on the road network represented by the map database and a second location on the road network represented by the map database;

wherein the navigation program uses the attributes to determine whether to explore an isolated portion of the road network.

18. The method of claim 17 wherein the isolated portion of the road network is connected to a non-isolated portion of the road network by only a single road segment.

19. The method of claim 17 wherein the isolated portion of the road network is connected to a non-isolated portion of the road network by plural road segments, wherein all of the plural segments connect to one road at different locations along the one road.