Method and system for representation and use of shape information in geographic databases
First Claim
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.
5 Assignments
0 Petitions
Accused Products
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.
-
Citations
14 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. - View Dependent Claims (2, 3, 4)
-
-
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. - View Dependent Claims (6, 7)
-
-
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. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
Specification