Method and system for representation and use of shape information in geographic databases

• US 6,029,173 A
• Filed: 11/26/1997
• Issued: 02/22/2000
• Est. Priority Date: 11/26/1997
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Lampert, David S., Meek, James A., Ashby, Richard A.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): MILLS, JOHN G
• Application Number:
  US08/979,211
• Time in Patent Office: 818 Days
• Field of Search: 707/1-204
• US Class Current: 707/696
• CPC Class Codes: G01C 21/3819 Road shape data, e.g. outline of a route
• CPC Class Codes: G01C 21/3852 Data derived from aerial or satellite images
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: Y10S 707/92 Navigation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A system and method for storing data in a computer-readable database to represent curved geographic features. The database can be used in a navigation system. A computable function is used to define a curved line that represents the curved geographic feature. The computable function may be a polynomial equation whose shape is defined by its coefficients. In one embodiment, the polynomial equation is a type of spline curve, in particular a Bezier curve whose shape is defined by control points. The coefficients of the polynomial equation are associated with data representing the curved geographic feature. In the case in which the polynomial equation is a Bezier curve, the control points for generating the Bezier curve are associated with the data representing the curved geographic feature. These control points are stored in the database and are used in displaying the curved geographic feature. Use of a computable function to represent curved geographic features and storing parameters to be used by the computable function has the potential for significantly reducing the storage requirements for representing curved geographic features in a database. According to a further aspect, data identifying the normalized control points are stored in a data array and references into the data array are associated with data representing the curved geographic features, thereby enabling curved geographic features to be represented in space efficient manner.

Claims

1. A method of displaying physical geographic features on a computer output device using a geographic database stored on a computer readable medium for use in a computer based navigation system wherein said geographic database comprises:

an indexed normalized shape array, said indexed normalized shape array comprising a plurality of entries, each of said plurality of entries comprising one or more polynomial equation coefficients and an index reference value;

a plurality of road segment data entities, each of said plurality of road segment data entities comprised of shape data attributes and node data attributes wherein said shape data attributes contain a representation of a physical geographic feature in the form of an index reference value corresponding to an entry in said indexed normalized shape array and further wherein said node data attributes represent geographic location points;

the method comprising the steps of;

determining the selected geographic feature to display on said computer output device;

locating the corresponding road segment data entity and the associated shape data and node data attributes to said selected geographic feature;

reading the index reference value stored in said shape data attributes of said road segment data entity;

indexing into said normalized shape array using said index reference value and reading the polynomial equation coefficients from the corresponding entry;

calculating a polynomial curve based on geographic location information contained in said node data attributes and said polynomial equation coefficients; and

displaying said polynomial curve on said computer output device.

2. The invention of claim 1 wherein said polynomial equation coefficients are Bezier control points.

3. The invention of claim 1 wherein said polynomial curve is a Bezier curve.

4. The invention of claim 1 further comprising the step of:

re-scaling and re-orienting said polynomial equation coefficients based upon said geographic location information contained in said node data attributes.

5. A method of converting a first geographic database that represents curved geographic features using shape point data to a second geographic database that represents curved geographic features using a computable function, wherein the shape point data represents curved geographic features in the first geographic database by specifying geographic coordinates of locations along the curved geographic features between end points thereof, the method comprising the steps of:

for each curved geographic feature represented in the first geographic database using shape point data, determining coefficients of the computable function that approximate a curved line through the specified geographic coordinates of locations along the curved geographic feature used to represent the shape of the curved geographic feature in the first database;

normalizing the coefficients determined for each curved geographic feature relative to the end points of the curved geographic feature being represented;

forming a table that includes as entries said normalized coefficients for the curved geographic features for which coefficients were determined; and

for each curved geographic feature represented in the first geographic database, replacing the shape point data including the specified geographic coordinates of each location along the curved geographic feature between the end points thereof with a reference to an entry in the table that includes the coefficients by which a curve that approximates the shape of the curved geographic feature can be approximated using the computable function, thereby forming said second geographic database.

6. A computer-readable medium product for use in a navigation system, said computer-readable medium product having stored thereon the second geographic database including data representing physical features having other-than-straight shapes, and produced in accordance with the method of claim 5.

7. A method of reproducing images of physical geographic features on a computer display device associated with a computer based navigation system using the second geographic database produced in accordance with the method of claim 5, wherein said method of reproducing comprises:

identifying a data entity to be used to render a representation of a geographic feature to display on said computer display device;

executing a subprogram to calculate an other-than-straight shape from said coefficients; and

displaying said other-than-straight geographic feature on said computer output device using said other-than-straight shape.

8. A method for storing data that represents physical other-than-straight geographic features in a computer readable database for use in a computer based navigation system, the method comprising the steps of:

calculating coefficients of a polynomial equation that represents a physical other-than-straight geographic feature wherein said coefficients of said polynomial equation are normalized relative to points along said other-than-straight geographic feature;

associating said coefficients with data that represents said physical other-than-straight geographic feature; and

storing said coefficients and said data that represents said physical other-than-straight geographic feature in said database on a computer readable medium.

9. The method of claim 8 wherein said polynomial equation is of the spline curve family.

10. The method of claim 8 wherein said polynomial equation is of the Bezier curve subset of the cubic spline subfamily.

11. The method of claim 8 wherein said normalized coefficients of said polynomial equation are stored as a line shape in a normalized shape array.

12. The method of claim 11 wherein said line shape is in the form of a control point position pair.

13. A computer-readable medium product for use in a navigation system, said computer-readable medium product having stored thereon a geographic database comprising data representing physical features having other-than-straight shapes, and produced in accordance with the method of claim 8.

14. A method of reproducing physical geographic features on a computer display device associated with a computer based navigation system using a geographic database produced in accordance with the method of claim 8, wherein said method of reproducing comprises:

identifying a data entity to be used to render a representation of a geographic feature to display on said computer display device;

executing a subprogram to calculate an other-than-straight shape from said coefficients; and

displaying said other-than-straight geographic feature on said computer output device using said other-than-straight shape.