Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2002-09-16
2004-12-28
Rones, Charles (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06836781
ABSTRACT:
The present invention relates to geographic data and more particularly the present invention relates to a way to represent a road network in a geographic database to facilitate certain navigation-related functions, such as route calculation.
Navigation systems provide useful features, such as calculating a route to a desired destination and providing guidance for following the route. In order to provide these features, navigation systems use geographic databases that include information about the locations of roads and intersections, estimated travel times along roads, the speed limits along roads, etc. Geographic databases used by navigation systems also include data about traffic restrictions, such as one-way streets, no-left-turns, etc., so that the navigation system can calculate a legal route (i.e., a route that conforms to applicable traffic laws and regulations). Using a geographic database, programming algorithms used in navigation systems can find an optimal (e.g, fastest or shortest) route to a specified destination.
A conventional way to represent roads in a geographic database is to represent them as discrete segments, i.e., wherein a segment corresponds to the portion of a road between intersections. In this kind of model, traffic restrictions (such as turn restrictions) are treated as properties of a road segment. This model conforms to the way roads are perceived and generally works well.
FIG. 1
is an illustration of a portion of a road network
10
.
FIG. 2
is a diagram that illutrates how the road network
10
shown in
FIG. 1
is represented in a conventional geographic database
14
.
In some geographic databases, a series of connected individual road segments are represented as an aggregation in order to facilitate some types of functions for which geographic databases are used. Examples of geographic databases in which a series of connected road segments are represented as an aggregation are disclosed in U.S. Pat. Nos. 6,038,559 and 6,112,200, the entire disclosures of which are represented by reference herein.
Although the conventional way of representing roads works well, there is room for improvement. For example, calculating a route using a geographic database can be computationally intensive. It would be beneficial if roads could be represented in a geographic database in a way that further facilitates certain functions, such as route calculation.
SUMMARY OF THE INVENTION
To address these and other objectives, an embodiment of the present invention comprises 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, 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.
REFERENCES:
patent: 6026384 (2000-02-01), Poppen
patent: 6421659 (2002-07-01), Nomura
patent: 6430499 (2002-08-01), Nakano et al.
patent: 6480783 (2002-11-01), Myr
patent: 6708112 (2004-03-01), Beesley et al.
Abel-Jalil Neveen
Kaplan Lawrence M.
Kozak Frank J.
Navteq North America, LLC
Rones Charles
LandOfFree
Method for streamlined representation of roads in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for streamlined representation of roads in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for streamlined representation of roads in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3312769