Method and system for representation of geographical features in a computer-based system

• US 7,805,442 B1
• Filed: 12/05/2000
• Issued: 09/28/2010
• Est. Priority Date: 12/05/2000
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq North America LLC (Nokia Corporation)
• Inventors: Dorum, Ole Henry, Israni, Vijaya, Joshi, Rajashri
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): Chojnacki; Mellissa M
• Application Number:
  US09/729,939
• Time in Patent Office: 3,584 Days
• Field of Search: 345/419, 345/423, 345/606, 364/449, 364/459, 395/120, 395/133, 395/141, 395/142, 434/112, 434/116, 434/365, 702 27- 28, 702/32, 702/179, 702/157, 702/150, 707 1- 10, 707/100, 707/104.1, 707/736, 701/201, 701213-215
• US Class Current: 707/736
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

Cartographic data is represented using polynomial splines. To improve representation accuracy and reduce storage requirements, a database storing data points (shape points and nodes) is converted into a database of spline control points. The spline control points are computed by fitting a polynomial spline to the geographic features using a least squares approximation. The control points associated with each geographic feature are stored in a computer-usable database. The geographic features can be displayed by computing the spline functions using the stored control points.

Claims

1. A method for representing geographic features in a computer-based system, comprising:

providing a first computer-usable database storing a plurality of data points specifying latitude and longitude coordinates of locations along at least one geographic feature;

fitting a polynomial spline to the at least one geographic feature by applying a least squares approximation to the data points specifying latitude and longitude coordinates to generate a plurality of control points for the polynomial spline; and

storing the control points in a second computer-usable database, the control points being usable for representing the geometry of the at least one geographic feature in the computer-based system.

2. The method of claim 1, wherein the data points are selected from the group consisting of coordinate pairs and coordinate triples.

3. The method of claim 1, further comprising:

configuring the number of control points.

4. The method of claim 1, wherein the polynomial spline is selected from the group consisting of uniform nonrational B-spline, non-uniform nonrational B-spline, uniform Catmull-Rom spline, nonuniform Catmull-Rom spline, and NURBS.

5. The method of claim 1, further comprising:

defining a knot sequence for the polynomial spline.

6. The method of claim 5, further comprising:

manually defining the knot sequence.

7. The method of claim 5, further comprising:

storing the knot sequence in the second computer-usable database.

8. The method of claim 1, further comprising:

incorporating in the least squares approximation a bearing value associated with a node included in the plurality of data points.

9. The method of claim 1, further comprising:

weighting a node included in the plurality of data points in the least squares approximation.

10. The method of claim 1, further comprising:

employing regularization in computing the least squares approximation.

11. The method of claim 1, further comprising:

identifying a straight section of the at least one geographic feature; and

storing in the second computer-usable database the data points corresponding to the straight section.

12. The method of claim 11, further comprising:

computing the control points only for one or more curved sections of the at least one geographic feature.

13. The method of claim 11, further comprising:

computing the control points such that the tangent to the spline approximation of a curved section of the at least one geographic feature and the tangent to the straight section are equal at the point at which the curved and straight section meet.

36. The method of claim 1, wherein the geographic feature is a road.

37. The method of claim 1, wherein the data points further specifying altitude.

14. A method of displaying on a computer output device a function representing a geographic feature, comprising:

retrieving from a computer-usable database a plurality of spline control points associated with the geographic feature, the spline control points being derived, using a least squares approximation, from a plurality of data points specifying latitude and longitude coordinates of locations along the geographic feature;

calculating a polynomial spline using the spline control points to generate the function representing the geometry of the geographic feature; and

displaying the function on the computer output device.

15. The method of claim 14, wherein the polynomial spline is selected from the group consisting of uniform nonrational B-spline, non-uniform nonrational B-spline, uniform Catmull-Rom spline, nonuniform Catmull-Rom spline, and NURBS.

16. A method of generating a computer-usable database that represents feature geometry using a plurality of spline control points associated with a plurality of geographic features, comprising:

providing a predetermined database that represents feature geometry using a plurality of data points specifying latitude and longitude coordinates of locations along the geographic features;

for each of the geographic features, retrieving a corresponding set of data points specifying latitude and longitude coordinates from the predetermined database;

fitting a polynomial spline to each of the geographic features by computing a plurality of control points yielding the least squares approximation to the corresponding set of data points specifying latitude and longitude coordinates; and

storing the plurality of spline control points in the computer-usable database.

17. The method of claim 16, further comprising:

identifying a straight section of a geographic feature based on the data points; and

storing in the computer-usable database the data points corresponding to the straight section of the geographic feature.

18. The method of claim 17, further comprising:

computing the control points only for one or more curved sections of the geographic feature.

19. The method of claim 17, further comprising:

computing the control points for a geographic feature that has a curved section and an adjoining straight section such that a bearing value at an endpoint of the curved section equals a corresponding bearing value at an endpoint of the straight section that meets the curved section.

20. The method of claim 16, further comprising:

incorporating in the least squares approximation a bearing value associated with a node included in the plurality of data points.

21. The method of claim 16, further comprising:

weighting a node included in the plurality of data points.

22. The method of claim 16, further comprising:

employing regularization in the least squares approximation.

23. A system for displaying a function representing the geometry of a geographic feature, comprising:

a database storing one or more spline control points associated with the geographic feature, the spline control points being derived, using a least squares approximation, from a plurality of data points specifying latitude and longitude coordinates of locations along the geographic feature;

a processor configured to compute a polynomial spline using the spline control points to generate the function representing the geometry of the geographic feature; and

a display device for displaying the polyline.

24. The system of claim 23, wherein the spline control points are derived by incorporating in the least squares approximation a bearing value associated with a node included in the plurality of data points.

25. The system of claim 23, wherein the spline control points are derived using the least squares approximation by weighting a node included in the plurality of data points.

26. The system of claim 23, wherein the spline control points are derived by employing regularization in the least squares approximation.

27. The system of claim 23, wherein the processor is configured to determine whether the geographic feature includes a straight section, and if so, linearly interpolate the data points representing the straight section.

28. The system of claim 23, wherein the polynomial spline is selected from the group consisting of uniform nonrational B-spline, nonuniform nonrational B-spline, uniform Catmull-Rom spline, nonuniform Catmull-Rom spline and NURBS.

29. A system for generating a plurality of spline control points that represent feature geometry, comprising:

a fast computer-usable database for storing a plurality of data points specifying latitude and longitude coordinates of locations along at least one geographic feature;

a processor configured to apply a least squares approximation to the data points specifying latitude and longitude coordinates to generate the plurality of control points for a polynomial spline; and

a second computer-usable database for storing the control points.

30. The system of claim 29, wherein the processor is configured to incorporate in the least squares approximation a bearing value associated with a node included in the plurality of data points.

31. The system of claim 29, wherein the processor is configured to weight a node included in the plurality of data points in the least squares approximation.

32. The system of claim 29, wherein the processor is configured to employ regularization in computing the least squares approximation.

33. The system of claim 29, wherein the processor is configured to determine whether the at least one geographic feature has a substantially straight section, and if so, to store in the second computer-usable database the data points corresponding to the straight section.

34. The system of claim 33, wherein the processor computes the control points only for one or more curved sections of the at least one geographic feature.

35. The system of claim 29, wherein the polynomial spline is selected from the group consisting of a uniform nonrational B-spline, nonuniform nonrational B-spline uniform Catmull-Rom spline, nonuniform Catmull-Rom spline, and NURBS.