Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2001-12-11
2003-06-03
Arthur, Gertrude (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S023000, C701S201000, C701S208000, C701S212000, C340S990000
Reexamination Certificate
active
06574554
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 overlapping, non-contiguous geographic regions. Certain embodiments of the present invention generally relate to navigation systems and methods that utilize roadway map databases organized in different tiers or levels of a map hierarchy.
Route planning systems are well known in the field of navigational instruments. Route planning systems in general calculate 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. For example, each map database includes data indicative of nodes representing intersections between roadways and data indicative of segments representative of roadway portions extending between nodes. 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.
Conventional methods for route planning depend on the capabilities of system resources, such as processor speed and the amount and speed of memory. To reduce the amount of memory needed, route planning or navigation devices typically do not store a detailed map of a large geographic area, such as North America. Instead, the memory for the route planning or navigation device is initially loaded with a detailed map (e.g. a map database containing detailed feature information for a small geographic region) only for a select geographic region, such as a particular city in which the user travels. When the user wishes to chart a path across a particular city, the user enters the source and destination locations in the particular city. The route planning or navigation device uses the detailed map database for the corresponding city map to plan a route between the source and destination locations. Both the source and destination locations are within the boundaries of the detailed map (i.e. within the particular city).
The route planning or navigation device may instead be loaded with a less detailed “base” map (e.g. map database containing general feature information for a large geographic region), such as the United States. When the user wishes to chart a path between cities, across the country, etc., the user first selects or loads the base map and then enters the source and destination locations. The route planning and navigation device accesses and plans a route through the base map. Hence, for long trips, the route planning and navigation device only utilizes the base map and thus is only able to offer limited information regarding the details of a planned route.
Due to memory constraints, the base map database includes less detailed feature information and may lack feature information surrounding the source and destination locations of interest to the user. The user may desire detailed feature information present only in a detailed map database, such as street information for source and destination cities. In general, each map database is stored on a separate CD. The route planning and navigation device typically only accesses a single CD at any given time since the user can only load one CD at a time. Heretofore, the user could only chart routes through one detailed map database or through one base map database at any particular time, namely when the appropriate CD was loaded.
For example, when planning a trip between Kansas City and Denver, the user would load a CD into the route planning device containing only the base map database that would encompass both cities. The user would then enter source and destination coordinates within the base map database. If the user desired detailed street information for Kansas City, for example, directions to Arrowhead Stadium, conventional navigation devices were unable to provide such information while simultaneously providing a route between cities since the street information was only on detailed map databases, while only the base map database could be used to provide routing. Instead, the user was required to remove the CD containing the base map database and load a CD containing a detailed map database for Kansas City. The user then entered a source location, such as along interstate 70 on the west side of town, and a destination location for Arrowhead Stadium. Similarly, if the user desired detailed street information for Denver, the prior CD containing the Kansas City street map must be removed and a separate CD containing a detailed street map for Denver must be loaded. Source and destination locations would again need to be entered by the user for the Denver area. In the foregoing example, conventional navigation devices require the user to load three separate CDs and to perform three separate source and destination data entry procedures.
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 supplier, by the manufacturer of the routing devices or by the service provider 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, DC and Boston. The cartographic data block may be divided into a first map database for the Washington, DC metropolitan area, a second map database for the Baltimore metropolitan area, a third map database for the Philadelphia metropolitan area, and so on. The map databases for Washington, DC and Baltimore may include matching roadway/boundary longitude and latitude coordinates since the map databases were “cut” from a common cartographic data block or “fabric”. However, each map database would nonetheless be provided as a separate map, such as on a separate CD. Accordingly, users would be required to switch CDs and perform independent routing operations based on discrete, separate map databases.
Today, numerous data suppliers map and chart roadway networks independent of one another. Typically, cartographic data from one supplier does not match cartographic data from a different supplier. Hence, when cartographic data blocks from different suppliers are divided into map databases, the map databases from different suppliers do not match, even though the map databases may be for common or overlapping geographic areas. For example, cartographic data for a map of Washington, DC from one data supplier will include geographic coordinates for the U.S. Capital that may differ (albeit slightly) from geog
Beesley Darin J.
Childs Michael
Arthur Gertrude
Garmin Ltd.
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-3121740