Изменения
→Алгоритм Дугласа-Пекера
==Алгоритм Дугласа-Пекера==
Алгоритму задается исходная ломаная и максимальное расстояние, которое может быть между исходной и упрощённой ломаными (то есть , максимальное расстояние от точек исходной ломаной к ближайшему участку полученной ломаной). Упрощенная ломаная состоит из подмножества точек, которые определяются из исходной ломанаяломаной.
===Описание===
Начальная ломаная представляет собой упорядоченный набор точек.
Алгоритм рекурсивно делит ломаную. Входом алгоритма служат координаты всех точек между первой и последней включая их, а так же <tex>\varepsilon</tex>. Первая и последняя точка сохраняются неизменными. После чего алгоритм находит точку, наиболее удалённую от отрезка, состоящего из первой и последней (оптимальный способ поиска расстояния от точки до отрезка рассмотрен ниже). Если точка находится на расстоянии, меньше , чем <tex>\varepsilon</tex>, то все точки, которые ещё не были отмечены к сохранению, могут быть выброшены из набора , и получившаяся прямая сглаживает кривую с точностью не ниже <tex>\varepsilon</tex>.
Если же расстояние больше <tex>\varepsilon</tex>, то алгоритм рекурсивно вызывает себя на наборе от начальной до данной и от данной до конечной точек (что это означает, что данная точка будет отмечена к сохранению).
По окончанию всех рекурсивных вызовов выходная ломаная строится только из тех точек, что были отмечены к сохранению.
| <tex>9</tex> || Алгоритм завершен
|}
===Время работы===
Ожидаемая сложность алгоритма может быть оценена выражением <tex>\Theta(n\log n)</tex> в лучшем случае, когда номер наиболее удаленной точки всегда оказывается лексикографически центральным. Однако , в худшем случае сложность алгоритма составляет <tex>O(n^2)</tex>. Это достигается, апример, в случае, когда если номер наиболее удаленной точки всегда соседний к номеру граничащей граничной точки.
===Замечания к алгоритму===
====Топология====
К сожалению, алгоритм Дугласа-Пекера в ходе своей работы не сохраняет топологию. Это означает, что означает в ответе мы можем получить линию с самопересечениями.
В статье де Берга (de Berg) ''A New Approach to Subdivision Simplification '' приведен алгоритм, позволяющий решать чуть более общую задачу , чем текущая, : упрощение полигональной цепи с учетом обязательных особых точек, не входящих в нее, и с учетом топологии. Можно использовать алгоритм и для текущего случая , задав множество особых точек пустыйпустым. Время работы алгоритма при этом составит <tex>O(n^2\log n)</tex>
====Оптимальность====
[[Файл:DP(1).png|100px|thumb|right|Оптимальный по количеству точек ответ]]
[[Файл:DP(2).png|100px|thumb|left|Ответ алгоритма Дугласа-Пекера]]
Алгоритм может находить не минимальный по количеству точек ответ. Рассмотрим пример, где в котором исходная линия с некоторым приближением будет представлять полуокружность. Мы можем подобрать такое <tex>\varepsilon</tex>, что алгоритм добавит три точки помимо стартовой и конечной (точки через каждую четверть исходной линии), в то же время мы можем взять две точки через
каждую треть исходной линии, для которых упрощение также верно.
===Решение альтернативной задачи===
Альтернативную задачу с заданным числом <tex>k</tex> оптимально решать так, что в итоговой цепи останутся лишь наиболее значимые точки. Алгоритм начинается так же, как и алгоритм для решения обычной задачи. Теперь каждый раз выберается выбирается та часть, у которой наиболее удаленная вершина находится на большем расстоянии относительно таких же вершин других частей. Алгоритм завершится, когда будет итоговая цепь будет состоять из требуемого числа точек.
====Реализация====
Практически очевидно, что данный вариант алгоритма легко реализовать на приоритетной очереди. Будем хранить расстояние, на котором находится наиболее удаленная вершина, как ключ, а номера вершин-границ как значение. На каждой итерации мы выбираем обьект с наибольшим ключем, делим и получившиеся части кладем обратно в очередь с новыми ключами.
