# 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 • AcceptedMay 10, 2017
• PublishedSep 1, 2017
Share
Rating

### Abstract

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.

### Acknowledgment

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).

### References

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

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

 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

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

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

 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

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

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

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

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

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

 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

 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

 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

 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

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

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

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

 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

 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

 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

 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

 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

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

 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&apos;_i}(s)$ is a constant; (b) ${P&apos;_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.  中国科技出版传媒股份有限公司  版权所有