Method for applying clothoid curve values to roadways in a geographic data information system

• US 7,912,879 B2
• Filed: 02/15/2008
• Issued: 03/22/2011
• Est. Priority Date: 12/04/2007
• Status: Active Grant

• Current Assignee: Tomtom Global Content B.V (TomTom NV)
• Original Assignee: Tele Atlas North America (TomTom NV)
• Inventors: Witmer, James Alan
• Primary Examiner(s): Vital; Pierre M
• Assistant Examiner(s): Vo; Truong V
• Application Number:
  US12/032,538
• Publication Number:
  US 20090144331A1
• Time in Patent Office: 1,131 Days
• Field of Search: 707/831, 703/2
• US Class Current: 707/831
• CPC Class Codes: G01C 21/3819 Road shape data, e.g. outline of a route
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps

Abstract

Embodiments of the invention are methods for applying clothoid curve values to roadways in a geographic data information system. One embodiment is a method, comprising: selecting database segments in the geographic data information system, wherein the database segments describe roadways; determining segment chains from the selected database segments; preparing the segment chains for transition to curvature space; transitioning to a curvature function in the curvature space, by computing heading change at points along the segment chain, resulting in a transformation of the segment chains into clothoids; smoothing the curvature function; fitting the smoothed curvature function with a more generalized form which remains within a selected tolerance of the smoothed curvature function; and storing identified segments of straight lines, transition zones, and segments of constant curvature in the geographic data information system.

Claims

1. A method for applying clothoid curve values to roadways in a geographic data information system, comprising:

selecting database segments in the geographic data information system, wherein the database segments describe roadways;

determining segment chains from the selected database segments, wherein determining the segment chains comprises;

identifying a plurality of at grade junctions of the selected segments and all dead ends of the selected segments as important locations; and

finding each geographic chain of segments that traverse from any such important location, and touch no other such important location, until reaching the same or other such important location;

preparing the segment chains for transition to curvature space;

transitioning to a curvature function in the curvature space, by computing heading change at points along the segment chains, resulting in a transformation of the segment chains into clothoids;

smoothing the curvature function;

fitting the smoothed curvature function with a more generalized form which remains within a selected tolerance of the smoothed curvature function; and

storing parametric values of the smoothed curvature function for the segment chains in the geographic data information system;

wherein the more generalized form of the smoothed curvature function is obtained by recursively applying a regression technique to said smoothed curvature function and seaming together the resulting plurality of regression-fit functions into a piecewise linear function, said seaming being achieved by assigning a common value to the more generalized form of the smoothed curvature function at the point where successive regression-fit functions are seamed together.

2. The method of claim 1, wherein preparing the segment chains for transition to curvature space further comprises finding corner interfaces.

3. The method of claim 2, wherein finding corner interfaces incorporates shape generalization to remove nearly collinear shape points.

4. The method of claim 2, wherein finding corner interfaces comprises:

using relative accuracy information to approximate a line attached to a curve defined by three successive shape points.

5. The method of claim 2, wherein preparing the segment chains for transition to curvature space further comprises:

generalization of shape points that have not been identified as part of a corner interface.

6. The method of claim 1, wherein preparing the segment chains for transition to curvature space comprises:

determination of each segment chain'"'"'s geographic context.

7. The method of claim 1, wherein smoothing the curvature function comprises Gaussian smoothing.

8. The method of claim 1, wherein smoothing the curvature function comprises:

an approximation to Gaussian smoothing with a piecewise linear function connecting Gaussian sample points placed at intervals from shape points.

9. The method of claim 8, wherein the approximation to Gaussian smoothing is obtained from iterative samples stored in a table that associates Gaussian intervals with numeric parameters.

10. The method of claim 1, wherein the regression-fit functions are weighted least squares regression fit functions.

11. The method of claim 10, wherein fitting the smoothed curvature function further comprises:

applying a search for acceptable straight line substitutions to the piecewise linear fit function.