US6029173A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for representation and use of shape information in geographic databases
Assignee: Here Global BV
•
Filing: 1997-11-26
•
Granted: 2000-02-22
•
Expires: 2017-11-26
Abstract
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.
Inventors
- 👤 James A. Meek
- 👤 Richard A. Ashby
- 👤 David S. Lampert
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 03:32
CPC Classifications
G; G01; G01C; G01C21/00; G01C21/38; G01C21/3863; G01C21/3867; G01C21/3804; G01C21/3807; G01C21/3815; G01C21/3819; G01C21/3833; G01C21/3852; Y; Y10; Y10S; Y10S707/00; Y10S707/912; Y10S707/918; Y10S707/919; Y10S707/92; Y10S707/99941; Y10S707/99943; Y10S707/99944; Y10S707/99945; Y10S707/99948
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
242 words
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.
Claim 2
Independent Claim
242 words
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.
Claim 3
Dependent Claim
14 words
The invention of claim 1 wherein said polynomial equation coefficients are Bezier control points.
Claim 4
Dependent Claim
13 words
The invention of claim 1 wherein said polynomial curve is a Bezier curve.
Claim 5
Dependent Claim
29 words
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.
Claim 6
Independent Claim
233 words
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.
Claim 7
Independent Claim
233 words
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.
Claim 8
Dependent Claim
39 words
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.
Claim 9
Dependent Claim
89 words
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.
Claim 10
Independent Claim
94 words
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.
Claim 11
Independent Claim
94 words
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.
Claim 12
Dependent Claim
15 words
The method of claim 8 wherein said polynomial equation is of the spline curve family.
Claim 13
Dependent Claim
20 words
The method of claim 8 wherein said polynomial equation is of the Bezier curve subset of the cubic spline subfamily.
Claim 14
Dependent Claim
24 words
The method of claim 8 wherein said normalized coefficients of said polynomial equation are stored as a line shape in a normalized shape array.
Claim 15
Dependent Claim
19 words
The method of claim 11 wherein said line shape is in the form of a control point position pair.
Claim 16
Dependent Claim
38 words
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.
Claim 17
Dependent Claim
86 words
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.
References Cited (Backward Citations)
EP0394517A1
Cited
US5438517A
Cited
US5497451A
Cited
US5470233A
Cited
WO1995032483A1
Cited
US5566288A
Cited
EP0807803A2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-02-21 | 2003-08-23 | 2004-02-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-02-21 | 2007-08-23 | 2008-02-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-02-21 | 2011-08-23 | 2012-02-22 | $7700.00 | Window Closed / Lapsed |