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