Journal Home > Volume 6 , Issue 4
Computational Visual Media 2020, 6(4): 417-430 https://doi.org/10.1007/s41095-020-0186-4
Research Article | Open Access | Issue | Published: 17 October 2020

Computing knots by quadratic and cubic polynomial curves

Show Author's Information Fan Zhang1,2( ),  Jinjiang Li1,2,  Peiqiang Liu1,2,  Hui Fan1,2
School of Computer Science and Technology, Shandong Technology and Business University, Yantai 264005, China
Co-Innovation Center of Shandong Colleges andUniversities: Future Intelligent Computing, Yantai 264005, China
Keywords:
knot, interpolation, polynomial curve, affine invariant
Cite this article:
Zhang F, Li J, Liu P, et al. Computing knots by quadratic and cubic polynomial curves. Computational Visual Media, 2020, 6(4): 417-430. https://doi.org/10.1007/s41095-020-0186-4
Download citation
EndNote(RIS)
BibTeX

733

Views

65

Downloads

Citations

6

Crossref

N/A

WoS

5

Scopus

2

CSCD

Abstract Full text About this article

A new method is presented to determine parameter values (knot) for data points for curve and surface generation. With four adjacent data points, a quadratic polynomial curve can be determined uniquely if the four points form a convex polygon. When the four data points do not form a convex polygon, a cubic polynomial curve with one degree of freedom is used to interpolate the four points, so that the interpolant has better shape, approximating the polygon formed by the four data points. The degree of freedom is determined by minimizing the cubic coefficient of the cubic polynomial curve. The advantages of the new method are, firstly, the knots computed have quadratic polynomial precision, i.e., if the data points are sampled from a quadratic polynomial curve, and the knots are used to construct a quadratic polynomial, it reproduces the original quadratic curve. Secondly, the new method is affine invariant, which is significant, as most parameterization methods do not have this property. Thirdly, it computes knots using a local method. Experiments show that curves constructed using knots computed by the new method have better interpolation precision than for existing methods.


menu
Abstract
Full text
Outline
About this article

Computing knots by quadratic and cubic polynomial curves

Show Author's information Fan Zhang1,2( ), Jinjiang Li1,2, Peiqiang Liu1,2, Hui Fan1,2
School of Computer Science and Technology, Shandong Technology and Business University, Yantai 264005, China
Co-Innovation Center of Shandong Colleges andUniversities: Future Intelligent Computing, Yantai 264005, China

Abstract

A new method is presented to determine parameter values (knot) for data points for curve and surface generation. With four adjacent data points, a quadratic polynomial curve can be determined uniquely if the four points form a convex polygon. When the four data points do not form a convex polygon, a cubic polynomial curve with one degree of freedom is used to interpolate the four points, so that the interpolant has better shape, approximating the polygon formed by the four data points. The degree of freedom is determined by minimizing the cubic coefficient of the cubic polynomial curve. The advantages of the new method are, firstly, the knots computed have quadratic polynomial precision, i.e., if the data points are sampled from a quadratic polynomial curve, and the knots are used to construct a quadratic polynomial, it reproduces the original quadratic curve. Secondly, the new method is affine invariant, which is significant, as most parameterization methods do not have this property. Thirdly, it computes knots using a local method. Experiments show that curves constructed using knots computed by the new method have better interpolation precision than for existing methods.

Keywords: knot, interpolation, polynomial curve, affine invariant

References(31)

[1]
J. H. Ahlberg,; E. Nilson,; J. L. Walsh, The Theory of Splines and Their Applications. Academic Press, 1967.
[2]
C. D. Boor, A Practical Guide to Splines. Springer-Verlag New York, 1978.
[3]
K. W. Brodlie, A review of methods for curve and function drawing. In: Mathematical Methods in Computer Graphics and Design. London: Academic Press, 33-37, 1980.
[4]
I. D. Faux,; M. J. Pratt, Computational Geometry for Design and Manufacture. Halsted Press, 1979.
[5]
B. Q. Su,; D. Y. Liu, Computational Geometry: Curve and Surface Modeling. Academic Press, 1989.
[6]
W. S. Li,; S. H. Xu,; J. M. Zheng,; G. Zhao, Target curvature driven fairing algorithm for planar cubic B-spline curves. Computer Aided Geometric Design Vol. 21, No. 5, 499-513, 2004.
DOI Google Scholar
[7]
W. Lü, Curves with chord length parameterization. Computer Aided Geometric Design Vol. 26, No. 3, 342-350, 2009.
DOI Google Scholar
[8]
G. Farin, Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide. Academic Press, 1988.
DOI
[9]
E. T. Y. Lee, Choosing nodes in parametric curve interpolation. Computer-Aided Design Vol. 21, No. 6, 363-370, 1989.
DOI Google Scholar
[10]
S. Y. Jeong,; Y. J. Choi,; P. Park, Parametric interpolation using sampled data. Computer-Aided Design Vol. 38, No. 1, 39-47, 2006.
DOI Google Scholar
[11]
C. Yuksel,; S. Schaefer,; J. Keyser, Parameterization and applications of Catmull-Rom curves. Computer-Aided Design Vol. 43, No. 7, 747-755, 2011.
DOI Google Scholar
[12]
J. J. Fang,; C. L. Hung, An improved parameterization method for B-spline curve and surface interpolation. Computer-Aided Design Vol. 45, No. 6, 1005-1028, 2013.
DOI Google Scholar
[13]
C. G. Lim, A universal parametrization in B-spline curve and surface interpolation. Computer Aided Geometric Design Vol. 16, No. 5, 407-422, 1999.
DOI Google Scholar
[14]
C. M. Zhang,; F. H. F. Cheng,; K. T. Miura, A method for determining knots in parametric curve interpolation. Computer Aided Geometric Design Vol. 15, No. 4, 399-416, 1998.
DOI Google Scholar
[15]
C. M. Zhang,; W. P. Wang,; J. Y. Wang,; X. M. Li, Local computation of curve interpolation knots with quadratic precision. Computer-Aided Design Vol. 45, No. 4, 853-859, 2013.
DOI Google Scholar
[16]
P. J. Hartley,; C. J. Judd, Parametrization and shape of B-spline curves for CAD. Computer-Aided Design Vol. 12, No. 5, 235-238, 1980.
DOI Google Scholar
[17]
S. P. Marin, An approach to data parametrization in parametric cubic spline interpolation problems. Journal of Approximation Theory Vol. 41, No. 1, 64-86, 1984.
DOI Google Scholar
[18]
X. M. Li,; F. Zhang,; G. N. Chen,; C. M. Zhang, Formula for computing knots with minimum stress and stretching energies. Science China Information Sciences Vol. 61, No. 5, Article No. 052104, 2017.
DOI Google Scholar
[19]
F. M. Lin,; L. Y. Shen,; C. M. Yuan,; Z. P. Mi, Certified space curve fitting and trajectory planning for CNC machining with cubic B-splines. Computer-Aided Design Vol. 106, 13-29, 2019.
DOI Google Scholar
[20]
Z. Y. Yang,; L. Y. Shen,; C. M. Yuan,; X. S. Gao, Curve fitting and optimal interpolation for CNC machining under confined error using quadratic B-splines. Computer-Aided Design Vol. 66, 62-72, 2015.
DOI Google Scholar
[21]
M. S. Floater,; M. Reimers, Meshless parameterization and surface reconstruction. Computer Aided Geometric Design Vol. 18, No. 2, 77-92, 2001.
DOI Google Scholar
[22]
C. Gotsman,; X. F. Gu,; A. Sheffer, Fundamentals of spherical parameterization for 3D meshes. In: Proceedings of the ACM SIGGRAPH 2003 Papers, 358-363, 2003.
DOI
[23]
X. F. Gu,; S. T. Yau, Global conformal surface parameterization. In: Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, 127-137, 2003.
[24]
H. Xie,; H. Qin, A novel optimization approach to the effective computation of NURBS knots. International Journal of Shape Modeling Vol. 7, No. 2, 199-227, 2001.
DOI Google Scholar
[25]
G. Farin, Rational quadratic circles are parametrized by chord length. Computer Aided Geometric Design Vol. 23, No. 9, 722-724, 2006.
DOI Google Scholar
[26]
B. Bastl,; B. Jüttler,; M. Lávička,; J. Schicho,; Z. Šír, Spherical quadratic Bézier triangles with chord length parameterization and tripolar coordinates in space. Computer Aided Geometric Design Vol. 28, No. 2, 127-134, 2011.
DOI Google Scholar
[27]
B. Bastl,; B. Jüttler,; M. Lávička,; Z. Šír, Curves and surfaces with rational chord length parameterization. Computer Aided Geometric Design Vol. 29, No. 5, 231-241, 2012.
DOI Google Scholar
[28]
S. Tsuchie,; K. Okamoto, High-quality quadratic curve fitting for scanned data of styling design. Computer-Aided Design Vol. 71, 39-50, 2016.
DOI Google Scholar
[29]
X. L. Han, A class of general quartic spline curves with shape parameters. Computer Aided Geometric Design Vol. 28, No. 3, 151-163, 2011.
DOI Google Scholar
[30]
U. Bashir,; M. Abbas,; J. M. Ali, The G2 and C2 rational quadratic trigonometric Bézier curve with two shape parameters with applications. Applied Mathematics and Computation Vol. 219, No. 20, 10183-10197, 2013.
DOI Google Scholar
[31]
M. Antonelli,; C. V. Beccari,; G. Casciola, High quality local interpolation by composite parametric surfaces. Computer Aided Geometric Design Vol. 46, 103-124, 2016.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 30 March 2020
Accepted: 17 June 2020
Published: 17 October 2020
Issue date: December 2020

Copyright

© The Author(s) 2020.

Acknowledgements

This work was supported in part by the following: National Natural Science Foundation of China under Grant Nos. 61602277 and 61772319, Natural Science Foundation of Shandong Province under Grant Nos. ZR2016FQ12 and ZR2018BF009, Key Research and Development Program of Yantai City under Grant No. 2017ZH065, CERNET Innovation Project under Grant No. NGII20161204, and Science and Technology Innovation Program for Distributed Young Talents of Shandong Province Higher Education Institutions under Grant No. 2019KJN042.

Rights and permissions

This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduc-tion in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made.

The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript, please go to https://www.editorialmanager.com/cvmj.

Return