Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2003-04-25
2004-03-16
Jeanglaude, Gertrude A. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S023000, C701S201000, C701S208000, C701S209000, C701S212000, C340S990000
Reexamination Certificate
active
06708112
ABSTRACT:
BACKGROUND OF THE INVENTION
Certain embodiments of the present invention generally relate to systems and methods for calculating navigation routes based on map databases indicative of adjacent geographic regions.
Route planning systems are well known in the field of navigational instruments. Route planning systems in general define one or more paths through a network of roads between source and destination locations. The path(s) planned by the system may be based on one or more criteria, such as shortest distance, shortest time, user preferences and the like. Several algorithms are known for performing route planning, with such algorithms calculating the route from the source or destination location or from both simultaneously. Conventional planning algorithms operate based on a predefined stored map database, which includes data indicative of a geographic region containing the source and destination locations.
In general, each map database corresponds to a particular geographic region, such as a city, a county, a state, a country, a continent, etc. Each map database contains data indicative of features within the associated geographic region with varied levels of specificity concerning the features. In general, map databases representing smaller geographic regions (e.g. cities) contain more detailed feature information (county roads, city streets, restaurants, and the like), while map databases representing larger geographic regions (e.g. states and countries) contain less detailed feature information (e.g. interstates, state highways, gas stations, hotels, rest stops, and the like). The feature information stored within each map database may include geographic coordinates (i.e. altitude, longitude and latitude) among other things. Each map database is bound by a geographic region perimeter or boundary that is intersected by roads of the roadway network that extend beyond the boundary.
Conventionally, a navigable network is comprised of roads, ferry routes, and possibly other means to travel from one location in the network to another. Conventionally the navigable network is described as a collection of intersections (know as nodes) of navigable features and links, arcs or paths (road, ferry, etc.) connecting nodes. Thus, the navigable network is viewed as a collection of nodes, at each of which a travel direction decision may be made, and a collection of links or arcs connecting the nodes and describing a travel path from one node to another. The term adjacency is conventionally used to describe the travel path and nodes reachable in the network from a given node. A solution between two points in the network involves iteratively examining the adjacencies from the start and destination points in the network, eventually “discovering” a low-cost path. Several well-known algorithms are designed to solve this problem, such as the A-star algorithm, various shortest path algorithms and the like.
Presently, cartographic information is charted or mapped by data suppliers as large cartographic data blocks. A single cartographic data block may include detailed maps for multiple adjoining metropolitan areas and/or detailed maps for large geographic areas and the like. A cartographic data block is typically divided by the data suppliers, by manufactures of the routing devices or by service providers into smaller map databases having a size more conducive to storage on, or wireless transmission to, a navigation or route planning device. By way of example only, a large block of cartographic data may constitute a detailed map of the metropolitan corridor for the East coast between Washington, D.C. and Boston. The cartographic data block may be divided into a first map database for the Washington, D.C. metropolitan area, a second map database for the Baltimore metropolitan area, a third map database for the Philadelphia metropolitan area, and so on. Unfortunately, a route cannot currently be charted using two separate map databases. For example, a route cannot be charted from an address located in Washington D.C. to a destination located in Baltimore using the aforementioned map databases.
Hence, conventional navigation and route planning devices are unable to plan routes between source and destination locations that are located in separate map databases, even if the separate map databases are adjacent to one another. Because conventional navigation and route planning devices are only able to calculate paths between sources and destinations in a single map database, the user is required to separately enter source and destination locations within each discrete map database. Stated another way, conventional systems provide map databases to describe the roadway network within a specific selected geographic area, but do not provide a means for the node exploration step to continue into adjacent geographic areas.
A need exists for improved navigation and route planning devices capable of automatically calculating routes between a single source location and a single destination location based on adjacent map databases. A need exists for a navigation device capable of accessing adjacent map databases to plan a route.
BRIEF SUMMARY OF THE INVENTION
It is a goal of certain embodiments of the present invention to enable node exploration to continue into adjacent geographic areas, effectively enabling a route to be computed through an arbitrary number of separately constructed, but adjacent, networks.
Certain embodiments of the present invention relate to a method for providing a navigation route between two locations. The method includes providing first and second data maps of different geographic regions. A group of potential paths are planned from the first location through the first geographic region based on the first data map. When each potential path intersects an edge of the first data map, a transition point in the second data map is identified based on the location where a current potential path intersects the edge of the first data map. The current potential path is further planned from the transition point into and/or through the second geographic region, based on the second data map, towards the second location. Optionally, the data maps may constitute first and second map databases which include data indicative of a roadway network or of nodes at which the roads intersect edges of the data maps. The method locates node coordinates where the roadway network intersects an edge of the first data map. The node coordinates may be used to identify the transition point. The data indicative of the node coordinates, at which roads intersect the edges of the first and second data maps, may be compared to identify the transition point in the second data map. The node coordinates are stored in an edge table associated with the second data map. Edge tables are searched for node coordinates which match the location where the current potential path intersects the edge of the first data map.
Optionally, multiple data maps may be analyzed corresponding to the geographic regions adjacent to the first geographic region, and one of the data maps may be selected as the second data map. The two adjacent data maps may be identified by organizing multiple data maps into a bounded box layout. To continue planning the current potential path through the second data map, node expansions are performed by looking at the nodes in the second data map that are linked to the transition point.
In accordance with another embodiment, a map database is recorded on a computer readable medium. The map database includes nodal records stored in a linked structure. The nodal records contain data indicative of nodes in a roadway network located in a geographic region within defined boundaries. Data indicative of the roads that intersect and join other nodes is also stored. Optionally, the nodal records may identify the nodes, the distance to the adjacent nodes, and the speed data for the roads connecting the nodes. The nodal records also include edge markers which indicate which nodes intersect the boundaries of the geographic reg
Beesley Darin J.
Childs Michael
Garmin Ltd
Jeanglaude Gertrude A.
Rolf Devon A.
LandOfFree
System and method for calculating a navigation route based... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for calculating a navigation route based..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for calculating a navigation route based... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3291404