COMPUTER READABLE STORAGE MEDIUM STORING INSTRUCTIONS FOR APPLYING CLOTHOID CURVE VALUES TO ROADWAYS IN A GEOGRAPHIC DATA INFORMATION SYSTEM

• US 20090144030A1
• Filed: 02/15/2008
• Published: 06/04/2009
• Est. Priority Date: 12/04/2007
• Status: Abandoned Application

• Current Assignee: Tele Atlas North America (TomTom NV)
• Original Assignee: Tele Atlas North America (TomTom NV)
• Inventors: Witmer, James Alan
• Application Number:
  US12/032,540
• Publication Number:
  US 20090144030A1
• Time in Patent Office: Days
• US Class Current: 703/1
• 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 include a computer readable storage medium storing instructions for applying clothoid curve values to roadways in a geographic data information system. One embodiment is a computer readable storage medium, storing instructions executable by a processor for applying clothoid curve values to roadways in a geographic data information system, the instructions 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 computer readable storage medium, storing instructions executable by a processor for applying clothoid curve values to roadways in a geographic data information system, the instructions 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 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 the identified segments of straight lines, transition zones, and segments of constant curvature in the geographic data information system.

2. The computer readable storage medium of claim 1, 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 important location, and touch no other important location, until reaching the same or other important location.

3. The computer readable storage medium of claim 1, wherein preparing the segment chains for transition to curvature space further comprises finding corner interfaces.

4. The computer readable storage medium of claim 3, wherein finding corner interfaces incorporates shape generalization to remove nearly collinear shape points.

5. The computer readable storage medium of claim 3, wherein finding corner interfaces comprises:

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

6. The computer readable storage medium of claim 3, 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.

7. The computer readable storage medium of claim 1, wherein preparing the segment chains for transition to curvature space comprises:

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

8. The computer readable storage medium of claim 1, wherein smoothing the curvature function comprises Gaussian smoothing.

9. The computer readable storage medium 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.

10. The computer readable storage medium of claim 9, wherein the approximation to Gaussian smoothing is obtained from iterative samples stored in a table that associates Gaussian intervals with numeric parameters.

11. The computer readable storage medium of claim 1, wherein fitting the smoothed curvature function is performed by seaming together a plurality of weighted least squares regression fit functions into a piecewise linear function.

12. The computer readable storage medium of claim 11, wherein fitting the smoothed curvature function further comprises:

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

13. The computer readable storage medium of claim 12, wherein the search for acceptable straight line substitutions to the piecewise linear fit function further comprises:

generating a straight line function value that generates no change in overall function area

14. The computer readable storage medium of claim 12, wherein fitting the smoothed curvature function further comprises:

applying a search for straight lines and singular points in the piecewise linear fit function which can be acceptably replaced with a value of zero.

15. The computer readable storage medium of claim 1, wherein the database segments comprise roadways in x,y positions.

16. The computer readable storage medium of claim 15, wherein the database segments further comprise non-roadway features.

17. The computer readable storage medium of claim 1, wherein the database segments comprise roadways in x,y,z positions.

18. The computer readable storage medium of claim 1, further comprising:

resulting in parameters of curvature gradients as clothoids mapped to transition zones.

19. The computer readable storage medium of claim 1, further comprising:

resulting in parameters of curvature mapped into segments of constant curvature.

20. The computer readable storage medium of claim 1, further comprising:

wherein parameters of curvature are used to compute safe speed parameters.

21. The computer readable storage medium of claim 1, further comprising:

wherein parameters of curvature are compared with an ideal maneuver.

22. The computer readable storage medium of claim 1, further comprising:

scoring a driver'"'"'s performance relative to an optimum driving technique.

23. The computer readable storage medium of claim 1, further comprising:

approximating roadbed shaping design from shaped geographic line segments.

24. The computer readable storage medium of claim 23, wherein the roadbed design is composed of straight lines, circular arcs, and clothoidal sections.

25. The computer readable storage medium of claim 23, wherein the process for roadbed design approximation consists of a first step of determining straight line edge interfaces at the beginning of curve sections.

26. The computer readable storage medium of claim 1, further comprising:

determining roadbed design parameters from x, y positions and roadbed design principles.