Method and system for representation of overlapping features in geographic databases

• US 6,118,404 A
• Filed: 01/21/1998
• Issued: 09/12/2000
• Est. Priority Date: 01/21/1998
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Fernekes, Robert P., Yates, Robert, Nyczak, Gregory M., Israni, Vijaya
• Primary Examiner(s): Blum, Theodore M.
• Application Number:
  US09/010,324
• Time in Patent Office: 965 Days
• Field of Search: 701/208, 701/209, 701/210, 340/990, 340/995, 342/357.13
• US Class Current: 342/357.43
• 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: G01C 21/3878 Hierarchical structures, e.g. layering

Abstract

A system and method for storing and using data representing crossings of geographic features, and an associated product having the data embodied thereon, for use with a computer based navigation system, is disclosed. A computer-readable medium has computer-readable data embodied thereon that represents geographic features in a geographic region. The computer-readable data includes a plurality of data entities of a first type each of which represents a respective one of a plurality of linearly extending geographic features and a plurality of data entities of a second type each of which represents a respective crossing at which one of the linearly extending geographic features represented by one of the plurality of data entities of the first type crosses over another of the linearly extending geographic features represented by another of the plurality of data entities of the first type at a higher altitude.

Claims

1. A method of displaying a crossing of at least two linearly extending geographic features that cross at different elevations on a computer display device of a computer based navigation system that uses a geographic database stored on a computer readable medium wherein said geographic database comprises:

a plurality of parcels, each containing a plurality of polyline data entities each of which represents a linearly extending geographic feature located within a geographic area;

and further contained in each of said plurality of parcels that contains polyline data entities that represent linearly extending geographic features that cross each other at different elevations is a separate overlay data entity that represents each overpass portion of each linearly extending geographic feature that crosses over another linearly extending geographic feature at a higher elevation;

the method comprising the steps of;

determining a selected portion of the geographic area to display on said computer display device;

locating which of the plurality of parcels contains the polyline data entities corresponding to said selected portion of the geographic area;

rendering the linearly extending geographic features represented by said polyline data entities contained in said parcel corresponding to said selected portion of the geographic area on said computer display device;

rendering the portion of each geographic feature represented by each overlay data entity contained in said parcel corresponding to said selected portion of the geographic area over said rendered geographic features represented by said polyline data entities on said computer display device,

whereby the displaying of the overlay data entity over the polyline data entities depicts which of said linearly extending geographic features has the higher elevation where linearly extending geographic features cross each other at different elevations.

2. The method of claim 1 wherein said overlay data entity is represented using data attributes of the corresponding portion of said polyline data entity representing said one of said at least two crossing physical geographic features which crosses at the highest elevation.

3. A method of reproducing a crossing of at least two physical geographic features that cross at different elevations on a computer display device comprising the steps of:

reading a plurality of data entities of a first type representing at least two individual geographic features that cross each other at different elevations from a computer readable medium in the order in which they are physically located on said computer readable medium;

rendering images of said at least two individual geographic features which cross each other at different elevations on said computer display device using said plurality of data entities of said first type;

reading from said computer readable medium a data entity of a second type that represents an overpass portion of the geographic feature of a higher elevation of said at least two individual geographic features that cross each other at different elevations, said data entity of said second type physically located after said plurality of data entities of said first type on said computer readable medium; and

rendering said overpass portion represented by said data entity of said second type on said computer display device,

whereby displaying the data entity of the second type over the data entities of the first type depicts the overpass portion of the one of said geographic features that has the higher elevation.

4. A method for displaying images of portions of a geographic region on a computer display, wherein the images portray at least two linearly extending geographic features one of which crosses another at a higher altitude, said method comprising the steps of:

reading from a computer-readable database stored on a computer-readable medium a first selected subset of a first plurality of data entities, wherein each of said first plurality of data entities represents a respective one of a plurality of linearly extending geographic features;

rendering on said computer display images of the linearly extending geographic features represented by said first selected subset of said first plurality of data entities;

reading from said computer-readable medium a second selected subset of a second plurality of data entities, wherein said second plurality of data entities represents linearly extending portions of said plurality of linearly extending geographic features that cross over other linearly extending geographic features at a higher altitude; and

rendering on said computer display images of said portions of geographic features represented by said second selected subset of said second plurality of data entities,

whereby the rendering of the second selected subset of said second plurality of data entities over the first selected subset of said first plurality of data entities depicts which of said rendered linearly extending geographic features has the higher altitude where linearly extending geographic features cross each other at different altitudes.

5. A method of storing representations of overpasses, wherein each overpass is a portion of one linearly extending geographic feature that passes over another linearly extending geographic feature at a higher altitude, said method comprising the steps of:

storing in a computer-readable database, a first plurality of data entities, each of which represents a respective one of a plurality of linearly extending geographic features; and

storing in said computer-readable database, a second plurality of data entities

wherein each of said second plurality of data entities represents a separate linearly extending portion of a linearly extending feature represented by one of said first plurality of data entities, and

wherein the linearly extending portion of a linearly extending feature represented by each of the second plurality of data entities crosses over at a higher altitude another linearly extending feature represented by another of said first plurality of data entities.

6. A method of producing a geographic database comprising the steps of:

identifying locations at which linearly extending features in a geographic region cross other linearly extending features at different elevations;

storing data entities of a first type in said geographic database to represent said linearly extending geographic features; and

storing data entities of a second type in said geographic database to represent linearly extending portions of the linearly extending geographic features that cross over other linearly extending features at said identified locations

whereby displaying the linearly extending portions represented by the data entities of the second type over the linearly extending geographic features represented by the data entities of the first type depicts which of said linearly extending geographic features have higher altitudes at said locations at which one linearly extending geographic feature crosses another at a higher elevation.

7. The method of claim 6 wherein each of said data entities of said second type is stored in said geographic database in a known order relative to the data entities of said first type the crossings of which are represented thereby.

8. The method of claim 6 further comprising the step of:

dividing a collection of data from which said data entities of said first type are formed into a plurality of parcels; and

storing each of the data entities of said second type in the same parcel as the data entities of said first type which represent the linearly extending geographic features the crossings of which are represented by the data entities of said second type.

9. A computer-readable medium having computer-readable data embodied thereon for representing geographic features in a geographic region and displaying said geographic features on a display device, comprising:

data entities of a first type and data entities of a second type,

wherein said data entities of said first type and said data entities of said second type are embodied on said medium,

wherein each of said data entities of said first type represents a respective linearly extending geographic feature located in said geographic region,

wherein each of said data entities of said second type represents a linearly extending portion of a respective corresponding linearly extending geographic feature represented by a data entity of said first type, and

wherein the linearly extending portion represented by a data entity of said second type represents a portion of the corresponding linearly extending geographic feature that crosses over at a higher altitude at least one other linearly extending geographic feature represented by another data entity of said first type,

whereby the displaying of the data entities of the second type over the data entities of the first type depicts which of said linearly extending geographic features has the higher altitude where linearly extending geographic features cross each other.

10. The invention of claim 9 wherein each one of said data entities of said second type includes a reference to the data entity of said first type that represents the linearly extending feature of which the portion represented by the data entity of said second type is a part.

11. The invention of claim 9 wherein each data entity of said second type includes data that represents two locations along the geographic feature represented by the corresponding data entity of said first type.

12. The invention of claim 11 wherein said two locations represent an extent of the crossing represented by the data entity of said second type.

13. The invention of claim 9 wherein each data entity of said second type includes data that references the one data entity of said first type that represents the geographic feature having a highest altitude of any of the geographic features represented by any of the data entities of said first type at a location of the crossing represented by the respective one of the data entity of said second type.

14. The invention of claim 9 wherein each data entity of said second type includes data that references an icon representing a crossing type.

15. The invention of claim 9 wherein each data entity of said second type is consistently ordered on said medium relative to all the data entities of the first type that represent linearly extending geographic features that cross each other at the crossing represented by said one of the of data entities of the second type.

16. The invention of claim 9 wherein each of the data entities of said second type is stored on said medium after the data entities of the first type that represent linearly extending geographic features that cross each other at the crossing represented by said one of the data entities of the second type.

17. The invention of claim 9 wherein said data entities of said first type and said data entities of said second type are organized on said medium in a plurality of parcels, such that each parcel includes a separate subset of data entities of said first type and said data entities of said second type.

18. The invention of claim 17 wherein each one of said data entities of said second type is stored in the same parcel as the data entities of the first type that represent geographic features that cross each other at the crossing represented by the one of said data entities of said second type.

19. The invention of claim 18 wherein each one of said data entities of said second type is stored within the same parcel after the data entities of the first type that represent geographic features that cross each other at the crossing represented by the one of said data entities of said second type.

20. The invention of claim 9 wherein said data entities of said first type and said data entities of said second type are organized on said medium in a plurality of layers, such that each layer includes a separate level of detail of geographic features in said geographic region.

21. The invention of claim 20 wherein higher layers of said plurality of layers provide less detail by omitting features having a lower ranking than a ranking assigned to features in said higher layers.

22. The invention of claim 20 wherein said data entities of said first type and said data entities of said second type of each of said plurality of layers are organized on said medium in a plurality of parcels, such that each parcel includes a separate subset of said data entities of said first type and said data entities of said second type.