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