Изменения
Новая страница: «Упрощение полигональной цепи - процесс, позволяющий уменьшить число точек кривой, аппро...»
Упрощение полигональной цепи - процесс, позволяющий уменьшить число точек кривой, аппроксимированной серией точек.
==Задача==
Пусть у нас есть некоторая аппроксимированная кривая, все точки которой нам не нужны, а большинство из них лишь занимает место. Такое встречается при обработки векторной графики и построении карт. Расмотрим пример для построения карт. Пусть у нас путь из Москвы в Санкт-Петербург, заданный точками через каждый километр пути. В маштабах всей России такая точность явно ни к чему, стоит оставить лишь точки, отражающие ключевые участки пути. В этом случае нам и пригодится упрощение, одним из вариантов реализации которой является алгоритм Дугласа-Пекера.
==Алгоритм Дугласа-Пекера==
Суть алгоритма Дугласа-Пекера(Douglas–Peucker) состоит в том, чтобы по данной ломаной, аппроксимирующей кривую, построить ломаную с меньшим числом точек. Алгоритм определяет расхождение, которое вычисляется по максимальному расстоянию между исходной и упрощённой кривыми. Упрощенная кривая состоит из подмножества точек, которые определяются из исходной кривой.
===Описание===
Начальная кривая представляет собой упорядоченный набор точек.
Алгоритм рекурсивно делит линию. Входом алгоритма служат координаты всех точек между первой и последней. Первая и последняя точка сохраняются неизменными. После чего алгоритм находит точку, наиболее удалённую от отрезка, состоящего из первой и последней. Если точка находится на расстоянии, меньше чем епсилон, то все точки, которые ещё не были отмечены к сохранению, могут быть выброшены из набора и получившаяся прямая сглаживает кривую с точностью не ниже епсилон.
Если же расстояние больше епсилон, то алгоритм рекурсивно вызывает себя с на наборе от начальной до данной и от данной до конечной точках (что означает, что данная точка будет отмечена к сохранению).
По окончанию всех рекурсивных вызовов выходная ломаная строится только из тех точек, что были отмечены к сохранению.
===Псевдокод===
<tex>Douglas–Peucker(first, last, eps)</tex>
:<code>Для всех точек между</code> <tex>first</tex> <code>и</code> <tex>last</tex>
::<code>Если точка удалена дальше чем предыдущие запомнить ее в</code> <tex>max</tex>
:<code>Если расстояние от</code> <tex>max</tex> <code>до отрезка</code> <tex>first-last</tex> <code>меньше</code> <tex>eps</tex>
::<code>Вернуться</code>
:<code>Иначе</code>
::<code>Добавить точку</code> <tex>max</tex> <code>в ответ</code>
::<tex>Douglas-Peucker(first, max, eps)</tex>
::<tex>Douglas-Peucked(max, last, eps)</tex>
==Задача==
Пусть у нас есть некоторая аппроксимированная кривая, все точки которой нам не нужны, а большинство из них лишь занимает место. Такое встречается при обработки векторной графики и построении карт. Расмотрим пример для построения карт. Пусть у нас путь из Москвы в Санкт-Петербург, заданный точками через каждый километр пути. В маштабах всей России такая точность явно ни к чему, стоит оставить лишь точки, отражающие ключевые участки пути. В этом случае нам и пригодится упрощение, одним из вариантов реализации которой является алгоритм Дугласа-Пекера.
==Алгоритм Дугласа-Пекера==
Суть алгоритма Дугласа-Пекера(Douglas–Peucker) состоит в том, чтобы по данной ломаной, аппроксимирующей кривую, построить ломаную с меньшим числом точек. Алгоритм определяет расхождение, которое вычисляется по максимальному расстоянию между исходной и упрощённой кривыми. Упрощенная кривая состоит из подмножества точек, которые определяются из исходной кривой.
===Описание===
Начальная кривая представляет собой упорядоченный набор точек.
Алгоритм рекурсивно делит линию. Входом алгоритма служат координаты всех точек между первой и последней. Первая и последняя точка сохраняются неизменными. После чего алгоритм находит точку, наиболее удалённую от отрезка, состоящего из первой и последней. Если точка находится на расстоянии, меньше чем епсилон, то все точки, которые ещё не были отмечены к сохранению, могут быть выброшены из набора и получившаяся прямая сглаживает кривую с точностью не ниже епсилон.
Если же расстояние больше епсилон, то алгоритм рекурсивно вызывает себя с на наборе от начальной до данной и от данной до конечной точках (что означает, что данная точка будет отмечена к сохранению).
По окончанию всех рекурсивных вызовов выходная ломаная строится только из тех точек, что были отмечены к сохранению.
===Псевдокод===
<tex>Douglas–Peucker(first, last, eps)</tex>
:<code>Для всех точек между</code> <tex>first</tex> <code>и</code> <tex>last</tex>
::<code>Если точка удалена дальше чем предыдущие запомнить ее в</code> <tex>max</tex>
:<code>Если расстояние от</code> <tex>max</tex> <code>до отрезка</code> <tex>first-last</tex> <code>меньше</code> <tex>eps</tex>
::<code>Вернуться</code>
:<code>Иначе</code>
::<code>Добавить точку</code> <tex>max</tex> <code>в ответ</code>
::<tex>Douglas-Peucker(first, max, eps)</tex>
::<tex>Douglas-Peucked(max, last, eps)</tex>
