SCIENCE CHINA Information Sciences, Volume 61 , Issue 5 : 052104(2018) https://doi.org/10.1007/s11432-017-9134-6

Formula for computing knots with minimum stress and stretching energies

More info
  • ReceivedJan 9, 2017
  • AcceptedMay 10, 2017
  • PublishedSep 1, 2017


Computing knots for a given set of data points in a plane is one of the key steps in the construction of fitting curves with high precision. In this study, a new method is proposed for computing a parameter value (knot) for each data point. With only three adjacent consecutive data points, one may not determine a unique interpolation quadratic polynomial curve, which has one degree of freedom (a variable). To obtain a better curve, the stress and stretching energies are used to optimize this variable so that the quadratic polynomial curve has required properties, which ensure that when the three consecutive points are co-linear, the optimal quadratic polynomial curve constructed is the best. If the position of the mid-point of the three points lies between the first point and the third point, the quadratic polynomial curve becomes a linear polynomial curve. Minimizing the stress and stretching energies is a time-consuming task. To avoid the computation of energy minimization, a new model for simplifying the stress and stretching energies is presented. The new model is an explicit function and is used to compute the knots directly, which greatly reduces the amount of computation. The knots are computed by the new method with minimum stress and stretching energies in the sense that if the knots computed by the new method are used to construct quadratic polynomial, the quadratic polynomial constructed has the minimum stress and stretching energies. Experiments show that the curves constructed using the knots generated by the proposed method result in better interpolation precision than the curves constructed using the knots by the existing methods.


This work was supported by National Natural Science Foundation of China (Grant Nos. 61572292, 61373078), NSFC Joint Fund with Zhejiang Integration of Informatization and Industrialization under Key Project (Grant No. U1609218).


[1] Ahlberg J H, Nilson E N, Walsh J L. The Theory of Splines and Their Applications. New York: Academic Press, 1967. Google Scholar

[2] Boor C. A Practical Guide to Splines. Berlin: Springer, 1978. Google Scholar

[3] Brodie K W. A review of methods for curve and function drawing. In: Mathematical Methods in Computer Graphics and Design. London: Academic Press, 1980. 1--37. Google Scholar

[4] Faux I D, Pratt M J. Computational Geometry for Design and Manufacture. New York: Halsted Press, 1979. Google Scholar

[5] Su B Q, Liu D Y. Computational Geometry. Shanghai: Shang Hai Academic Press, 1982. Google Scholar

[6] Li W, Xu S, Zheng J. Target curvature driven fairing algorithm for planar cubic B-spline curves. Comput Aided Geometric Des, 2004, 21: 499-513 CrossRef Google Scholar

[7] Lü W. Curves with chord length parameterization. Comput Aided Geometric Des, 2009, 26: 342-350 CrossRef Google Scholar

[8] Farin G. Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide. London: Academic Press, 1990. Google Scholar

[9] Lee E T Y. Choosing nodes in parametric curve interpolation. Comput-Aided Des, 1989, 21: 363-370 CrossRef Google Scholar

[10] Jeong S Y, Choi Y J, Park P G. Parametric interpolation using sampled data. Comput-Aided Des, 2006, 38: 39-47 CrossRef Google Scholar

[11] Yuksel C, Schaefer S, Keyser J. Parameterization and applications of Catmull-Rom curves. Comput-Aided Des, 2011, 43: 747-755 CrossRef Google Scholar

[12] Fang J J, Hung C L. An improved parameterization method for B-spline curve and surface interpolation. Comput-Aided Des, 2013, 45: 1005-1028 CrossRef Google Scholar

[13] Caiming Zhang , Fuhua (Frank) Cheng , Miura K T. A method for determining knots in parametric curve interpolation. Comput Aided Geometric Des, 1998, 15: 399-416 CrossRef Google Scholar

[14] Zhang C, Wang W, Wang J. Local computation of curve interpolation knots with quadratic precision. Comput-Aided Des, 2013, 45: 853-859 CrossRef Google Scholar

[15] Hartley P J, Judd C J. Parametrization and shape of B-spline curves for CAD. Comput-Aided Des, 1980, 12: 235-238 CrossRef Google Scholar

[16] Marin S P. An approach to data parametrization in parametric cubic spline interpolation problems. J Approximation Theor, 1984, 41: 64-86 CrossRef Google Scholar

[17] Floater M S, Reimers M. Meshless parameterization and surface reconstruction. Comput Aided Geometric Des, 2001, 18: 77-92 CrossRef Google Scholar

[18] Gotsman C. Fundamentals of spherical parameterization for 3d meshes. Acm Trans Graph, 2003, 22: 28--29. Google Scholar

[19] Gu X, Yau S T. Global conformal surface parameterization. In: Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, Aachen, 2003. 127--137. Google Scholar

[20] Xie H, Qin H. A novel optimization approach to the effective computation of nurbs knots. Int J Shape Model, 2011, 7: 199--227. Google Scholar

[21] Bastl B, Jüttler B, Lávi?ka M. Spherical quadratic Bézier triangles with chord length parameterization and tripolar coordinates in space. Comput Aided Geometric Des, 2011, 28: 127-134 CrossRef Google Scholar

[22] Bastl B, Jüttler B, Lávi?ka M. Curves and surfaces with rational chord length parameterization. Comput Aided Geometric Des, 2012, 29: 231-241 CrossRef Google Scholar

[23] Tsuchie S, Okamoto K. High-quality quadratic curve fitting for scanned data of styling design. Comput-Aided Des, 2016, 71: 39-50 CrossRef Google Scholar

[24] Han X. A class of general quartic spline curves with shape parameters. Comput Aided Geometric Des, 2011, 28: 151-163 CrossRef Google Scholar

[25] Antonelli M, Beccari C V, Casciola G. High quality local interpolation by composite parametric surfaces. Comput Aided Geometric Des, 2016, 46: 103-124 CrossRef Google Scholar

  • Figure 1

    Three consecutive points.

  • Figure 2

    The plots of ${P_i}(s)$ for $s_{i}=i/10$, $i=2,3,\ldots,8$.

  • Figure 3

    Three co-linear points. (a) ${P'_i}(s)$ is a constant; (b) ${P'_i}(s_{i})$ = 0.

  • Figure 4

    $l_{j}$ and $\alpha_{k}$.

  • Figure 5

    The plot of the formula (21).

  • Figure 8

    Error curves by six methods. (a) 80$E_1(6,t)$ by M1; (b) 700$E_2(6,t)$ by M1; (c) 92$E_1(6,t)$ by M2; (d) 330$E_2(6,t)$ by M2; (e) 92$E_1(6,t)$ by M3; (f) 140$E_2(6,t)$ by M3; (g) 360$E_1(6,t)$ by M4; (h) 800$E_2(6,t)$ by M4; (i) 36$E_1(6,t)$ by M6;protectłinebreak (j) 600$E_2(6,t)$ by M6; (k) 396$E_1(6,t)$ by New; (l) 1000$E_2(6,t)$ by New.

  • Figure 9

    Modify a curve interactively.

  • Table 1   Maximum errors of $E_{1}(k,t)$ and $E_{2}(k,t)$ for $\lambda~=~0.15$
    $E_{1}(k,t)$ New M1 M2 M3 M4 M5 M6
    $k$=0 1.64E$-$3 series1.02E$-$3 5.95E$-$3 1.03E$-$2 1.11E$-$3 1.76E$-$2 8.96E$-$3
    $k$=1 1.78E$-$3 2.18E$-$3 7.67E$-$3 1.24E$-$2 series1.24E$-$3 2.09E$-$2 1.09E$-$2
    $k$=2 2.04E$-$3 3.49E$-$3 9.14E$-$3 1.40E$-$2 series1.75E$-$3 2.36E$-$2 1.23E$-$2
    $k$=3 2.39E$-$3 5.59E$-$3 1.03E$-$2 1.51E$-$2 series2.24E$-$3 2.58E$-$2 1.32E$-$2
    $k$=4 series2.70E$-$3 7.99E$-$3 1.14E$-$2 1.57E$-$2 2.71E$-$3 2.77E$-$2 1.36E$-$2
    $k$=5 series2.96E$-$3 1.07E$-$2 1.27E$-$2 1.58E$-$2 3.19E$-$3 2.93E$-$2 1.37E$-$2
    $k$=6 series3.19E$-$3 1.35E$-$2 1.42E$-$2 1.60E$-$2 3.63E$-$3 3.06E$-$2 1.50E$-$2
    $k$=7 series3.39E$-$3 1.73E$-$2 1.55E$-$2 1.76E$-$2 4.03E$-$3 3.17E$-$2 1.66E$-$2
    $k$=8 series3.58E$-$3 2.20E$-$2 1.66E$-$2 1.91E$-$2 4.41E$-$3 3.26E$-$2 1.82E$-$2
    $k$=9 series3.75E$-$3 2.71E$-$2 1.76E$-$2 2.04E$-$2 4.75E$-$3 3.34E$-$2 1.97E$-$2
    $k$=10 series3.93E$-$3 3.23E$-$2 1.84E$-$2 2.17E$-$2 5.08E$-$3 3.40E$-$2 2.10E$-$2
    $k$=11 series4.22E$-$3 3.76E$-$2 1.91E$-$2 2.28E$-$2 5.38E$-$3 3.45E$-$2 2.21E$-$2
    $k$=12 series4.71E$-$3 4.30E$-$2 1.97E$-$2 2.38E$-$2 5.66E$-$3 3.50E$-$2 2.30E$-$2
    $k$=13 series5.51E$-$3 4.83E$-$2 2.02E$-$2 2.46E$-$2 5.93E$-$3 3.54E$-$ 2 2.39E$-$2
    $E_{2}(k,t)$ New M1 M2 M3 M4 M5 M6
    $k$=1 4.18E$-$5 7.87E$-$5 2.24E$-$4 8.09E$-$4 series2.15E$-$5 1.26E$-$4 7.60E$-$4
    $k$=2 5.49E$-$5 1.01E$-$4 2.76E$-$4 8.83E$-$4 series4.64E$-$5 1.57E$-$4 8.32E$-$4
    $k$=3 7.69E$-$5 1.24E$-$4 3.31E$-$4 9.53E$-$4 series7.37E$-$5 1.78E$-$4 9.01E$-$4
    $k$=4 series1.03E$-$4 1.63E$-$4 3.88E$-$4 1.02E$-$3 1.06E$-$4 1.90E$-$4 9.64E$-$4
    $k$=5 series1.33E$-$4 2.06E$-$4 4.45E$-$4 1.07E$-$3 1.51E$-$4 2.30E$-$4 1.02E$-$3
    $k$=6 series1.67E$-$4 2.47E$-$4 4.99E$-$4 1.12E$-$3 1.85E$-$4 2.66E$-$4 1.06E$-$3
    $k$=7 2.05E$-$4 2.83E$-$4 5.49E$-$4 1.14E$-$3 series1.93E$-$4 2.97E$-$4 1.09E$-$3
    $k$=8 series2.45E$-$4 3.76E$-$4 5.90E$-$4 1.15E$-$3 2.49E$-$4 3.24E$-$4 1.10E$-$3
    $k$=9 series2.86E$-$4 4.92E$-$4 6.58E$-$4 1.12E$-$3 5.03E$-$4 3.46E$-$4 1.07E$-$3
    $k$=10 series3.33E$-$4 6.39E$-$4 7.23E$-$4 1.04E$-$3 4.18E$-$4 3.97E$-$4 1.01E$-$3
    $k$=11 series3.97E$-$4 9.32E$-$4 7.76E$-$4 9.93E$-$4 5.09E$-$4 4.70E$-$4 9.73E$-$4
    $k$=12 series4.50E$-$4 1.35E$-$3 8.06E$-$4 1.03E$-$3 5.78E$-$4 5.54E$-$4 1.02E$-$3
    $k$=13 6.19E$-$4 1.88E$-$3 7.97E$-$4 1.04E$-$3 series5.42E$-$4 6.48E$-$4 1.04E$-$3
    $k$=14 8.43E$-$4 2.50E$-$3 series7.23E$-$4 9.85E$-$4 8.13E$-$4 7.48E$-$4 9.79E$-$4
  • Table 2   Maximum-Minimum errors of $E_{1}(k,t)$ and $E_{2}(k,t)$
    $E_{1}(k,t)$ New M1 M2 M3 M4 M5 M6
    $\lambda=0.05$ 11 1 0 0 2 0 0
    $\lambda=0.10$ 12 1 0 0 1 0 0
    $\lambda=0.15$ 10 1 0 0 3 0 0
    $\lambda=0.20$ 7 1 0 0 6 0 0
    $\lambda=0.25$ 4 1 0 0 9 0 0
    Summary 44 5 0 0 21 0 0
    $E_{2}(k,t)$ New M1 M2 M3 M4 M5 M6
    $\lambda=0.05$ 8 0 2 0 4 0 0
    $\lambda=0.10$ 9 0 1 0 4 0 0
    $\lambda=0.15$ 8 0 1 0 5 0 0
    $\lambda=0.20$ 9 0 0 0 4 1 0
    $\lambda=0.25$ 10 0 0 0 4 0 0
    Summary 44 0 4 0 21 1 0
  • Table 3   Maximum errors of $E_{3}(t)$
    $E_{3}(t)$ New M1 M2 M3 M4 M5 M6
    $\lambda=0.05$ series3.75E$-$6 6.71E$-$6 6.23E$-$6 2.39E$-$5 5.38E$-$6 9.13E$-$6 3.60E$-$5
    $\lambda=0.10$ series3.82E$-$6 6.74E$-$6 5.87E$-$6 4.97E$-$5 4.83E$-$6 9.22E$-$6 6.05E$-$5
    $\lambda=0.15$ series3.88E$-$6 6.77E$-$6 9.06E$-$5 7.80E$-$5 4.29E$-$6 9.30E$-$6 8.74E$-$5
    $\lambda=0.20$ series3.94E$-$6 6.80E$-$6 1.31E$-$5 1.08E$-$4 4.55E$-$6 9.38E$-$6 1.17E$-$4
    $\lambda=0.25$ series4.00E$-$6 6.82E$-$6 1.78E$-$5 1.42E$-$4 4.91E$-$6 9.45E$-$6 1.49E$-$4
  • Table 4   Maximum-Minimum errors of $E_{l}(t)$, $l=3,4,5,6$
    $E_{l}(t)$ New M1 M2 M3 M4 M5 M6
    $\lambda=0.05$ 4 0 0 0 0 0 0
    $\lambda=0.10$ 4 0 0 0 0 0 0
    $\lambda=0.15$ 4 0 0 0 0 0 0
    $\lambda=0.20$ 4 0 0 0 0 0 0
    $\lambda=0.25$ 3 0 0 0 1 0 0
    Summary 19 0 0 0 1 0 0

Copyright 2020  CHINA SCIENCE PUBLISHING & MEDIA LTD.  中国科技出版传媒股份有限公司  版权所有

京ICP备14028887号-23       京公网安备11010102003388号