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

• US 6,366,927 B1
• Filed: 12/13/1999
• Issued: 04/02/2002
• 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): Von Buhr, Maria N.
• Application Number:
  US09/460,454
• Time in Patent Office: 841 Days
• Field of Search: 707/100-104, 701/200-203, 701/208-212, 345/643-645, 345/441-443
• US Class Current: 1/1
• 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 to represent other-than-straight map features in a computer-readable geographic database for use in a navigation system. For geographic features that are other-than-straight, a curve generated by a computable function is fitted to an image of the other-than-straight map 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 other-than-straight 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 other-than-straight feature. These control points are stored in the geographic database and are used in displaying the other-than-straight geographic feature. Use of a computable function to generate other-than-straight geographic features and storing parameters to be used by the computable function has the potential for significantly reducing the storage requirements for representing other-than-straight features in a geographic database. According to a further aspect, normalized control point pairs are stored in a data structure and an index reference into the data structure is associated with data used to represent the other-than-straight geographic features, thereby resulting in further reduction in data storage requirements.

Claims

1. A geographic database embodied in a computer readable medium wherein the geographic database includes data representing curving geographic features, said geographic database comprising:

a table containing parameters of a computable function; and

a plurality of data entities that represent geographic features, wherein each of said data entities that represents a curving geographic feature includes

data representing positions of end points of the represented curving geographic feature, and

data representing a curving shape of said represented geographic feature between said end points thereof,

wherein said data representing said curving shape of said represented geographic feature comprises a reference to parameters in said table.

2. The geographic database of claim 1 wherein said computer readable medium is installed in a navigation system.

3. The geographic database of claim 1 wherein the computable function is a Bezier curve.

4. The geographic database of claim 1 wherein the computable function is a Bezier curve and the parameters represent control points.

5. The geographic database of claim 1 wherein the computable function is a polynomial function and the parameters represent coefficients of said polynomial function.

6. The geographic database of claim 1 wherein said plurality of data entities that represent geographic features represent roads.

7. The geographic database of claim 1 wherein said geographic features represented by said plurality of data entities comprise one of:

ponds, railroad tracks, buildings, airports, stadiums, parks, mountain ranges, docks, ferries, tunnels, and bridges.

8. The geographic database of claim 1 wherein said geographic features represented by said plurality of data entities have shapes in the form of one of:

lines and polygons.

9. The geographic database of claim 1 wherein said parameters in said table are normalized.

10. The geographic database of claim 1 wherein said parameters in said table are normalized relative to end points of the represented curving geographic feature being represented.

11. The geographic database of claim 1 wherein said parameters in said table are normalized relative to end points of the represented curving geographic feature being represented, wherein normalization includes one of scaling, rotating, and translating.

12. A computer program used with a geographic database, the computer program comprising:

first computer code means that accesses data representing other than straight geographic features in said geographic database, wherein said data representing other than straight geographic features includes normalized parameters that represent other than straight shapes of represented geographic features;

second computer code means for adjusting said normalized parameters by one of scaling, rotating, and translating; and

third computer code means for calculating a curve to represent said other than straight geographic features using said adjusted normalized parameters.

13. The computer program of claim 12 further comprising:

fourth computer code means for generating an image of said curve on a computer display.

14. The computer program of claim 12 further comprising:

fourth computer code means for determining a position of a vehicle wherein geographic coordinates of said vehicle are matched to said curve.

15. The computer program of claim 12 wherein said first computer code means further comprises:

computer code means that accesses references in said data representing said other than straight geographic features and then uses said references to access said normalized parameters from a table stored with said geographic database.

16. The computer program of claim 12 wherein said normalized parameters are normalized relative to end points of the other than straight geographic features associated therewith.

17. The computer program of claim 12 wherein said other than straight geographic features include roads.

18. The invention of claim 12 wherein said normalized parameters represent Bezier curve control points and wherein said third computer code means calculates a Bezier curve using said Bezier curve control points.

19. A data arrangement used in a geographic database stored on a computer readable medium and used to represent curved geographic features, the data arrangement comprising:

a table containing a plurality of entries, wherein each entry in said table includes coefficients that define a shape between two points using a computable function, and wherein said coefficients are normalized relative to said two points; and

a plurality of data entities that represent separate portions of linearly extending geographic features,

wherein each of said plurality of data entities includes data identifying end points of that separate portion of a linearly extending geographic feature represented thereby,

and wherein each data entity of said plurality of data entities that represents a portion of a linearly extending geographic feature that is curved includes a reference to an entry in said table, wherein said referenced entry contains parameters that define the shape of the portion of the linearly extending geographic feature represented thereby using the computable function when the two points to which the parameters in the referenced entry are normalized with respect to the end points identified by the data entity from which the reference was made.

20. The invention of claim 19 wherein said computable function is a Bezier curve.