Порівняльний аналіз алгоритмів спрощення многокутників та ламаних ліній

Abstract

У статті проаналізовано існуючі на сьогодні алгоритми спрощення многокутників та ламаних ліній на площині. Проведено порівняльний аналіз оцінок складності алгоритмів, експериментально встановлено час виконання алгоритмів та побудовано криві залежності ступені спрощеності многокутника від значень похибки алгоритму.

В статье проанализированы существующие методы упрощения многоугольников и ломаных линий на плоскости. Проведен сравнительный анализ оценок сложности алгоритмов, экспериментально установлено время выполнения алгоритмов и построены кривые зависимости степени упрощенности многоугольника от значений допустимой погрешности метода.

The article deals with the analysis of the existing algorithms for polygons and polylines simplification. A comparative analysis of the complexities of the algorithms has been carried out. The performed experiments allowed us to measure the empirical execution time of the algorithms and to establish the dependence of the simplicity degree on the tolerable error of the algorithm.