Method and system for representation of geographical features in a computer-based system
View Patent ↗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.
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.
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.
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.