Изменения

Суть алгоритма Дугласа-Пекера (Douglas-Peucker) состоит в том, чтобы по данной ломаной, аппроксимирующей кривую, построить ломаную с меньшим числом точек. Алгоритму задается максимальное расхождение, которое не может превышать расстояние между исходной и упрощённой ломаными (то есть максимальное расстояние от точек исходной ломаной к ближайшему участку полученной ломаной). Упрощенная кривая ломаная состоит из подмножества точек, которые определяются из исходной кривойломаная.

Начальная кривая ломаная представляет собой упорядоченный набор точек.

Алгоритм рекурсивно делит линиюломаную. Входом алгоритма служат координаты всех точек между первой и последней. Первая и последняя точка сохраняются неизменными. После чего алгоритм находит точку, наиболее удалённую от отрезка, состоящего из первой и последней (оптимальный способ поиска расстояния от точки до отрезка рассмотрен ниже). Если точка находится на расстоянии, меньше чем <tex>\varepsilon</tex>, то все точки, которые ещё не были отмечены к сохранению, могут быть выброшены из набора и получившаяся прямая сглаживает кривую с точностью не ниже <tex>\varepsilon</tex>.