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