Data processing: vehicles – navigation – and relative location – Navigation
Reexamination Certificate
1998-12-30
2001-02-13
Cuchlinski, Jr., William A. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
C701S025000, C701S201000, C701S206000, C701S209000, C701S208000, C701S211000, C340S988000, C340S990000, C073S17800T
Reexamination Certificate
active
06188955
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
In general, this invention relates to the storage of geographic feature data and more particularly, to a method and apparatus for storing geographic coordinate data in an efficient manner to be utilized for both graphical and navigational processes.
2. Description of the Related Art
Route planning devices are well known in the field of navigational instruments. The method of route planning implemented by known prior art systems depends on the capabilities of system resources, such as processor speed and the amount and speed of memory. As increased system capability also increases system cost, the method of route planning implemented by a navigation device is a function of overall system cost. Some of the higher cost systems implement a nodal analysis in which the route planning system determines every potential path from a present location to a desired location from data stored in memory. The route planning system then examines each potential path and eliminates paths by built-in criteria such as type of road traversed, shortest distances or user inputted preferred routes. The higher cost route planning systems require a great amount of memory storage space to store every potential route, as well as a need for a powerful processor to analyze the enormous amount of data stored in the memory. These route planning systems provide very accurate route planning data with little or no user intervention. While highly accurate navigational devices eliminate user intervention, their corresponding high cost eliminates a potential market which is unwilling to pay the cost associated with the accuracy and the ease of little intervention.
On the other end of the cost spectrum, some lower cost route planning systems implement a straight line approach in determining the distance between a desired destination and a current location. In this approach, the processor creates a straight line from the present location to the final destination and measures that straight line distance. The low cost system route planning data can be highly inaccurate because the system does not take into account actual thoroughfare layouts. For example, if a desired destination is on a mountain, the straight line distance from a current location might be only six miles. However, if the only available road to that destination is a windy road around the mountain entailing 30 miles of actual driving, the route planning distance calculated by a low cost system implementing the straight line method will be inaccurate. Because the low cost systems are so inaccurate, the practicality of their implementation is reduced by their large potential for error.
In order to effectuate a route planning method, most systems require the cartographic data to be stored as a record in memory. Additionally, many of the prior art systems also require the same cartographic data to be stored as a record in memory a second time for use in graphically representing the cartographic data on a display screen. Because the data contained within both records is repetitive, the redundancy creates a burden on the memory resources of the route planning system. This burden increases substantially in the higher cost systems because of the larger amounts of data needed by the system. Thus, both the high cost and the low cost navigational devices unduly burden system resources by the use of separate navigation and graphical record banks.
Current prior art systems have created a spectrum of products in which the degree of navigational accuracy is dictated primarily by the cost of the system. The lower cost systems currently offer a low degree of accuracy inadequate for users. In addition, both the higher cost and the lower cost system burden overall navigational system resources by the duplication of cartographic data. Therefore, there exists a need for a navigational route planning device which is more accurate than current low cost systems, without requiring the more expensive system resources. In addition, there is also a need for a navigational route planning device that does not unnecessarily burden system resources with redundant, duplicative cartographic data
SUMMARY OF THE INVENTION
Based on the above noted deficiencies in the related art, it is an object of the present invention to provide a low cost navigational route planning system which is more accurate than current low cost systems with minimal user intervention. It is the further object of the present invention to eliminate any unnecessary duplicative cartographic data stored in memory. Finally, it is the object of the present invention to provide an efficient format for storing and recalling navigational and graphical data in one memory location.
These and other objects of the present invention are achieved by a method and device implementing a three-level hierarchy for storing, recalling and processing navigational and graphical data. A vehicle is equipped with an electronic navigation route planning device of the present invention capable of calculating the distance to a desired destination along a desired route and displaying a geographical representation of that route. To initiate the system, a driver inputs a plurality of variables, including the cartographic data and a final desired destination, as well as several potential additional variables such as driver identity, thoroughfare preferences, thoroughfare class limitations or display format preferences. Alternatively, the cartographic data may be prestored in the navigation device. Upon receiving the driver inputs, the navigation device implements a three-level hierarchy for storing, recalling and processing cartographic data. It will be appreciated that this step may already be complete on prestored cartographic data cartridges or completed during the implementation of the system software prior to its sale.
Before any calculation or display processes are executed, the cartographic data is first divided into basic two dimensional X and Y geographic coordinates. Thus, a thoroughfare will be dictated by the X and Y coordinates it traverses. To define a particular thoroughfare, the navigation device is concerned with the change in X and Y coordinates. For example, if a thoroughfare is relatively straight, the coordinates within that thoroughfare will only change along one axis. However, if a particular thoroughfare has turns or is windy, there will be frequent changes in coordinates along both axis. The navigation device implements a mathematical formula which optimizes the storage of the change in coordinates of a thoroughfare into approximately sized equal data records. Because increased coordinate changes require additional storage space, the more changes in a thoroughfare's coordinates, the more data records the navigation device requires to store those changes.
Each coordinate change data record created by the optimizing formula is known as a feature. Within each feature data record, the navigation device creates a field storing the coordinate changes as optimized by the mathematical formula as well as a field containing the thoroughfare's principal name, fields containing the thoroughfare's alternative names and a field containing the road classification of the particular thoroughfare.
After the entire cartographic area is broken down into equal sized data features, the navigation device creates a sorted list containing the endpoints of all the feature data records. The sorted list contains four separate fields in which the feature records are sorted by that field's criteria such as alphabetically by the principal name or alternate name fields, ascending by the X-coordinates of the two dimensional endpoints of each feature record, ascending by the Y-coordinates of the two dimensional endpoints of each feature record and by a thoroughfare's classification.
The navigation device groups those features which are related or connected into a second data record known as links. To construct a link record, the navigation device will only group those feature data reco
Beesley Darin J.
Robinson Stephen C.
Walters Thomas H.
Arthur Gertrude
Cuchlinski Jr. William A.
Garmin Corporation
Shook Hardy & Bacon LLP
LandOfFree
Method and apparatus for storing cartographic route data 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 and apparatus for storing cartographic route data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for storing cartographic route data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2593567