304
правки
Изменения
Нет описания правки
Начальная кривая представляет собой упорядоченный набор точек.
Алгоритм рекурсивно делит линию. Входом алгоритма служат координаты всех точек между первой и последней. Первая и последняя точка сохраняются неизменными. После чего алгоритм находит точку, наиболее удалённую от отрезка, состоящего из первой и последней(оптимальный способ поиска расстояния от точки до отрезка рассмотрен ниже). Если точка находится на расстоянии, меньше чем епсилон<tex>\varepsilon</tex>, то все точки, которые ещё не были отмечены к сохранению, могут быть выброшены из набора и получившаяся прямая сглаживает кривую с точностью не ниже епсилон<tex>\varepsilon</tex>.
Если же расстояние больше епсилон<tex>\varepsilon</tex>, то алгоритм рекурсивно вызывает себя с на наборе от начальной до данной и от данной до конечной точках (что означает, что данная точка будет отмечена к сохранению).
По окончанию всех рекурсивных вызовов выходная ломаная строится только из тех точек, что были отмечены к сохранению.
===Пример===
[[Файл:Example_DP.png|300px|right]]
Рассмотрим пример для точек, заданных на рисунке, где сплошная линия отражает исходную линию, и епсилон равному <tex>\varepsilon = \sqrt 2</tex>.
{| class="wikitable"
! Шаг || Действие
[[Файл:DP(1).png|100px|thumb|right|Оптимальный по количеству точек ответ]]
[[Файл:DP(2).png|100px|thumb|left|Ответ алгоритма Дугласа-Пекера]]
Алгоритм может находить не минимальный по количеству точек ответ. Рассмотрим пример, где исходная линия с некоторым приближением будет представлять полуокружность. Мы можем подобрать такое епсилон<tex>\varepsilon</tex>, что алгоритм добавит три точки помимо стартовой и конечной(точки через каждую четверть исходной линии), в то же время мы можем взять две точки через
каждую треть исходной линии, для которых упрощение также верно.
