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