MODELING OF ASYMPTOTICALLY OPTIMAL PIECEWISE LINEAR INTERPOLATION OF PLANE PARAMETRIC CURVES

Authors

  • О. V. Frolov Simon Kuznets Kharkiv National University Of Economic, Kharkiv, Ukraine., Ukraine
  • M. U. Losev Simon Kuznets Kharkiv National University Of Economic, Kharkiv, Ukraine., Ukraine

DOI:

https://doi.org/10.15588/1607-3274-2021-3-6

Keywords:

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.

Author Biographies

О. V. Frolov, Simon Kuznets Kharkiv National University Of Economic, Kharkiv, Ukraine.

PhD, Associate Professor, Associate Professor at the Information Systems Department.

M. U. Losev, Simon Kuznets Kharkiv National University Of Economic, Kharkiv, Ukraine.

PhD, Associate Professor, Associate Professor at the Information Systems Department.

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

2021-10-06

How to Cite

Frolov О. V., & Losev, M. U. (2021). MODELING OF ASYMPTOTICALLY OPTIMAL PIECEWISE LINEAR INTERPOLATION OF PLANE PARAMETRIC CURVES . Radio Electronics, Computer Science, Control, (3), 57–68. https://doi.org/10.15588/1607-3274-2021-3-6

Issue

Section

Mathematical and computer modelling