304
правки
Изменения
Нет описания правки
*ускорение подходит лишь для двумерного случая из-за способа построения выпуклой оболочки
*в некоторых случаях оригинальный алгоритм Дугласа-Пекера работает быстрее (например в случае, когда цепь приближено является окружностью)
==Обзор алгоритмов сохраняющих топологию==
В статье де Берга (de Berg) приведен алгоритм, позволяющий решающий чуть более общую задачу чем наша, упрощение полигональной цепи с учетом обязательных особых точек не входящих в нее. Мы можем использовать алгоритм и для нашего случая задав множество особых точек пустый. Время работы алгоритма для нашего случая составит <tex>O\left(n^2\log n\right)</tex>.
==Ссылки==
