MODELING OF ASYMPTOTICALLY OPTIMAL PIECEWISE LINEAR INTERPOLATION OF PLANE PARAMETRIC CURVES
DOI:
https://doi.org/10.15588/1607-3274-2021-3-6Keywords:
interpolation, polyline segment, linear rational B-spline, equidistant, integration, parametric curve, approximation error, variance.Abstract
Context. Piecewise linear approximation of curves has a large number of applications in computer algorithms, as the reconstruction of objects of complex shapes on monitors, CNC machines and 3D printers. In many cases, it is required to have the smallest number of segments for a given accuracy.
Objective. The objective of this paper is to improve the method of asymptotically optimal piecewise linear interpolation of plane parametric curves. This improvement is based to research influence of the method parameters and algorithms to distributions of approximation errors.
Method. An asymptotically optimal method of curves interpolation is satisfied to the condition of minimum number of approximation units. Algorithms for obtaining the values of the sequence of approximation nodes are suggested. This algorithm is based on numerical integration of the nodes regulator function with linear and spline interpolation of its values. The method of estimating the results of the curve approximation based on statistical processing of line segments sequence of relative errors is substantiated. Modeling of real curves approximation is carried out and influence of the sampling degree of integral function – the nodes regulator on distribution parameters of errors is studied. The influence is depending on a method of integral function interpolation.
Results. Research allows to define necessary the number of discretization nodes of the integral function in practical applications. There have been established that with enough sampling points the variance of the error’s distribution stabilizes and further increasing this number does not significantly increase the accuracy of the curve approximation. In the case of spline interpolation of the integral function, the values of the distribution parameters stabilized much faster, which allows to reduce the number of initial sampling nodes by 5–6 times having similar accuracy.
Conclusions. Modelling of convex planar parametric curves reconstruction by an asymptotically optimal linear interpolation algorithm showed acceptable results without exceeding the maximum errors limit in cases of a sufficient discretization of the integral function. The prospect of further research is to reduce the computational complexity when calculating the values of the integral distribution function by numerical methods, and to use discrete analogues of derivatives in the expression of this function.
References
Ligun A. A., Shumeiko A. A., Radzevitch S. P., Goodman E. D. Asymptotically optimal disposition of tangent points for approximation of smooth convex surfaces by polygonal functions, Computer Aided Geometric Design, 1997, Vol. 14, pp. 533–546. DOI: 10.1016/S0167-8396(96)000441.
de Figueiredo L. H. Adaptive sampling of parametric curves, Graphics Gems V, 1995, pp. 173–178. DOI: 10.1016/B978-0-12-543457-7.50032-2.
Pagani L., Scott P. J. Curvature based sampling of curves and surfaces, Computer Aided Geometric Design, 2018, Vol. 59, pp. 32–48. DOI: 10.1016/j.cagd.2017.11.004.
Hernández-Mederos V., Estrada-Sarlabous J. Sampling points on regular parametric curves with control of their distribution, Computer Aided Geometric Design, 2003, Vol. 20, Issue 6, pp. 363–382. DOI: 10.1016/S0167-8396(03)000797.
Zhong W., Luo X., Chang W. et al. A real-time interpolator for parametric curves, International Journal of Machine Tools and Manufacture, 2018, Vol. 125, pp. 133–145, DOI: 10.1016/j.ijmachtools.2017.11.010.
Bo P., Bartoň M., Pottmann H. Automatic fitting of conical envelopes to free-form surfaces for flank CNC machining, Computer-Aided Design, 2017, Vol. 91, pp. 84–94. DOI: 10.1016/ j.cad.2017.06.006.
Song Y., Yang Zh., Liu Y., Deng J. Function representation based slicer for 3D printing, Computer Aided Geometric Design, 2018, Vol. 62, pp. 276–293. DOI: 10.1016/j.cagd.2018.03.012.
Ohrhallinger S., Wimmer M. StretchDenoise: parametric curve reconstruction with guarantees by separating connectivity from residual uncertainty of samples, Proceedings of the 26th Pacific Conference on Computer Graphics and Applications, 2018, pp. 1–4. DOI: 10.2312/pg.20181266.
Cleghorn C. W., Engelbrecht A. P. Piecewise linear approximation of n-dimensional parametric curves using particle swarms, Swarm Intelligence. ANTS 2012. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, 2012, Vol. 7461, pp. 292–299. DOI: 10.1007/978-3-642-326509_30.
Ugaz C., Han L., Lim A. Knot locating in piecewise linear approximation [Electronic resource], arXiv preprint, arXiv 1909.03112, 2019, 13 p. Access mode: https://arxiv.org/abs/1909.03112
Berjón D., Gallego G., Cuevas C. et al. Optimal piecewise linear function approximation for GPU-based applications, IEEE Transactions on Cybernetics, 2016, Vol. 46 (11), pp. 2584–2595. DOI: 10.1109/TCYB.2015.2482365.
Belyaev A. G., Anoshkina E. V., Yoshizawa S., Yano M. Polygonal curve evolutions for planar shape modeling and analysis, International Journal of Shape Modeling, 1999, Vol. 05, No. 02, pp. 195–217. DOI: 10.1142/S0218654399000174.
Langer T., Belyaev A. G., Seidel H.-P. Asymptotic analysis of discrete normals and curvatures of polylines, SCCG '05: Proceedings of the 21st Spring Conference on Computer Graphics, 2005. pp. 229–232. DOI: 10.1145/1090122.1090160.
Gournay F., Kahn J., Lebrat L. Approximation of curves with piecewise constant or piecewise linear functions [Electronic resource], HAL Id hal-02284549, 2019, 17 p. Access mode: https://arxiv.org/pdf/1909.04582.pdf
Han Y., Samet H. LiMITS: An effective approach for trajectory simplification [Electronic resource], arXiv pre-print, arXiv:2010.08622v1, 2020, 13 p. Access mode: https://arxiv.org/abs/2010.08622v1
Fuhr R. D., Kallay M. Monotone linear rational spline interpolation, Computer Aided Geometric Design. 1992, Vol. 9, Issue 4, pp. 313–319. DOI:10.1016/0167-8396(92)90038-Q.
Epperson J. F. An introduction to numerical methods and analysis. New Jersey, Wiley, 2013, 615 p.
Oja P. Low degree rational spline interpolation, BIT Numerical Mathematics, 1997, Vol. 37, Issue 4, pp. 901–909. DOI: 10.1007/BF02510359.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 О. В. Фролов, М. Ю. Лосєв
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
