Упрощение полигональной цепи

Упрощение полигональной цепи - процесс, позволяющий уменьшить число точек кривой, аппроксимированной серией точек.

Задача

Пусть у нас есть некоторая аппроксимированная кривая, все точки которой нам не нужны, а большинство из них лишь занимает место. Такое встречается при обработки векторной графики и построении карт. Расмотрим пример для построения карт. Пусть у нас есть путь из Москвы в Санкт-Петербург, заданный точками через каждый километр пути. В маштабах всей России такая точность явно ни к чему, стоит оставить лишь точки, отражающие ключевые участки пути. В этом случае нам и пригодится упрощение, одним из вариантов реализации которой является алгоритм Дугласа-Пекера.

Алгоритм Дугласа-Пекера

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

Описание

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

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

Если же расстояние больше епсилон, то алгоритм рекурсивно вызывает себя с на наборе от начальной до данной и от данной до конечной точках (что означает, что данная точка будет отмечена к сохранению).

По окончанию всех рекурсивных вызовов выходная ломаная строится только из тех точек, что были отмечены к сохранению.

Псевдокод

[math]Douglas–Peucker(first, last, eps)[/math]

Для всех точек между [math]first[/math] и [math]last[/math]

Если точка удалена дальше чем предыдущие запомнить ее в [math]max[/math]

Если расстояние от [math]max[/math] до отрезка [math]first-last[/math] меньше [math]eps[/math]

Вернуться

Иначе

Добавить точку [math]max[/math] в ответ

[math]DouglasPeucker(first, max, eps)[/math]

[math]DouglasPeucked(max, last, eps)[/math]

Пример

Рассмотрим пример для точек, заданных на рисунке, где сплошная линия отражает исходную линию и епсилон равному [math]\sqrt 2[/math]

Шаг	Действие
[math]1[/math]	Найдем наиболее удаленную точку от отрезка [math]1-5[/math], это точка [math]3[/math]
[math]2[/math]	Расстояние до точки [math]3[/math] больше [math]\sqrt 2[/math], добавляем ее в ответ
[math]3[/math]	Запустим алгоритм для точек [math]1[/math] и [math]3[/math]
[math]4[/math]	Найдем наиболее удаленную точку от отрезка [math]1-3[/math], это точка [math]2[/math]
[math]5[/math]	Расстояние до точки [math]2[/math] меньше [math]\sqrt 2[/math], возвращаемся
[math]6[/math]	Запустим алгоритм для точек [math]3[/math] и [math]5[/math]
[math]7[/math]	Найдем наиболее удаленную точку от отрезка [math]3-5[/math], это точка [math]4[/math]
[math]8[/math]	Расстояние до точки [math]4[/math] меньше [math]\sqrt 2[/math], возвращаемся
[math]9[/math]	Алгоритм завершен