System and method for using a map database with attributed no-outlet and circular segments
First Claim
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.
5 Assignments
0 Petitions
Accused Products
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.
45 Citations
19 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
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. - View Dependent Claims (13)
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. - View Dependent Claims (15, 16)
-
-
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. - View Dependent Claims (18, 19)
-
Specification