Modeling of asymptotically optimal piecewise linear interpolation of plane parametric curves

Abstract

EN: 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. UK: Актуальність. Апроксимація кривих ламаними привертає увагу з метою її застосування до відтворення об’єктів складної форми на комп’ютері, верстатах з ЧПК та 3D принтерах. При цьому бажано мати найменшу кількість ланок ламаної, що замінює криву, зі збереженням необхідної точності відтворення. Мета. Вдосконалення методу асимптотично оптимальної кусково-лінійної інтерполяції плоских параметричних кривих на основі дослідження впливу його параметрів та алгоритмів на розподіли похибок апроксимації реальних кривих ліній. Метод. В роботі розглядається асимпточно-оптимальна інтерполяція плоских кривих, які задовольняють умові мінімальності кількості ланок апроксимації. Було запропоновано алгоритми отримання значень послідовності вузлів апроксимації на основі чисельного інтегрування функції – регулятора з подальшою лінійною та сплайновою інтерполяцією її значень. Обґрунтовано методику оцінки результатів моделювання апроксимації реальних кривих, що базується на статистичній обробці рядів відносних похибок ланок ламаної. Проведено моделювання апроксимації реальних кривих та досліджено вплив на показники розподілу похибок кількісної характеристики ступеню дискретизації інтегральної функції – регулятора вузлів в залежності від методу інтерполяції значень інтегральної функції. Результати. Проведені дослідження дозволили виявити вплив первісної дискретизації інтегральної функції – регулятора вузлів на якість відтворення кривих ламаними за асимптотично оптимальним алгоритмом та можливості визначення раціонального ступеню дискретизації при практичних розрахунках для відтворення виробів складної форми. Встановлено, що при достатній кількості точок дискретизації дисперсія розподілу похибок апроксимації стабілізується і збільшення цієї кількості на порядок не значно підвищує точність відтворення кривої. При цьому сплайнова інтерполяція значень інтегральної функції давала значно більшу швидкість стабілізації значень параметрів розподілів, що дозволяє знизити кількість вузлів первісної дискретизації у 5–6 разів маючи аналогічні показники точності апроксимації. Висновки. Відтворення реальних плоских параметричних кривих опуклої форми ламаними за асимптотично-оптимальним алгоритмом інтерполяції показало цілком прийнятні результати без перевищення допустимої похибки апроксимації у випадках достатнього ступеню дискретизації значень інтегральної функції. Напрямками подальших досліджень може бути дослідження можливості спрощення розрахунків при обчисленні значень інтегральної функції розподілу чисельними методами, а також можливості використання дискретних аналогів похідних у виразі цієї функції.