research-article

Clothoid fitting and geometric Hermite subdivision

Authors:

Andreas WeinmannAuthors Info & Claims

Advances in Computational Mathematics, Volume 47, Issue 4

https://doi.org/10.1007/s10444-021-09876-5

Published: 01 August 2021 Publication History

Abstract

We consider geometric Hermite subdivision for planar curves, i.e., iteratively refining an input polygon with additional tangent or normal vector information sitting in the vertices. The building block for the (nonlinear) subdivision schemes we propose is based on clothoidal averaging, i.e., averaging w.r.t. locally interpolating clothoids, which are curves of linear curvature. To this end, we derive a new strategy to approximate Hermite interpolating clothoids. We employ the proposed approach to define the geometric Hermite analogues of the well-known Lane-Riesenfeld and four-point schemes. We present numerical results produced by the proposed schemes and discuss their features.

References

[1]

Aspert N, Ebrahimi T, and Vandergheynst P Non-linear subdivision using local spherical coordinates Computer Aided Geometric Design 2003 20 3 165-187

[2]

Alia, C., Gilles, T., Reine, T., Ali, C.: Local trajectory planning and tracking of autonomous vehicles, using clothoid tentacles method. In: 2015 IEEE Intelligent Vehicles Symposium (IV), pp 674–679. IEEE (2015)

[3]

Baass KG The use of clothoid templates in highway design Transportation Forum 1984 1 47-52

[4]

Birkhoff, G., de Boor, C.: Nonlinear splines. In: Proc. General Motors Symp. of 1964, pp 164–190 (1965)

[5]

Berkemeier, M.: Clothoid segments for optimal switching between arcs during low-speed Ackerman path tracking with rate-limited steering. In: 2015 American Control Conference (ACC), pp 501–506. IEEE (2015)

[6]

Bertolazzi E and Frego M G1 fitting with clothoids Mathematical Methods in the Applied Sciences 2015 38 5 881-897

[7]

Bertolazzi E and Frego M Interpolating clothoid splines with curvature continuity Mathematical Methods in the Applied Sciences 2018 41 4 1723-1737

[8]

Budianto B and Lun DPK Inpainting for fringe projection profilometry based on geometrically guided iterative regularization IEEE Trans. Image Process. 2015 24 12 5531-5542

[9]

Baran, I., Lehtinen, J., Popović, J.: Sketching clothoid splines using shortest paths. In: Computer Graphics Forum, vol. 29, pp 655–664. Wiley Online Library (2010)

[10]

Biral F, Lot R, Rota S, Fontana M, and Huth V Intersection support system for powered two-wheeled vehicles: Threat assessment based on a receding horizon approach IEEE Trans. Intell. Transp. Syst. 2012 13 2 805-816

[11]

Cavaretta, A., Dahmen, W., Micchelli, C.: Stationary subdivision, volume 453 American Mathematical Soc. (1991)

[12]

Cohen A, Dyn N, and Matei B Quasilinear subdivision schemes with applications to ENO interpolation Appl. Comput. Harmon. Anal. 2003 15 2 89-116

[13]

Cashman T, Hormann K, and Reif U Generalized Lane–Riesenfeld algorithms Computer Aided Geometric Design 2013 30 4 398-409

[14]

Chalmoviansky P and Jüttler B A non-linear circle-preserving subdivision scheme Adv. Comput. Math. 2007 27 4 375-400

[15]

Coope I Curve interpolation with nonlinear spiral splines IMA J. Numer. Anal. 1993 13 3 327-341

[16]

Dyn N, Floater M, and Hormann K Four-point curve subdivision based on iterated chordal and centripetal parameterizations Computer Aided Geometric Design 2009 26 3 279-286

[17]

Dyn N and Hormann K Geometric conditions for tangent continuity of interpolatory planar subdivision curves Computer Aided Geometric Design 2012 29 6 332-347

[18]

Dyn N and Levin D Subdivision schemes in geometric modelling Acta Numerica 2002 11 73-144

[19]

Donoho D and Yu T Nonlinear pyramid transforms based on median-interpolation SIAM J. Math. Anal. 2000 31 5 1030-1061

[20]

Ewald T, Reif U, and Sabin M Hölder regularity of geometric subdivision schemes Constr. Approx. 2015 42 3 425-458

[21]

Grohs P A general proximity analysis of nonlinear subdivision schemes SIAM J. Math. Anal. 2010 42 2 729-750

[22]

Goldman R, Vouga E, and Schaefer S On the smoothness of real-valued functions generated by subdivision schemes using nonlinear binary averaging Computer Aided Geometric Design 2009 26 231-242

[23]

Han, B: Framelets and wavelets: Algorithms, analysis, and applications. Springer (2018)

[24]

Havemann S, Edelsbrunner J, Wagner P, and Fellner D Curvature-controlled curve editing using piecewise clothoid curves Computers & Graphics 2013 37 6 764-773

[25]

Hoschek, J., Lasser, D.: Grundlagen der geometrischen Datenverarbeitung Teubner (1992)

[26]

Kuijt F and Van Damme R Shape preserving interpolatory subdivision schemes for nonuniform data Journal of Approximation Theory 2002 114 1 1-32

[27]

Kimia B, Frankel I, and Popescu A Euler spiral for shape completion Int. J. Comput. Vis. 2003 54 1-3 159-182

[28]

Lipovetsky E and Dyn N A weighted binary average of point-normal pairs with application to subdivision schemes Computer Aided Geometric Design 2016 48 36-48

[29]

Marinov, M., Dyn, N., Levin, D.: Geometrically controlled 4-point interpolatory schemes. In: Advances in multiresolution for geometric modelling, pp 301–315. Springer (2005)

[30]

Mehlum, E.: Nonlinear splines. In: Computer Aided Geometric Design, pp 173–207. Elsevier (1974)

[31]

Moosmüller C C1 Analysis of Hermite subdivision schemes on manifolds SIAM J. Numer. Anal. 2016 54 5 3003-3031

[32]

McCrae J and Singh K Sketching piecewise clothoid curves Computers & Graphics 2009 33 4 452-461

[33]

Meek D and Walton D Offset curves of clothoidal splines Comput. Aided Des. 1990 22 4 199-201

[34]

Meek D and Walton D Clothoid spline transition spirals Math. Comput. 1992 59 199 117-133

[35]

Meek D and Walton D An arc spline approximation to a clothoid J. Comput. Appl. Math. 2004 170 1 59-77

[36]

Meek D and Walton D A two-point G1 Hermite interpolating family of spirals J. Comput. Appl. Math. 2009 223 1 97-113

[37]

Peters, J., Reif, U.: Subdivision surfaces. Springer (2008)

[38]

Rump, S.M.: INTLAB - INTerval LABoratory. In: Csendes, T. (ed.) Developments in Reliable Computing. http://www.ti3.tuhh.de/rump/, pp 77–104. Kluwer Academic Publishers, Dordrecht (1999)

[39]

Sabin, M., Dodgson, N.: A circle-preserving variant of the four-point subdivision scheme. Mathematical Methods for Curves and Surfaces: Tromsø, pp 275–286 (2004)

[40]

Schneider, R., Kobbelt, L.: Discrete fairing of curves and surfaces based on linear curvature distribution. In: Curve and Surface Design, Saint-Malo 1999, Innovations in Applied Mathematics, pp. 371–380 (2000)

[41]

Stoer J Curve fitting with clothoidal splines J. Res. Nat. Bur. Standards 1982 87 4 317-346

[42]

Wallner J and Dyn N Convergence and C1 analysis of subdivision schemes on manifolds by proximity Computer Aided Geometric Design 2005 22 7 593-622

[43]

Weinmann A Nonlinear subdivision schemes on irregular meshes Constr. Approx. 2010 31 3 395-415

[44]

Walton D and Meek D G1 interpolation with a single Cornu spiral segment J. Comput. Appl. Math. 2009 223 1 86-96

[45]

Xie G and Yu T Smoothness equivalence properties of general manifold-valued data subdivision schemes Multiscale Modeling & Simulation 2009 7 3 1073-1100

Cited By

Levien RUguray A(2024)GPU-friendly Stroke ExpansionProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36753907:3(1-29)Online publication date: 9-Aug-2024
https://dl.acm.org/doi/10.1145/3675390
Hofit BNira DNir S(2023)Geometric Hermite interpolation in by refinementsAdvances in Computational Mathematics10.1007/s10444-023-10037-z49:3Online publication date: 9-Jun-2023
https://dl.acm.org/doi/10.1007/s10444-023-10037-z

Index Terms

Clothoid fitting and geometric Hermite subdivision

Index terms have been assigned to the content through auto-classification.

Recommendations

A two-point G1 Hermite interpolating family of spirals

A one-parameter family of spirals that can match planar, two-point G^1 Hermite data is presented. These spirals can be used as an alternative to the biarc, which is also a one-parameter family of curves that can match two-point G^1 Hermite data. Some ...
G2 curve design with a pair of Pythagorean Hodograph quintic spiral segments

When designing curves, it is often desirable to join two points, at which G^2 Hermite data are given, by a low degree parametric polynomial curve which has no extraneous curvature extrema. Such curves are referred to as being fair. The join can be ...
On parametrization of interpolating curves

In parametric curve interpolation there is given a sequence of data points and corresponding parameter values (nodes), and we want to find a parametric curve that passes through data points at the associated parameter values. We consider those ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Advances in Computational Mathematics

Advances in Computational Mathematics Volume 47, Issue 4

Aug 2021

336 pages

ISSN:1019-7168

Issue’s Table of Contents

© The Author(s) 2021.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 August 2021

Accepted: 27 May 2021

Received: 14 April 2020

Author Tags

Author Tags

Qualifiers

Research-article

Funding Sources

Hochschule Darmstadt University of Applied Sciences (3312)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Levien RUguray A(2024)GPU-friendly Stroke ExpansionProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36753907:3(1-29)Online publication date: 9-Aug-2024
https://dl.acm.org/doi/10.1145/3675390
Hofit BNira DNir S(2023)Geometric Hermite interpolation in by refinementsAdvances in Computational Mathematics10.1007/s10444-023-10037-z49:3Online publication date: 9-Jun-2023
https://dl.acm.org/doi/10.1007/s10444-023-10037-z

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents