Method and apparatus for storing cartographic route data

• US 6,188,955 B1
• Filed: 12/30/1998
• Issued: 02/13/2001
• Est. Priority Date: 12/30/1998
• Status: Expired due to Term

• Current Assignee: Garmin Corporation (Garmin Limited)
• Original Assignee: Garmin Corporation (Garmin Limited)
• Inventors: Beesley, Darin J., Walters, Thomas H., Robinson, Stephen C.
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US09/223,553
• Time in Patent Office: 776 Days
• Field of Search: 701/200, 701/115, 701/206, 701/208, 701/209, 701/212, 701/300, 701/23, 701/25, 701/201, 340/988, 340/990, 340/995, 731/78.R
• US Class Current: 701/200
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

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 thoroughfare planning device capable of calculating the distance to a desired thoroughfare. To calculate a distance, a driver inputs a plurality of variables, including cartographic data and a final desired destination, as well as several potential additional variables. Upon receiving the driver inputs, the navigation device implements a three-level hierarchy for storing, recalling and processing cartographic data. After the cartographic data is stored in memory, the navigation unit can calculate distance to a thoroughfare utilizing a cascading search method beginning with searching the most specific first level and progressing to the broader second and third levels until a common network between the two locations is established. The navigation device can also utilize the three level hierarchy to display cartographic data as a graphical map on the unit utilizing the same cascading method to display detail on the display screen and locate the specific details on any coordinate on the screen. Therefore the navigation unit utilizes the same three level hierarchy to calculate distance to a desired destination and to display a graphical representation of the map.

Claims

1. An electronic navigation device for planning a route over at least one of a plurality of thoroughfares, from a starting location to a selected destination, said device comprising:

a processor;

a memory connected to said processor, said memory having data indicative of said thoroughfares, wherein each of said thoroughfare has a plurality of associated features, wherein selected features are associated to form links of features, and wherein selected links are associated to form networks of links,

wherein said processor determines whether said selected destination and said starting location are within the same said feature, and when said selected destination and said starting location are within the same said feature, said processor defines said route on said common feature;

when said selected destination and said starting location are not within the same said feature, said processor determines whether said selected destination and said starting location are within the same said link and, when said selected destination and said starting location are within the same said link, said processor defines said route on said common link; and

when said selected destination and said starting location are not within the same link, said processor determines whether said selected destination and said starting location are on the same network and, when said selected destination and said starting location are on the same network, said processor defines said route on said common network.

2. The electronic navigation device as set forth in claim 1, wherein, when said selected destination and said starting location are not within a common network, said processor establishes a straight line from said starting location to said selected destination and permits a user to input at least one intersection of two networks to establish a common network.

3. The electronic navigation device as set forth in claim 1, in combination with a moving vehicle, wherein said processor establishes said starting location as a current location of said device as calculated by said processor.

4. The electronic navigation device as set forth in claim 3, wherein said current location is calculated at periodic intervals.

5. The electronic navigation device as set forth in claim 4, wherein said periodic interval is once every second.

6. The electronic navigation as set forth in claim 4, wherein said current location is utilized to update said route distance.

7. An electronic navigation method for planning a route over at least one of a plurality of thoroughfares, from a starting location to a selected destination, said method comprising:

associating a plurality of features with each said thoroughfare;

associating said selected features to form lengths of features;

associating selected said lengths of features to form networks of said lengths;

determining whether said selected destination and said starting location are within the same said feature, and when said selected destination and said starting location are within the same said feature, defining said route on said common feature;

when said selected destination and said starting location are not within the same said feature, determining whether said selected destination and said starting location are within the same said link and,

when said selected destination and said starting location are within the same said link, defining said route on said common link; and

when said selected destination and said starting location are not within the same said link, determining whether said selected destination and said starting location are on the same network and, when said selected destination and said starting location are on the same network, defining said route on said common network.

8. A navigation device comprising:

a processor;

a display, connected to said processor;

a memory connected to said processor, said memory containing cartographic data, including a thoroughfare having a name, wherein at least a portion of said thoroughfare is displayed on said display; and

an input, said input being operable to identify any point on said portion of said thoroughfare displayed on said display, whereupon such identification said processor retrieves said name of said thoroughfare from said memory and displays said name on said display.

9. The navigation device of claim 8, wherein said thoroughfare has a thoroughfare classification and a cartographic set of two-dimensional coordinates and wherein said processor retrieves and displays said name of said thoroughfare from said memory and at least one of said thoroughfare classification and said two-dimensional coordinates.

10. A cartographic data storage device comprising:

a plurality of first level records, wherein each record in said first level contains at least one of a name of a thoroughfare, a thoroughfare classification of a thoroughfare, and data indicative of a change in cartographic coordinates of a section of said thoroughfares;

a plurality of second level records, wherein each of said records in said second level contains selected records of said first level; and

a plurality of third level records, wherein each said record on said third level contain records of said second level having a matching said name,

wherein a sorted list containing a field sorted by said name, a field sorted by an X-coordinate of said cartographic coordinates, a field sorted by a Y-coordinate of said cartographic coordinates, and a field sorted by said thoroughfare classification is utilized to construct said second level records and said third level records.