Method and apparatus for creating a clothoid road geometry

• US 10,060,749 B2
• Filed: 02/19/2015
• Issued: 08/28/2018
• Est. Priority Date: 02/19/2015
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Dorum, Ole Henry
• Primary Examiner(s): Khatib, Rami
• Assistant Examiner(s): Wiltey, Nicholas K
• Application Number:
  US14/625,722
• Publication Number:
  US 20160245657A1
• Time in Patent Office: 1,286 Days
• Field of Search: None
• CPC Class Codes: G01C 21/3819 Road shape data, e.g. outline of a route
• CPC Class Codes: G01C 21/3881 Tile-based structures

Abstract

A method, apparatus and computer program product are provided in order to create a clothoid road geometry. In the context of a method, a link geometry representative of a portion of a road network is converted into a plurality of link splines. The method also includes converting the plurality of link splines into respective sequences of one or more clothoids based upon curvature profiles of the link splines.

Claims

1. A method comprising:

converting a link geometry representative of a portion of a road network into a plurality of link splines comprising piecewise polynomial functions, wherein the link geometry comprises a plurality of links and is stored by a database, and wherein converting the link geometry into the plurality of link splines comprises defining a plurality of partially overlapping link chains with each link chain comprised of a plurality of links, converting each link chain into a respective link spline and aligning respective ends of the link splines corresponding to overlapping link chains;

converting the plurality of link splines into respective sequences of one or more clothoids based upon curvature profiles of the link splines, wherein converting the plurality of link splines into respective sequences of one or more clothoids comprises, for each link spline, determining a plurality of break-point locations along a respective link spline dependent upon a curvature profile of the link spline comprising an ordered array of [curvature κ

, arc length s] value pairs by identifying one or more zero-crossings to define one or more respective break-point locations, approximating a section between neighboring zero-sections with a polyline, and converting one or more sections of the respective link spline to respective clothoids; and

using the respective sequences of one or more clothoids by a map display or to support an advanced driver assistance system (ADAS).

2. The method according to claim 1, wherein converting one or more sections of the respective link spline to respective clothoids comprises:

for a section of the respective link spline having a start break-point and an end break-point, determining coordinates of the link spline at the start break-point and the end break-point;

determining tangent headings of the of the link spline at the start break-point and the end break-point; and

determining the respective clothoid based upon the coordinates and the tangent headings of the link spline at the start break-point and the end break-point.

3. The method according to claim 1, wherein converting one or more sections of the respective link spline to respective clothoids comprises:

for a section of the respective link spline having a start break-point and an end break-point, determining coordinates of the link spline at the start break-point and the end break-point;

determining curvatures of the of the link spline at the start break-point and the end break-point; and

determining the respective clothoid based upon the coordinates and the curvatures of the link spline at the start break-point and the end break-point.

4. The method according to claim 1, further comprising:

determining the curvature profile defining a curvature of the respective link spline at a respective arc length; and

wherein approximating a section between neighboring zero-sections comprises approximating the curvature profile of a curve comprised of a plurality of curve sections with a plurality of polylines with each polyline approximating the curvature profile of a respective curve section, wherein determining the plurality of break-point locations comprises determining the break-point locations based upon vertices identified at intersections of adjacent polylines and zero-crossings of the plurality of polylines.

5. The method according to claim 1, wherein each link chain is representative of one or more road segments having a same road type attribute.

6. The method according to claim 1, further comprising:

subdividing the link geometry comprising a plurality of links into a plurality of tiles; and

aligning respective ends of the link splines that meet at a boundary of a tile.

7. An apparatus embodied by a map and positioning engine (MPE) or an advanced driver assistance system (ADAS), the apparatus comprising at least one processor and at least one memory including computer program code, the at least one memory and computer program code configured to, with the processor, cause the apparatus to at least:

convert a link geometry representative of a portion of a road network into a plurality of link splines comprising piecewise polynomial functions, wherein the link geometry comprises a plurality of links and is stored by a database, and wherein the apparatus is caused to convert the link geometry into the plurality of link splines by defining a plurality of partially overlapping link chains with each link chain comprised of a plurality of links, converting each link chain into a respective link spline and aligning respective ends of the link splines corresponding to overlapping link chains; and

convert the plurality of link splines into respective sequences of one or more clothoids based upon curvature profiles of the link splines, wherein the apparatus is caused to convert the plurality of link splines into respective sequences of one or more clothoids by, for each link spline, determining a plurality of break-point locations along a respective link spline dependent upon a curvature profile of the link spline comprising an ordered array of [curvature κ

, arc length s] value pairs by identifying one or more zero-crossings to define one or more respective break-point locations, approximating a section between neighboring zero-sections with a polyline, and converting one or more sections of the respective link spline to respective clothoids.

8. The apparatus according to claim 7, wherein the at least one memory and computer program code are configured to, with the processor, cause the apparatus to convert one or more sections of the respective link spline to respective clothoids by:

for a section of the respective link spline having a start break-point and an end break-point, determining coordinates of the link spline at the start break-point and the end break-point;

determining tangent headings of the of the link spline at the start break-point and the end break-point; and

determining the respective clothoid based upon the coordinates and the tangent headings of the link spline at the start break-point and the end break-point.

9. The apparatus according to claim 7, wherein the at least one memory and computer program code are configured to, with the processor, cause the apparatus to convert one or more sections of the respective link spline to respective clothoids by:

for a section of the respective link spline having a start break-point and an end break-point, determining coordinates of the link spline at the start break-point and the end break-point;

determining curvatures of the of the link spline at the start break-point and the end break-point; and

determining the respective clothoid based upon the coordinates and the curvatures of the link spline at the start break-point and the end break-point.

10. The apparatus according to claim 7, wherein the at least one memory and computer program code are further configured to, with the processor, cause the apparatus to:

determine the curvature profile defining a curvature of the respective link spline at a respective arc length; and

wherein the apparatus is caused to approximate a section between neighboring zero-sections by approximating the curvature profile of a curve comprised of a plurality of curve sections with a plurality of polylines with each polyline approximating the curvature profile of a respective curve section, wherein the at least one memory and computer program code are configured to, with the processor, cause the apparatus to determine the plurality of break-point locations by determining the break-point locations based upon vertices identified at intersections of adjacent polylines and zero-crossings of the plurality of polylines.

11. The apparatus according to claim 7, wherein each link chain is representative of one or more road segments having a same road type attribute.

12. The apparatus according to claim 7, wherein the at least one memory and computer program code are further configured to, with the processor, cause the apparatus to:

subdivide the link geometry comprising a plurality of links into a plurality of tiles; and

align respective ends of the link splines that meet at a boundary of a tile.

13. A computer program product embodied by a map and positioning engine (MPE) or an advanced driver assistance system (ADAS), the computer program product comprising at least one non-transitory computer-readable storage medium having computer-executable program code portions stored therein, the computer-executable program code portions comprising program code instructions configured to:

convert a link geometry representative of a portion of a road network into a plurality of link splines comprising piecewise polynomial functions, wherein the link geometry comprises a plurality of links and is stored by a database, and wherein the link geometry is converted into the plurality of link splines by defining a plurality of partially overlapping link chains with each link chain comprised of a plurality of links, converting each link chain into a respective link spline and aligning respective ends of the link splines corresponding to overlapping link chains; and

convert the plurality of link splines into respective sequences of one or more clothoids based upon curvature profiles of the link splines, wherein the plurality of link splines are converted into respective sequences of one or more clothoids by, for each link spline, determining a plurality of break-point locations along a respective link spline dependent upon a curvature profile of the link spline comprising an ordered array of [curvature κ

, arc length s] value pairs by identifying one or more zero-crossings to define one or more respective break-point locations, approximating a section between neighboring zero-sections with a polyline, and converting one or more sections of the respective link spline to respective clothoids.

14. The computer program product according to claim 13, wherein the program code instructions configured to convert one or more sections of the respective link spline to respective clothoids comprise program code instructions configured to:

for a section of the respective link spline having a start break-point and an end break-point, determine coordinates of the link spline at the start break-point and the end break-point;

determine tangent headings of the of the link spline at the start break-point and the end break-point; and

determine the respective clothoid based upon the coordinates and the tangent headings of the link spline at the start break-point and the end break-point.

15. The computer program product according to claim 13, wherein the program code instructions configured to convert one or more sections of the respective link spline to respective clothoids comprise program code instructions configured to:

for a section of the respective link spline having a start break-point and an end break-point, determine coordinates of the link spline at the start break-point and the end break-point;

determine curvatures of the of the link spline at the start break-point and the end break-point; and

determine the respective clothoid based upon the coordinates and the curvatures of the link spline at the start break-point and the end break-point.

16. The computer program product according to claim 13, wherein the computer-executable program code portions further comprise program code instructions configured to:

determine the curvature profile defining a curvature of the respective link spline at a respective arc length; and

wherein the program code instructions configured to approximate a section between neighboring zero-sections comprise program code instructions configured to approximate the curvature profile of a curve comprised of a plurality of curve sections with a plurality of polylines with each polyline approximating the curvature profile of a respective curve section, wherein the program code instructions configured to determine the plurality of break-point locations comprise program code instructions configured to determine the break-point locations based upon vertices identified at intersections of adjacent polylines and zero-crossings of the plurality of polylines.

17. The computer program product according to claim 13, wherein each link chain is representative of one or more road segments having a same road type attribute.