Method and system for map display in a navigation application

• US 6,092,076 A
• Filed: 03/24/1998
• Issued: 07/18/2000
• Est. Priority Date: 03/24/1998
• Status: Expired due to Term

• Current Assignee: Navigon AG (Garmin Limited)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: McDonough, William, Rao, Srinivasa, Srivastava, Ashutosh
• Primary Examiner(s): HO, RUAY L
• Application Number:
  US09/047,141
• Time in Patent Office: 847 Days
• Field of Search: 707/1-10, 707/100-104, 707/200-206, 345/326-335, 455/456
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3667 Display of a road map G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635
• CPC Class Codes: G09B 29/106 using electronic means
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A program and method for a map display tool for use with a navigation system and used with a map database. The map display tool is adapted to render a map on a display or in a graphics buffer for a predetermined geographic region. The map display tool includes a map processing layer for performing the essential data manipulation, a graphics interface layer that maintains a series of look up tables with graphics commands, and a primitive layer customized to interact with an underlying graphics platform and the graphics interface layer. The map display tool renders a map by retrieving data items from the map database and processing each data item. Shape information is rendered on a screen or in a graphics buffer, name information is buffered and sorted to optimize filtering, prioritization, spatial conflicts resolution and other tasks prior to rendering.

Claims

1. A map display program for use in a navigation system having a graphics platform and a map, the map display program adapted to retrieve and display geographical information representative of a first position in response to requests from a navigation application in the navigation system, the map display program comprising:

a map processing layer containing a plurality of map display functions, the map processing layer responsive to the navigation application and in communication with a graphics interface layer;

the graphics interface layer having at least one lookup table, the at least one lookup table comprising drawing attribute information, the graphics interface layer responsive to instructions from the map processing layer; and

a primitive layer in communication with the graphics interface layer and the graphics platform, the primitive layer populating the at least one lookup table in the graphics interface layer with platform specific data types from the graphics platform, wherein the map processing layer is independent of the graphics platform.

2. A map display program for use in a navigation system used with a map database, the map display program adapted to retrieve and display geographical information representative of an area in response to requests from a navigation application in the navigation system, the map display program comprising:

a map object comprising;

map data relating to a geographical area;

a name table having a plurality of name storage locations for holding a plurality of roadway names retrieved from the map database, each name storage location containing a first list of roadway names; and

at least one name placement position associated with each of the roadway names, wherein the name placement position represents a position on a display.

3. The map display program of claim 2, further comprisingapoint of interest list, the point of interest list containing data from the map database pertaining to at least one point of interest name and location data for the point of interest name.

4. The map display program of claim 2, wherein the plurality of name storage locations contain a plurality of roadway shield icons.

5. The map display program of claim 2, wherein the map display program further comprises:

a name prioritization routine adapted to select roadway name information from the name table according to a predetermined priority list; and

at least one prioritized information list located in the map object, the prioritized information list generated by the name prioritization routine and containing data associated with names selected by the name prioritization routine.

6. The map display program of claim 5, further comprising:

a point of interest list, the point of interest list containing data from the map database pertaining to at least one point of interest name and location data for the point of interest name; and

a list of roadway shield icons in the plurality of name table locations in the name table, wherein the name prioritization routine is adapted to select roadway name information and roadway shield icon information from the name table according to the priority list; and

wherein the name prioritization routine is adapted to select point of interest names according to the priority list.

7. The map display program of claim 6, wherein the prioritized information list further comprises located in the map object, the prioritized information list generated by the name prioritization routine and containing data associated with names and icons selected by the name prioritization routine.

8. The map display program of claim 7, wherein the plurality of prioritized information lists comprises:

a list of prioritized roadway names, a list of prioritized roadway shield icons, and a list of prioritized point of interest names; and

a list of spatial extents representative of area on the display required by the prioritized lists of roadway names, roadway shield icons, and point of interest names.

9. A method of preparing name information for placement on a map display of a navigation system, the method comprising the steps of:

retrieving map data for a predetermined geographical area from a map database stored on a computer readable medium, the map data comprising name information;

generating a name table in a map object, the name table comprising all name information for the retrieved map data;

selecting name information from the name table using a predetermined set of name priority rules stored in the map object; and

generating at least one list in the map object containing the selected name information in the map object.

10. The method of claim 9, wherein the step of generating a name table comprises:

using a hashing function to create a name table having a plurality of name storage locations for holding a plurality of roadway names contained in the map data retrieved from the map database, wherein each name storage location comprises a roadway name list containing roadway names and associated roadway name locations in the name storage location, by

determining a proper name storage location for each retrieved roadway name;

determining whether the retrieved roadway name is present in the roadway name list in the proper name storage location;

if the retrieved roadway name is not already present in any of the name storage locations, adding the retrieved roadway name to the roadway name list in the proper name storage location; and

if the retrieved roadway name is already present in the proper name storage location in the name table, adding an additional roadway name location to the roadway name in the roadway name list.

11. The method of claim 9, further comprising the step of generating a point of interest name list from map data retrieved from the map database, wherein the point of interest name list is a linked list created in the map object.

12. A map display program for use in a navigation system used with a map database, the map display program adapted to retrieve and display geographical information representative of an area in response to requests from a navigation application in the navigation system, the map display program comprising:

a map processing layer containing a plurality of map display functions, the map processing layer responsive to the navigation application;

wherein the map processing layer further comprises a plurality of conditional statements executed from each of the map display functions forming the map display layer, each of the conditional statements operative to check for a substitute routine and execute the substitute routine if available, whereby the map display program is configurable through the presence of the substitute routine;

a graphics interface layer having at least one lookup table and at least one drawing processing function, the at least one lookup table comprising drawing attribute information; and

a primitive layer in communication with the graphics interface layer and a graphics platform, the primitive layer populating the lookup tables in the graphics interface layer with platform specific data types from the graphical function platform, wherein the map processing layer is independent of the graphics platform.

13. The map display program of claim 12, wherein the graphics interface layer further comprises a plurality of graphics processing conditional requests executed by the drawing processing functions, each of the graphics processing conditional statements operative to check for a substitute graphics processing routine and execute the substitute graphics processing routine if available, whereby the map display program is configurable through the presence of the substitute graphics processing routine.

14. The invention of claim 12, wherein the plurality of conditional statements in the map processing layer comprises a map projection conditional statement, the map projection conditional statement configured to look for a substitute coordinate transform routine from the navigation application.

15. The invention of claim 12, wherein the plurality of conditional statements in the map processing layer comprises a display projection conditional statement, the display projection conditional statement configured to look for a substitute coordinate transform routine from the navigation application to transform coordinates into a display coordinate system.

16. The invention of claim 12, wherein the plurality of conditional statements in the map processing layer comprises a name management conditional statement, the name management conditional statement configured to look for a substitute name management routine from the navigation application to manage name information retrieved from the map database.

17. A method of rendering a map on a display in a navigation system, the method comprising the steps of:

providing a map display tool having a set of map processing functions and a map data structure;

retrieving a plurality of map data items for a predetermined geographical area from a map database stored on a computer readable medium, each of the map data items comprising feature information and name information corresponding to the feature information;

drawing the feature information to a display with the map display tool;

storing the name information in the map data structure; and

after drawing the feature information for all of the plurality of retrieved map data items, processing the name information in the map data structure and drawing the name information in the map data structure to the display.

18. The method of claim 17, wherein the step of processing the name information comprises, prioritizing the name information in the map data structure according to a priority list in the map data structure.

19. The method of claim 18, wherein the step of processing name information further comprises performing a spatial conflicts determination of the name information in the map data structure.