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

2012-03-01T05:37:24Z

83.149.3.173:

Упрощение полигональной цепи {{---}} процесс, позволяющий уменьшить число точек кривой, аппроксимированной серией точек.
==Задача==
Дана некоторая аппроксимированная кривая, заданная последовательностью точек, и некоторое <tex>\varepsilon</tex>. Требуется ответить, какие точки мы можем оставить, так чтобы расхождение между исходной и получившейся кривыми не превышало <tex>\varepsilon</tex>, при этом количество точек в получившейся кривой должно стремиться к минимуму.
==Мотивация==
Такая задача встречается при обработки векторной графики и построении карт. Расмотрим пример для построения карт. Дан путь из Москвы в Санкт-Петербург, заданный точками через каждый километр пути. В масштабах всей России такая точность явно ни к чему, стоит оставить лишь точки, отражающие ключевые участки пути. В этом случае и пригодится упрощение, одним из вариантов реализации которого является алгоритм Дугласа-Пекера.

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

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

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

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

===Псевдокод===
<code>DouglasPeucker(int first, int last, double eps)</code>
:<code>max = -infinity</code>
:<code>index = -1</code>
:<code>for (int i = first + 1; i < last; i++)</code>
::<code>distance = dist(points[i], segment(points[first],points[last]))</code>
::<code>if (distance > max && distance > eps)</code>
:::<code>max = distance, index = i</code>
:<code>if(index == -1)</code>
::<code>return</code>
:<code>else</code>
::<code>answer[index] = true</code>
::<code>DouglasPeucker(first, index, eps)</code>
::<code>DouglasPeucker(index, last, eps)</code>

===Пример===
[[Файл:Example_DP.png‎|300px|right]]
Рассмотрим пример для точек, заданных на рисунке, где сплошная линия отражает исходную линию, и <tex>\varepsilon = \sqrt 2</tex>.
{| class="wikitable"
! Шаг || Действие
|-
| <tex>1</tex> || Найдем наиболее удаленную точку от отрезка <tex>1-5</tex>, это точка <tex>3</tex>
|-
| <tex>2</tex> || Расстояние до точки <tex>3</tex> больше <tex>\sqrt 2</tex>, добавляем ее в ответ
|-
| <tex>3</tex> || Запустим алгоритм для точек <tex>1</tex> и <tex>3</tex>
|-
| <tex>4</tex> || Найдем наиболее удаленную точку от отрезка <tex>1-3</tex>, это точка <tex>2</tex>
|-
| <tex>5</tex> || Расстояние до точки <tex>2</tex> меньше <tex>\sqrt 2</tex>, возвращаемся
|-
| <tex>6</tex> || Запустим алгоритм для точек <tex>3</tex> и <tex>5</tex>
|-
| <tex>7</tex> || Найдем наиболее удаленную точку от отрезка <tex>3-5</tex>, это точка <tex>4</tex>
|-
| <tex>8</tex> || Расстояние до точки <tex>4</tex> меньше <tex>\sqrt 2</tex>, возвращаемся
|-
| <tex>9</tex> || Алгоритм завершен
|}
Линия, полученная в результате работы алгоритма, отражается пунктирной линией.

===Время работы===
Ожидаемая сложность алгоритма может быть оценена выражением <tex>\Theta(n\log n)</tex> в лучшем случае, когда номер наиболее удаленной точки всегда оказывается лексикографически центральным. Однако в худшем случае сложность алгоритма <tex>O\left(n^2\right)</tex>, когда номер наиболее удаленной точки всегда соседний к номеру граничащей точки.

===Замечания к алгоритму===
====Топология====
К сожалению, алгоритм Дугласа-Пекера в ходе своей работы не сохраняет топологию, что означает в ответе мы можем получить линию с самопересечениями.

====Оптимальность====
[[Файл:DP(1).png‎|100px|thumb|right|Оптимальный по количеству точек ответ]]
[[Файл:DP(2).png‎|100px|thumb|left|Ответ алгоритма Дугласа-Пекера]]
Алгоритм может находить не минимальный по количеству точек ответ. Рассмотрим пример, где исходная линия с некоторым приближением будет представлять полуокружность. Мы можем подобрать такое <tex>\varepsilon</tex>, что алгоритм добавит три точки помимо стартовой и конечной (точки через каждую четверть исходной линии), в то же время мы можем взять две точки через
каждую треть исходной линии, для которых упрощение также верно.

<br>
==Поиск расстояния от точки до отрезка==
===Идея===
При определении расстояния от точки до отрезка нужно сначала проанализировать взаимное расположение точки и отрезка прямой, то есть, проверить, куда опустится перпендикуляр из точки: непосредственно на отрезок или на прямую, являющуюся продолжением рассматриваемого отрезка.

Если на отрезок, то ответ это расстояние от исходной точки до точки пересечения отрезка с перпендикуляром, если нет, то расстояние от исходной точки до одного из концов отрезка.

Самое очевидное {{---}} это найти точку пересечения перпендикуляра и прямой, и в зависимости от ее положения вычислить ответ. На самом деле, этот анализ может быть произведен путем построения треугольника, вершинами которого являются концы отрезка и точка, и сопоставления соотношения длин его сторон.

===Реализация===
[[Файл:DistancePointToSegment.gif‎|300px|right]]
Даны точка <tex>(x_0, y_0)</tex> и отрезок, заданный точками <tex>(x_1, y_1)</tex> и <tex>(x_2, y_2)</tex>.

Введём обозначения:
*<tex>R_1</tex> отрезок <tex>(x_0, y_0)</tex><tex>(x_1, y_1)</tex>
*<tex>R_2</tex> отрезок <tex>(x_0, y_0)</tex><tex>(x_2, y_2)</tex>
*<tex>R_{12}</tex> отрезок <tex>(x_1, y_1)</tex><tex>(x_2, y_2)</tex>
Если:
*<tex>|R_1| \ge \sqrt{|R_2|^2+|R_{12}|^2}</tex>, то ответ это <tex>|R_2|</tex>, так как угол между <tex>R_2</tex> и <tex>R_{12}</tex> при данном условии <tex> \ge 90^{\circ}</tex>
*<tex>|R_2| \ge \sqrt{|R_1|^2+|R_{12}|^2}</tex>, то ответ это <tex>|R_1|</tex>, так как угол между <tex>R_1</tex> и <tex>R_{12}</tex> при данном условии <tex> \ge 90^{\circ}</tex>
*Оба предыдущих условия ложны, то <tex>abs(| \overrightarrow{R_{12}} \times \overrightarrow{R_1}|/|\overrightarrow{R_{12}}|)</tex>, где <tex> \overrightarrow{R_{12}} = (x_2 -x_1, y_2 - y_1)</tex> и <tex> \overrightarrow{R_1} = (x_1 - x_0, y_1 - y_0)</tex>. Это следует из формул для площади параллелограмма через векторное произведение и через произведения основания на высоту

==Ссылки==
*[http://ru.wikipedia.org/wiki/Алгоритм_Рамера_—_Дугласа_—_Пекера Алгоритм Дугласа-Пекера]
*[http://pers.narod.ru/algorithms/pas_dist_from_point_to_line.html Поиск расстояния от точки до отрезка]
*[http://algolist.manual.ru/maths/geom/distance/pointline.php Поиск расстояния от точки до прямой]

Викиконспекты - Вклад участника [ru]

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