Application of the ψ-s curve to road geometry extraction and modeling

• US 7,152,022 B1
• Filed: 04/25/2002
• Issued: 12/19/2006
• Est. Priority Date: 04/25/2002
• Status: Expired due to Fees

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq North America LLC (Nokia Corporation)
• Inventors: Joshi, Rajashri
• Primary Examiner(s): Rodriguez, Paul
• Assistant Examiner(s): GUILL, RUSSELL L
• Application Number:
  US10/131,955
• Time in Patent Office: 1,699 Days
• Field of Search: 703/2, 701/208
• US Class Current: 703/2
• 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
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves

Abstract

A method for determining the line segments, circular arcs, and clothoidal arcs that form a complex curve along a length thereof is disclosed. A ψ-s curve of the complex curve is determined, which is a plot of tangent angles, wherein the angle is made with a fixed line by a tangent to the complex curve along the length thereof. The straight line portions and parabolic portions of the plot of the ψ-s curve are determined and used to determine the corresponding circular arcs and straight lines that form the complex curve and clothoidal arcs that form the complex curve, respectively. The ψ-s curve can be used to identify the curves and straight lines that define the geometry of roads and therefore can be used to store data that indicate the geometry of roads in a geographic database that contains data representing the roads.

Claims

1. A method of determining straight line segments, circular arcs and clothoidal arcs that form a complex curve comprising:

providing data indicating a shape of the complex curve along a length thereof;

forming a transform of the shape by determining an angle made with a fixed line by a tangent to the shape along the length thereof to provide a plurality of tangent angles;

forming a plot of the tangent angles along the length of the complex curve against the length along the complex curve;

determining straight lines that fit said plot;

using said straight lines that fit said plot to determine at least one of the line segments and circular arcs that form the shape of the complex curve along the length thereof; and

representing said complex curve in a geographic database by storing, in said geographic database, data that indicate the at least one of the line segments and circular arcs that form the shape of the complex curve along the length thereof.

2. The method of claim 1 wherein the complex curve represents a road segment.

3. The method of claim 1 further comprising:

determining parabolic arcs, if any, that fit said plot; and

using said parabolic arcs that fit said plot to determine clothoidal arcs that form the shape of the complex curve along the length thereof.

4. A method of representing geometry of a road segment in a geographic database comprising:

providing data indicating a shape of the road segment along a length thereof;

forming a transform of the shape by determining an angle made with a fixed line by a tangent to the shape at each point along the length to provide a plurality of tangent angles;

forming a plot of the tangent angles at each point along the length of the road segment against the length along the road segment;

determining straight lines that correspond to said plot;

using the straight lines that correspond to the plot to determine at least one of line segments and circular arcs that form the shape of the road segment along the length thereof; and

representing said road segment in the geographic database by storing, in said geographic database, data that indicate the line segments and circular arcs that form the shape of the road segment along the length thereof.

5. The method of claim 4 wherein the data indicating a shape of the road segment along a length thereof are obtained by extracting from photographs or maps.

6. The method of claim 4 wherein the data indicating a shape of the road segment along a length thereof are obtained using a positioning system located in a vehicle that travels along the road segment.

7. The method of claim 6 wherein said vehicle is a mobile mapping vehicle.

8. The method of claim 4 further comprising:

determining parabolic arcs, if any, that fit said plot; and

using said parabolic arcs that fit said plot to determine clothoidal arcs that form the shape of the road segment along the length thereof.

9. The method of claim 8 further comprising:

representing said road segment in the geographic database by storing, in said geographic database, data that indicate the clothoidal arcs that form the shape of the road segment along the length thereof.

10. The method of claim 9 further comprising:

determining a value of the curvature at locations along the length of the road segment using the data that indicate the line segments, circular arcs and clothoidal arcs that form the shape of the road segment along the length thereof.

11. A computer-readable medium having a geographic database formed according to process comprising:

providing data indicating a shape of a road segment along a length thereof;

forming a transform of the shape by determining an angle made with a fixed line by a tangent to the shape at each point along the length to provide a plurality of tangent angles;

forming a plot of the tangent angles at each point along the length of the road segment against the length along the road segment;

determining straight lines that correspond to said plot;

using the straight lines that correspond to the plot to determine at least one of line segments and circular arcs that form the shape of the road segment along the length thereof; and

representing said road segment in the geographic database by storing, in said geographic database, a data structure that indicates the line segments and circular arcs that form the shape of the road segment along the length thereof.

12. A process for forming a geographic database comprising:

obtaining data that represent a shape of a road;

plotting a curve that corresponds to the shape of the road;

determining a ψ

-s transform of the curve, wherein the ψ

-s transform is a plot of a tangent angle, wherein the angle of the tangent angle is made with a fixed line by a tangent to the curve along a length thereof;

determining straight line portions of the ψ

-s transform;

using the straight line portions of the ψ

-s transform to determine at least one corresponding straight lines and circular arcs that approximate the curve that corresponds to the shape of the road; and

storing data that indicate the straight lines and circular arcs that approximate the curve that corresponds to the shape of the road in order to represent the road.

13. The method of claim 12 wherein said data that represent the shape of the road are obtained by digitizing photographs or maps.

14. The method of claim 12 wherein said data that represent the shape of the road are obtained using a positioning system located in a vehicle that travels along the road.

15. The method of claim 14 wherein said vehicle is a mobile mapping vehicle.

16. The method of claim 12 further comprising:

determining parabolic arcs, if any, that fit said plot; and

using said parabolic arcs that fit said plot to determine clothoidal arcs that form the shape of the road along the length thereof.

17. The method of claim 16 wherein said data that indicate the straight lines, circular arcs and clothoidal arcs that approximate the curve that corresponds to the shape of the road are stored in the geographic database to represent said road.

18. The method of claim 17 further comprising:

determining a value of the curvature at locations along the length of the road using the data that indicate the straight lines, circular arcs and clothoidal arcs that approximate the curve that corresponds to the shape of the road; and

storing data indicating said value in said geographic database.

19. A computer-readable medium having a geographic database formed according to process comprising:

obtaining data that represent a shape of a road;

plotting a curve that corresponds to the shape of the road;

determining a ψ

-s transform of the curve, wherein the ψ

-s transform is plot of a tangent angle, wherein the angle of the tangent angle is made with a fixed line by a tangent to the curve along a length thereof;

determining straight line portions of the ψ

-s transform;

using the straight line portions of the ψ

-s transform to determine at least one corresponding straight lines and circular arcs that approximate the curve that corresponds to the shape of the road; and

storing a data structure that indicates the straight lines and circular arcs that approximate the curve that corresponds to the shape of the road in order to represent the road.

20. A method comprising:

providing data indicating a shape of a complex curve along a length thereof;

forming a transform of the shape by determining an angle made with a fixed line by a tangent to the shape along the length thereof to provide a plurality of tangent angles;

forming a plot of the tangent angles along the length of the complex curve against the length along the complex curve;

determining at least one geometrical shape that fit said plot;

using said at least one geometrical shape to determine at least one of a line, a circular arc and a clothoidal arc that form the shape of the complex curve along the length thereof; and

storing data that indicate the at least one of a line, a circular arc and a clothoidal arc that form the shape of the complex curve along the length thereof.

21. The method of claim 20, therein the at least one geometrical shape comprises any one or more selected from a group of a zero slope line that indicates the line, a nonzero slope line that indicates the circular arc, and a parabolic arc that indicates the clothoidal arc.

22. The method of claim 20, wherein the complex curve represents a road segment in a geographic database.

23. The method of claim 22, wherein the data indicating a shape of the road segment along a length thereof are obtained by any one or more selected from a group of extracting from photographs, extracting from maps, and using a positioning system located in a vehicle that travels along the road segment.

24. The method of claim 23, wherein the vehicle is a mobile mapping vehicle.

25. The method of claim 23 further comprising:

determining a value of the curvature at locations along the length of the complex curve using the data that indicate the line, the circular arc, and the clothoidal arc that form the shape of the complex curve along the length thereof.

26. The method of claim 20 further comprising:

representing the complex curve in a geographic database.

27. A computer-readable medium having computer-executable instructions for performing the steps of:

providing data indicating a shape of a complex curve along a length thereof;

forming a transform of the shape by determining an angle made with a fixed line by a tangent to the shape along the length thereof to provide a plurality of tangent angles;

forming a plot of the tangent angles along the length of the complex curve against the length along the complex curve;

determining at least one geometrical shape that fit said plot; and

using said at least one geometrical shape to determine at least one of a line, a circular arc and a clothoidal arc that form the shape of the complex curve along the length thereof; and

storing data that indicate at least one of a line, a circular arc and a clothoidal arc that form the shape of the complex curve along the length thereof.