304
правки
Изменения
→Описание
Начальная кривая представляет собой упорядоченный набор точек.
Алгоритм рекурсивно делит линию. Входом алгоритма служат координаты всех точек между первой и последней. Первая и последняя точка сохраняются неизменными. После чего алгоритм находит точку, наиболее удалённую от отрезка, состоящего из первой и последней(оптимальный способ, нахождения расстояния от точки до отрезка рассмотрен ниже). Если точка находится на расстоянии, меньше чем епсилон, то все точки, которые ещё не были отмечены к сохранению, могут быть выброшены из набора и получившаяся прямая сглаживает кривую с точностью не ниже епсилон.
Если же расстояние больше епсилон, то алгоритм рекурсивно вызывает себя с на наборе от начальной до данной и от данной до конечной точках (что означает, что данная точка будет отмечена к сохранению).
По окончанию всех рекурсивных вызовов выходная ломаная строится только из тех точек, что были отмечены к сохранению.
===Псевдокод===
<tex>Douglas–Peucker(first, last, eps)</tex>
