Упрощение полигональной цепи — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 49 промежуточных версий 9 участников)
Строка 1: Строка 1:
Упрощение полигональной цепи {{---}} процесс, позволяющий уменьшить число точек кривой, аппроксимированной серией точек.
+
Упрощение полигональной цепи {{---}} процесс, позволяющий уменьшить число точек полилинии.
 
==Задача==
 
==Задача==
Дана некоторая аппроксимированная кривая, заданная последовательностью точек, и некоторое <tex>\varepsilon</tex>. Требуется ответить, какие точки мы можем оставить, так чтобы расхождение между исходной и получившейся кривыми не превышало <tex>\varepsilon</tex>, при этом количество точек в получившейся кривой должно стремиться к минимуму.
+
Дана некоторая полилиния, заданная последовательностью точек <tex> a_1, a_2, ..., a_n</tex>, и некоторое <tex>\varepsilon</tex>. Требуется найти цепь <tex> a_1, a_i, a_j, ..., a_n </tex>, являющейся подпоследовательностью исходной. Для этой цепи верно, что для всех <tex>k</tex>, таких что <tex> i < k < j:</tex> <tex>\rho(a_k, Segment(a_i, a_j)) \le \varepsilon</tex> для любых соседних <tex>i</tex> и <tex>j</tex>.
 +
 
 +
Существует также альтернативная задача, в которой вместо <tex>\varepsilon</tex> задано число <tex>k</tex> вершин в итоговой цепи. В этом случае требуется составить цепь <tex> a_1, a_i, a_j, ..., a_n </tex> заданной длины таким образом, что максимально необходимое <tex>\varepsilon</tex> для условия <tex> \rho(a_k, Segment(a_i, a_j)) \le \varepsilon</tex> было минимально.
 +
 
 +
Также упрощение можно выполнять с помощью введения новой полилинии, не сохраняющей точки исходной, но такая вариация задачи рассмотрена не будет.
  
Существует также альтернативная задача, при которой вместо <tex>\varepsilon</tex> задано число <tex>k</tex> вершин в итоговой цепи.
 
 
==Мотивация==
 
==Мотивация==
 
Такая задача встречается при обработки векторной графики и построении карт. Например, есть цепь, несколько точек которой попадают в один и тот же пиксель. Очевидно, что тогда можно упростить все эти точки в одну. В этом случае и пригодится упрощение, одним из вариантов реализации которого является алгоритм Дугласа-Пекера (Douglas-Peucker).
 
Такая задача встречается при обработки векторной графики и построении карт. Например, есть цепь, несколько точек которой попадают в один и тот же пиксель. Очевидно, что тогда можно упростить все эти точки в одну. В этом случае и пригодится упрощение, одним из вариантов реализации которого является алгоритм Дугласа-Пекера (Douglas-Peucker).
  
В случае, когда у нас есть несколько устройств с разным dpi, например монитор и принтер, то, решив альтернативную задачу, можно адаптировать одну и ту же цепь для разных устройств.
+
В случае, когда у нас есть несколько устройств с разным dpi, например, монитор и принтер, то, взяв за <tex>\varepsilon</tex> половину расстояния, которое помещается на одной из границ пикселя, мы можем растеризовать одну и ту же цепь для разных устройств.
  
 
==Алгоритм Дугласа-Пекера==
 
==Алгоритм Дугласа-Пекера==
Алгоритму задается исходная ломаная и максимальное расстояние, которое может быть между исходной и упрощённой ломаными (то есть максимальное расстояние от точек исходной ломаной к ближайшему участку полученной ломаной). Упрощенная ломаная состоит из подмножества точек, которые определяются из исходной ломаная.
+
Алгоритму задается исходная полилиния и максимальное расстояние, которое может быть между исходной и упрощённой полилиниями (то есть, максимальное расстояние от точек исходной к ближайшему участку полученной полилинии). Упрощенная полилиния состоит из подмножества точек, которые определяются из исходной.
 
===Описание===
 
===Описание===
Начальная ломаная представляет собой упорядоченный набор точек.
+
Начальная полилиния представляет собой упорядоченный набор точек.
  
Алгоритм рекурсивно делит ломаную. Входом алгоритма служат координаты всех точек между первой и последней включая их, а так же <tex>\varepsilon</tex>. Первая и последняя точка сохраняются неизменными. После чего алгоритм находит точку, наиболее удалённую от отрезка, состоящего из первой и последней (оптимальный способ поиска расстояния от точки до отрезка рассмотрен ниже). Если точка находится на расстоянии, меньше чем <tex>\varepsilon</tex>, то все точки, которые ещё не были отмечены к сохранению, могут быть выброшены из набора и получившаяся прямая сглаживает кривую с точностью не ниже <tex>\varepsilon</tex>.
+
Алгоритм рекурсивно делит полилинию. Входом алгоритма служат координаты всех точек между первой и последней включая их, а так же <tex>\varepsilon</tex>. Первая и последняя точка сохраняются неизменными. После чего алгоритм находит точку, наиболее удалённую от отрезка, состоящего из первой и последней (оптимальный способ поиска расстояния от точки до отрезка рассмотрен ниже). Если точка находится на расстоянии, меньше, чем <tex>\varepsilon</tex>, то все точки, которые ещё не были отмечены к сохранению, могут быть выброшены из набора, и получившаяся прямая сглаживает кривую с точностью не ниже <tex>\varepsilon</tex>.
  
Если же расстояние больше <tex>\varepsilon</tex>, то алгоритм рекурсивно вызывает себя на наборе от начальной до данной и от данной до конечной точек (что означает, что данная точка будет отмечена к сохранению).
+
Если же расстояние больше <tex>\varepsilon</tex>, то алгоритм рекурсивно вызывает себя на наборе от начальной до данной и от данной до конечной точек (данная точка будет отмечена к сохранению).
  
По окончанию всех рекурсивных вызовов выходная ломаная строится только из тех точек, что были отмечены к сохранению.
+
По окончанию всех рекурсивных вызовов итоговая полилиния строится только из тех точек, что были отмечены к сохранению.
  
 
===Псевдокод===
 
===Псевдокод===
Строка 59: Строка 62:
 
| <tex>9</tex> || Алгоритм завершен
 
| <tex>9</tex> || Алгоритм завершен
 
|}
 
|}
Линия, полученная в результате работы алгоритма, отражается пунктирной линией.
+
Полилиния, полученная в результате работы алгоритма, отражается черной пунктирной линией.
 
 
 
 
 
 
 
 
  
 
===Время работы===
 
===Время работы===
Ожидаемая сложность алгоритма может быть оценена выражением <tex>\Theta(n\log n)</tex> в лучшем случае, когда номер наиболее удаленной точки всегда оказывается лексикографически центральным. Однако в худшем случае сложность алгоритма <tex>O(n^2)</tex>, когда номер наиболее удаленной точки всегда соседний к номеру граничащей точки.
+
Ожидаемая сложность алгоритма может быть оценена выражением <tex>\Theta(n\log n)</tex> в лучшем случае, когда номер наиболее удаленной точки всегда оказывается лексикографически центральным. Однако, в худшем случае сложность алгоритма составляет <tex>O(n^2)</tex>. Это достигается, например, в случае, если номер наиболее удаленной точки всегда соседний к номеру граничной точки.
  
 
===Замечания к алгоритму===
 
===Замечания к алгоритму===
 
====Топология====
 
====Топология====
К сожалению, алгоритм Дугласа-Пекера в ходе своей работы не сохраняет топологию, что означает в ответе мы можем получить линию с самопересечениями.
+
К сожалению, алгоритм Дугласа-Пекера в ходе своей работы не сохраняет топологию. Это означает, что в ответе мы можем получить линию с самопересечениями.
  
В статье де Берга (de Berg) A New Approach to Subdivision Simplification приведен алгоритм, позволяющий решать чуть более общую задачу чем текущая, упрощение полигональной цепи с учетом обязательных особых точек, не входящих в нее, с учетом топологии. Можно использовать алгоритм и для текущего случая задав множество особых точек пустый. Время работы алгоритма при этом составит <tex>O(n^2\log n)</tex>
+
В статье де Берга (de Berg) ''[http://www.bowdoin.edu/~ltoma/teaching/cs350/spring06/Lecture-Handouts/deberg95new.pdf "A New Approach to Subdivision Simplification"]''(1995) приведен алгоритм, позволяющий решать чуть более общую задачу, чем текущая: упрощение полигональной цепи с учетом обязательных особых точек, не входящих в нее и с учетом топологии. Можно использовать алгоритм и для текущего случая, задав множество особых точек пустым. Время работы алгоритма при этом составит <tex>O(n^2\log n)</tex>. Краткое описание алгоритма дано ниже.
  
 
====Оптимальность====
 
====Оптимальность====
 
[[Файл:DP(1).png‎|100px|thumb|right|Оптимальный по количеству точек ответ]]
 
[[Файл:DP(1).png‎|100px|thumb|right|Оптимальный по количеству точек ответ]]
 
[[Файл:DP(2).png‎|100px|thumb|left|Ответ алгоритма Дугласа-Пекера]]
 
[[Файл:DP(2).png‎|100px|thumb|left|Ответ алгоритма Дугласа-Пекера]]
Алгоритм может находить не минимальный по количеству точек ответ. Рассмотрим пример, где исходная линия с некоторым приближением будет представлять полуокружность. Мы можем подобрать такое <tex>\varepsilon</tex>, что алгоритм добавит три точки помимо стартовой и конечной (точки через каждую четверть исходной линии), в то же время мы можем взять две точки через
+
Алгоритм может находить не минимальный по количеству точек ответ. Рассмотрим пример, в котором исходная линия с некоторым приближением будет представлять полуокружность. Мы можем подобрать такое <tex>\varepsilon</tex>, что алгоритм добавит три точки помимо стартовой и конечной (точки через каждую четверть исходной линии), в то же время мы можем взять две точки через
 
каждую треть исходной линии, для которых упрощение также верно.
 
каждую треть исходной линии, для которых упрощение также верно.
  
Строка 83: Строка 82:
  
 
===Решение альтернативной задачи===
 
===Решение альтернативной задачи===
Альтернативную задачу с заданным числом <tex>k</tex> оптимально решать так, что в итоговой цепи останутся лишь наиболее значимые точки. Алгоритм начинается как и для обычной задачи. Теперь каждый раз выберается та часть, у которой наиболее удаленная вершина находится на большем расстоянии относительно таких же вершин других частей. Алгоритм завершится, когда будет итоговая цепь будет состоять из требуемого числа точек.  
+
Решение альтернативной задачи очень схоже с исходном алгоритмом. На каждой итерации алгоритм находит подучасток исходной цепи, на котором расстояние до наиболее удаленной точки максимально, делит ее так же как и в исходном алгоритме и запоминает полученные в результате деления подучастки для следующих итераций. Алгоритм стартует, когда для выбора доступна только исходная цепь.
 
====Реализация====
 
====Реализация====
 
Практически очевидно, что данный вариант алгоритма легко реализовать на приоритетной очереди. Будем хранить расстояние, на котором находится наиболее удаленная вершина, как ключ, а номера вершин-границ как значение. На каждой итерации мы выбираем обьект с наибольшим ключем, делим и получившиеся части кладем обратно в очередь с новыми ключами.
 
Практически очевидно, что данный вариант алгоритма легко реализовать на приоритетной очереди. Будем хранить расстояние, на котором находится наиболее удаленная вершина, как ключ, а номера вершин-границ как значение. На каждой итерации мы выбираем обьект с наибольшим ключем, делим и получившиеся части кладем обратно в очередь с новыми ключами.
Строка 91: Строка 90:
 
При определении расстояния от точки до отрезка нужно сначала проанализировать взаимное расположение точки и отрезка прямой, то есть, проверить, куда опустится перпендикуляр из точки: непосредственно на отрезок или на прямую, являющуюся продолжением рассматриваемого отрезка.  
 
При определении расстояния от точки до отрезка нужно сначала проанализировать взаимное расположение точки и отрезка прямой, то есть, проверить, куда опустится перпендикуляр из точки: непосредственно на отрезок или на прямую, являющуюся продолжением рассматриваемого отрезка.  
  
Если на отрезок, то ответ это расстояние от исходной точки до точки пересечения отрезка с перпендикуляром, если нет, то расстояние от исходной точки до одного из концов отрезка.  
+
Если перпендикуляр падает на отрезок, то ответом будет расстояние от исходной точки до точки пересечения отрезка с перпендикуляром, иначе {{---}} расстояние от исходной точки до одного из концов отрезка.  
  
Самое очевидное {{---}} это найти точку пересечения перпендикуляра и прямой, и в зависимости от ее положения вычислить ответ. На самом деле, этот анализ может быть произведен путем построения треугольника, вершинами которого являются концы отрезка и точка, и сопоставления соотношения длин его сторон.
+
Самое очевидное {{---}} найти точку пересечения перпендикуляра и прямой и, в зависимости от ее положения, вычислить ответ. Или же, этот анализ может быть произведен путем построения треугольника, вершинами которого являются концы отрезка и точка, и сопоставления соотношения длин его сторон.
  
 
===Реализация===
 
===Реализация===
[[Файл:DistancePtoS.png‎|400px|right]]
+
[[Файл:DistancePtoS1.png‎|400px|right]]
Даны точка <tex>(x_0, y_0)</tex> и отрезок, заданный точками <tex>(x_1, y_1)</tex> и <tex>(x_2, y_2)</tex>.
+
Даны точка <tex>O</tex> и отрезок, заданный точками <tex>A</tex> и <tex>B</tex>.
  
 
Введём обозначения:
 
Введём обозначения:
*<tex>R_1</tex> отрезок <tex>(x_0, y_0)</tex><tex>(x_1, y_1)</tex>
+
*<tex>R_1</tex> {{---}} отрезок <tex>[O; A]</tex>
*<tex>R_2</tex> отрезок <tex>(x_0, y_0)</tex><tex>(x_2, y_2)</tex>
+
*<tex>R_2</tex> {{---}} отрезок <tex>[O; B]</tex>
*<tex>R_{12}</tex> отрезок <tex>(x_1, y_1)</tex><tex>(x_2, y_2)</tex>
+
*<tex>R_{12}</tex> {{---}} отрезок <tex>[A; B]</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_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>|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>. Это следует из формул для площади параллелограмма через векторное произведение и через произведения основания на высоту
+
*Оба предыдущих условия ложны, то <tex>\operatorname{abs} (\frac{| \overrightarrow{R_{12}} \times  \overrightarrow{R_1}|}{|\overrightarrow{R_{12}}|})</tex>, где <tex> \overrightarrow{R_{12}} = B - A</tex> и <tex> \overrightarrow{R_1} = A - O</tex>. Это следует из формул для площади параллелограмма через векторное произведение и через произведения основания на высоту
  
 
<br clear="all"/>
 
<br clear="all"/>
 +
 
==Обзор ускорения работы алгоритма Дугласа-Пекера==
 
==Обзор ускорения работы алгоритма Дугласа-Пекера==
Как описано выше, в худшем случае алгоритм работает за <tex>O(n^2)</tex>. Можно внести дополнения, которые позволят получить <tex>O(n\log n)</tex> в худшем случае. Ускорение основывается на уменьшении времени поиска наиболее удаленной вершины. Это можно осуществить благодаря идее о том, что наиболее удаленная вершина лежит на выпуклой оболочке полигональной цепи.
+
Как описано выше, в худшем случае алгоритм работает за <tex>O(n^2)</tex>. Можно внести дополнения, которые позволят получить <tex>O(n\log n)</tex> в худшем случае. Ускорение основывается на уменьшении времени поиска наиболее удаленной вершины. Это можно осуществить благодаря идее о том, что наиболее удаленная вершина лежит на выпуклой оболочке полигональной цепи. Описание ускорения взято из статьи Хершберга(Hershberger) ''[http://www.bowdoin.edu/~ltoma/teaching/cs350/spring06/Lecture-Handouts/hershberger92speeding.pdf "Speeding Up the Douglas-Peucker Line-Simplification Algorithm"]'' (1992).
  
Для построения выпуклой оболочки используется алгоритм Мелкмана, который работает для двумерной полигональной цепи без самопересечений за <tex>O(n)</tex>, строя все промежуточные выпуклые оболочки, которые пригодятся в дальнейшем.
+
Для построения выпуклой оболочки используется [http://www.ams.sunysb.edu/~jsbm/courses/545/melkman.pdf алгоритм Мелкмана], который работает для двумерной полигональной цепи без самопересечений за <tex>O(n)</tex>, строя все промежуточные выпуклые оболочки, которые пригодятся в дальнейшем.
  
Построив выпуклую оболочку, используется бинарный поиск для нахождения наиболее удаленной вершины за <tex>O(\log n)</tex>. Затем, если потребуется, действия повторятся рекурсивно, как и в оригинальном алгоритме, но заново строить оболочки не имеет смысла, так как промежуточные уже были построены. Использовав их, можно разбить текущую оболочку на две за <tex>O(\log n)</tex>.
+
После построения выпуклой оболочки используется бинарный поиск для нахождения наиболее удаленной вершины за <tex>O(\log n)</tex>. Затем, если потребуется, действия повторятся рекурсивно, как и в оригинальном алгоритме, но заново строить оболочки не имеет смысла, так как промежуточные уже были построены. Использовав их, можно разбить текущую оболочку на две за <tex>O(\log n)</tex>.
  
 
В итоге получается, что в худшем случае <tex>O(n)</tex> разбиений за <tex>O(\log n)</tex> и поиск за <tex>O(\log n)</tex>, что дает <tex>O(n\log n)</tex>.
 
В итоге получается, что в худшем случае <tex>O(n)</tex> разбиений за <tex>O(\log n)</tex> и поиск за <tex>O(\log n)</tex>, что дает <tex>O(n\log n)</tex>.
Строка 125: Строка 125:
 
==Алгоритм Реуманна-Виткама==
 
==Алгоритм Реуманна-Виткама==
 
[[Файл:Pw2.png‎|200px|right]]
 
[[Файл:Pw2.png‎|200px|right]]
Алгоритм Реуманна-Виткама (Reumann-Witkam) определяет прямую через первые две точки цепи, последняя из последовательных точек начиная со второй, удаленных небольше чем на <tex>\varepsilon</tex>, соединяются прямой, а все промежуточные точки исключаются. Алгоритм продолжится последовательно для оставшихся точек до тех пор, пока не будет достигнута последняя.
+
[http://psimpl.sourceforge.net/reumann-witkam.html Алгоритм Реуманна-Виткама] (Reumann-Witkam) определяет прямую через первые две точки цепи, последняя из последовательных точек начиная со второй, удаленных небольше чем на <tex>\varepsilon</tex>, соединяются прямой, а все промежуточные точки исключаются.  
 +
 
 +
Алгоритм продолжится последовательно для оставшихся точек до тех пор, пока не будет достигнута последняя.
  
 
На рисунке прямая, проходящая через точки отображена красной линией, границы, в которые попадают вершины, допустимые для упрощения, отображены красными пунктирными линиями, точки попавшие в итоговую цепь отображены черным.
 
На рисунке прямая, проходящая через точки отображена красной линией, границы, в которые попадают вершины, допустимые для упрощения, отображены красными пунктирными линиями, точки попавшие в итоговую цепь отображены черным.
Строка 132: Строка 134:
 
==Алгоритм Опхейма==
 
==Алгоритм Опхейма==
 
[[Файл:Op.png‎|200px|left]]
 
[[Файл:Op.png‎|200px|left]]
Алгоритм Опхейма (Opheim) несколько схож с алгоритмом Реуманна-Виткама. В этом алгоритме мы рассматриваем все вершины в <tex>\varepsilon</tex> радиусе от первой, и строим луч из текущей и последней, попавшей в радиус. Если таких точек нет, то берется следующая за исходной. Последующие вершины упрощаются до тех пор, пока их расстояние до луча превосходит <tex>\varepsilon</tex> и радиальное расстояние до первой точке превосходит <tex>\varepsilon</tex>. Затем алгоритм продолжается для оставшихся точек до тех пор, пока не будет достигнута последняя.
+
[http://psimpl.sourceforge.net/opheim.html Алгоритм Опхейма] (Opheim) несколько схож с алгоритмом Реуманна-Виткама. В этом алгоритме мы рассматриваем все вершины в <tex>\varepsilon</tex> радиусе от первой, и строим луч из текущей и последней, попавшей в радиус. Если таких точек нет, то берется следующая за исходной.  
 +
 
 +
Последующие вершины упрощаются до тех пор, пока их расстояние до луча превосходит <tex>\varepsilon</tex> и радиальное расстояние до первой точки превосходит <tex>\varepsilon</tex>. Затем алгоритм продолжается для оставшихся точек до тех пор, пока не будет достигнута последняя.
  
 
На рисунке радиус, луч и максимальное радиальное расстояние отображены красными линиями и дугами. Точки попавшие в итоговую цепь отображены черным.
 
На рисунке радиус, луч и максимальное радиальное расстояние отображены красными линиями и дугами. Точки попавшие в итоговую цепь отображены черным.
Строка 138: Строка 142:
  
 
==Алгоритм Ланга==
 
==Алгоритм Ланга==
Алгоритм Ланга (Lang) определяет фиксированный размер поисковой области для упрощения. Две точки, что образуют поисковую область, составляют отрезок. Этот отрезок используется для расчета перпендикулярного расстояния до каждой промежуточной точки. Если рассчитанное расстояние больше заданного <tex>\varepsilon</tex>, область поиска будет уменьшен путем исключения ее последней точки. Этот процесс будет продолжаться, пока все рассчитанные расстояния не будут ниже заданного <tex>\varepsilon</tex>, или когда нет больше промежуточных точек. Все промежуточные точки удаляются, а новая область поиска определяется, начиная с последней точки в старой области.
+
[[Файл:La.png‎|200px|right]]
 +
[http://psimpl.sourceforge.net/lang.html Алгоритм Ланга] (Lang) определяет фиксированный размер поисковой области для упрощения. Две точки, что образуют поисковую область, составляют отрезок. Этот отрезок используется для расчета перпендикулярного расстояния до каждой промежуточной точки. Если рассчитанное расстояние больше заданного <tex>\varepsilon</tex>, область поиска будет уменьшен путем исключения ее последней точки.  
 +
 
 +
Этот процесс будет продолжаться, пока все рассчитанные расстояния не будут ниже заданного <tex>\varepsilon</tex>, или когда нет больше промежуточных точек. Все промежуточные точки удаляются, а новая область поиска определяется, начиная с последней точки в старой области.
  
Граница поисковой области помечена красной линией, допустимая область для упрощения - красной пунктирной линией, точки попавшие в итоговую цепь отображены черным.  
+
На рисунке граница поисковой области помечена красной линией, допустимая область для упрощения - красной пунктирной линией, точки попавшие в итоговую цепь отображены черным.
 +
<br clear="all"/>
 +
 
 +
==Алгоритм, сохраняющий топологию==
 +
Алгоритм сохраняющий топологию, как было упомянуто ранее, содержится в статье де Берга A New Approach to Subdivision Simplification, где расскрываются также детали реализации, здесь же описывается идея алгоритма. Также стоит обратить внимание, что исходная полигональная цепь должна быть без самопересечений.
 +
 
 +
Алгоритм делится на четыре основных этапа:
 +
*Создание графа <tex>G_1</tex>, в котором помимо исходных ребер, добавлены все возможные сокращенные ребра. Иначе говоря ребра, для который верно, что <tex>i < j</tex> и для любого <tex>t</tex>, такого что <tex>i < t < j</tex>, верно <tex>\rho(V_t, \overline{V_iV_j}) \le \varepsilon</tex>.
 +
*Создание графа <tex>G_2</tex>, в котором добавлены все возможные ребра, не нарушающие топологию. На этом этапе построение выполняется без учета <tex>\varepsilon</tex>.
 +
*Создание графа <tex> G = G_1 \cap G_2</tex>, в котором будет содержаться кратчайшая полигональная цепь без самопересечений по построению <tex>G_1</tex> и <tex>G_2</tex>.
 +
*Поиск кратчайшего пути в <tex>G</tex>, как в невзвешенном графе, этот путь и будет являться ответом на задачу.
  
 
==Ссылки==
 
==Ссылки==
Строка 146: Строка 163:
 
*[http://pers.narod.ru/algorithms/pas_dist_from_point_to_line.html Поиск расстояния от точки до отрезка]
 
*[http://pers.narod.ru/algorithms/pas_dist_from_point_to_line.html Поиск расстояния от точки до отрезка]
 
*[http://algolist.manual.ru/maths/geom/distance/pointline.php Поиск расстояния от точки до прямой]
 
*[http://algolist.manual.ru/maths/geom/distance/pointline.php Поиск расстояния от точки до прямой]
*[http://www.bowdoin.edu/~ltoma/teaching/cs350/spring06/Lecture-Handouts/hershberger92speeding.pdf Speeding Up the Douglas-Peucker Line-Simplification Algorithm]
+
*[http://www.bowdoin.edu/~ltoma/teaching/cs350/spring06/Lecture-Handouts/hershberger92speeding.pdf "Speeding Up the Douglas-Peucker Line-Simplification Algorithm"]
 +
*[http://www.ams.sunysb.edu/~jsbm/courses/545/melkman.pdf Алгоритм Мелкмана]
 
*[http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm Алгоритм Мелкмана]
 
*[http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm Алгоритм Мелкмана]
 
*[http://softsurfer.com/Archive/algorithm_0112/algorithm_0112.htm Двоичный поиск на выпуклой оболочке]
 
*[http://softsurfer.com/Archive/algorithm_0112/algorithm_0112.htm Двоичный поиск на выпуклой оболочке]
*[http://www.bowdoin.edu/~ltoma/teaching/cs350/spring06/Lecture-Handouts/deberg95new.pdf A New Approach to Subdivision Simplification]
+
*[http://www.bowdoin.edu/~ltoma/teaching/cs350/spring06/Lecture-Handouts/deberg95new.pdf "A New Approach to Subdivision Simplification"]
 
*[http://www.codeproject.com/Articles/114797/Polyline-Simplification#headingRD Алгоритмы и визуализатор упрощения полигональной цепи]
 
*[http://www.codeproject.com/Articles/114797/Polyline-Simplification#headingRD Алгоритмы и визуализатор упрощения полигональной цепи]
 +
 +
[[Категория: Вычислительная геометрия]]

Текущая версия на 19:21, 4 сентября 2022

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

Задача

Дана некоторая полилиния, заданная последовательностью точек [math] a_1, a_2, ..., a_n[/math], и некоторое [math]\varepsilon[/math]. Требуется найти цепь [math] a_1, a_i, a_j, ..., a_n [/math], являющейся подпоследовательностью исходной. Для этой цепи верно, что для всех [math]k[/math], таких что [math] i \lt k \lt j:[/math] [math]\rho(a_k, Segment(a_i, a_j)) \le \varepsilon[/math] для любых соседних [math]i[/math] и [math]j[/math].

Существует также альтернативная задача, в которой вместо [math]\varepsilon[/math] задано число [math]k[/math] вершин в итоговой цепи. В этом случае требуется составить цепь [math] a_1, a_i, a_j, ..., a_n [/math] заданной длины таким образом, что максимально необходимое [math]\varepsilon[/math] для условия [math] \rho(a_k, Segment(a_i, a_j)) \le \varepsilon[/math] было минимально.

Также упрощение можно выполнять с помощью введения новой полилинии, не сохраняющей точки исходной, но такая вариация задачи рассмотрена не будет.

Мотивация

Такая задача встречается при обработки векторной графики и построении карт. Например, есть цепь, несколько точек которой попадают в один и тот же пиксель. Очевидно, что тогда можно упростить все эти точки в одну. В этом случае и пригодится упрощение, одним из вариантов реализации которого является алгоритм Дугласа-Пекера (Douglas-Peucker).

В случае, когда у нас есть несколько устройств с разным dpi, например, монитор и принтер, то, взяв за [math]\varepsilon[/math] половину расстояния, которое помещается на одной из границ пикселя, мы можем растеризовать одну и ту же цепь для разных устройств.

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

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

Описание

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

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

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

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

Псевдокод

DouglasPeucker(int first, int last, double eps)

max = -infinity
index = -1
for (int i = first + 1; i < last; i++)
distance = dist(points[i], segment(points[first],points[last]))
if (distance > max && distance > eps)
max = distance, index = i
if(index == -1)
return
else
answer[index] = true
DouglasPeucker(first, index, eps)
DouglasPeucker(index, last, eps)

Пример

Example DP.png

Рассмотрим пример для точек, заданных на рисунке, где сплошная линия отражает исходную линию, и [math]\varepsilon = \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] Алгоритм завершен

Полилиния, полученная в результате работы алгоритма, отражается черной пунктирной линией.

Время работы

Ожидаемая сложность алгоритма может быть оценена выражением [math]\Theta(n\log n)[/math] в лучшем случае, когда номер наиболее удаленной точки всегда оказывается лексикографически центральным. Однако, в худшем случае сложность алгоритма составляет [math]O(n^2)[/math]. Это достигается, например, в случае, если номер наиболее удаленной точки всегда соседний к номеру граничной точки.

Замечания к алгоритму

Топология

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

В статье де Берга (de Berg) "A New Approach to Subdivision Simplification"(1995) приведен алгоритм, позволяющий решать чуть более общую задачу, чем текущая: упрощение полигональной цепи с учетом обязательных особых точек, не входящих в нее и с учетом топологии. Можно использовать алгоритм и для текущего случая, задав множество особых точек пустым. Время работы алгоритма при этом составит [math]O(n^2\log n)[/math]. Краткое описание алгоритма дано ниже.

Оптимальность

Оптимальный по количеству точек ответ
Ответ алгоритма Дугласа-Пекера

Алгоритм может находить не минимальный по количеству точек ответ. Рассмотрим пример, в котором исходная линия с некоторым приближением будет представлять полуокружность. Мы можем подобрать такое [math]\varepsilon[/math], что алгоритм добавит три точки помимо стартовой и конечной (точки через каждую четверть исходной линии), в то же время мы можем взять две точки через каждую треть исходной линии, для которых упрощение также верно.


Решение альтернативной задачи

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

Реализация

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

Поиск расстояния от точки до отрезка

Идея

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

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

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

Реализация

DistancePtoS1.png

Даны точка [math]O[/math] и отрезок, заданный точками [math]A[/math] и [math]B[/math].

Введём обозначения:

  • [math]R_1[/math] — отрезок [math][O; A][/math]
  • [math]R_2[/math] — отрезок [math][O; B][/math]
  • [math]R_{12}[/math] — отрезок [math][A; B][/math]

Если:

  • [math]|R_1| \ge \sqrt{|R_2|^2+|R_{12}|^2}[/math], то ответ это [math]|R_2|[/math], так как угол между [math]R_2[/math] и [math]R_{12}[/math] при данном условии [math] \ge 90^{\circ}[/math]
  • [math]|R_2| \ge \sqrt{|R_1|^2+|R_{12}|^2}[/math], то ответ это [math]|R_1|[/math], так как угол между [math]R_1[/math] и [math]R_{12}[/math] при данном условии [math] \ge 90^{\circ}[/math]
  • Оба предыдущих условия ложны, то [math]\operatorname{abs} (\frac{| \overrightarrow{R_{12}} \times \overrightarrow{R_1}|}{|\overrightarrow{R_{12}}|})[/math], где [math] \overrightarrow{R_{12}} = B - A[/math] и [math] \overrightarrow{R_1} = A - O[/math]. Это следует из формул для площади параллелограмма через векторное произведение и через произведения основания на высоту


Обзор ускорения работы алгоритма Дугласа-Пекера

Как описано выше, в худшем случае алгоритм работает за [math]O(n^2)[/math]. Можно внести дополнения, которые позволят получить [math]O(n\log n)[/math] в худшем случае. Ускорение основывается на уменьшении времени поиска наиболее удаленной вершины. Это можно осуществить благодаря идее о том, что наиболее удаленная вершина лежит на выпуклой оболочке полигональной цепи. Описание ускорения взято из статьи Хершберга(Hershberger) "Speeding Up the Douglas-Peucker Line-Simplification Algorithm" (1992).

Для построения выпуклой оболочки используется алгоритм Мелкмана, который работает для двумерной полигональной цепи без самопересечений за [math]O(n)[/math], строя все промежуточные выпуклые оболочки, которые пригодятся в дальнейшем.

После построения выпуклой оболочки используется бинарный поиск для нахождения наиболее удаленной вершины за [math]O(\log n)[/math]. Затем, если потребуется, действия повторятся рекурсивно, как и в оригинальном алгоритме, но заново строить оболочки не имеет смысла, так как промежуточные уже были построены. Использовав их, можно разбить текущую оболочку на две за [math]O(\log n)[/math].

В итоге получается, что в худшем случае [math]O(n)[/math] разбиений за [math]O(\log n)[/math] и поиск за [math]O(\log n)[/math], что дает [math]O(n\log n)[/math].

Замечания

К сожалению, у данного метода есть несколько недостатков по сравнению с оригинальным алгоритмом, некоторые из которых уже были упомянуты:

  • исходная цепь должна быть без самопересечений для использования алгоритма Мелкмана
  • ускорение подходит лишь для двумерного случая из-за способа построения выпуклой оболочки
  • в некоторых случаях оригинальный алгоритм Дугласа-Пекера работает быстрее (например в случае, когда цепь приближено является окружностью)

Алгоритм Реуманна-Виткама

Pw2.png

Алгоритм Реуманна-Виткама (Reumann-Witkam) определяет прямую через первые две точки цепи, последняя из последовательных точек начиная со второй, удаленных небольше чем на [math]\varepsilon[/math], соединяются прямой, а все промежуточные точки исключаются.

Алгоритм продолжится последовательно для оставшихся точек до тех пор, пока не будет достигнута последняя.

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

Алгоритм Опхейма

Op.png

Алгоритм Опхейма (Opheim) несколько схож с алгоритмом Реуманна-Виткама. В этом алгоритме мы рассматриваем все вершины в [math]\varepsilon[/math] радиусе от первой, и строим луч из текущей и последней, попавшей в радиус. Если таких точек нет, то берется следующая за исходной.

Последующие вершины упрощаются до тех пор, пока их расстояние до луча превосходит [math]\varepsilon[/math] и радиальное расстояние до первой точки превосходит [math]\varepsilon[/math]. Затем алгоритм продолжается для оставшихся точек до тех пор, пока не будет достигнута последняя.

На рисунке радиус, луч и максимальное радиальное расстояние отображены красными линиями и дугами. Точки попавшие в итоговую цепь отображены черным.

Алгоритм Ланга

La.png

Алгоритм Ланга (Lang) определяет фиксированный размер поисковой области для упрощения. Две точки, что образуют поисковую область, составляют отрезок. Этот отрезок используется для расчета перпендикулярного расстояния до каждой промежуточной точки. Если рассчитанное расстояние больше заданного [math]\varepsilon[/math], область поиска будет уменьшен путем исключения ее последней точки.

Этот процесс будет продолжаться, пока все рассчитанные расстояния не будут ниже заданного [math]\varepsilon[/math], или когда нет больше промежуточных точек. Все промежуточные точки удаляются, а новая область поиска определяется, начиная с последней точки в старой области.

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

Алгоритм, сохраняющий топологию

Алгоритм сохраняющий топологию, как было упомянуто ранее, содержится в статье де Берга A New Approach to Subdivision Simplification, где расскрываются также детали реализации, здесь же описывается идея алгоритма. Также стоит обратить внимание, что исходная полигональная цепь должна быть без самопересечений.

Алгоритм делится на четыре основных этапа:

  • Создание графа [math]G_1[/math], в котором помимо исходных ребер, добавлены все возможные сокращенные ребра. Иначе говоря ребра, для который верно, что [math]i \lt j[/math] и для любого [math]t[/math], такого что [math]i \lt t \lt j[/math], верно [math]\rho(V_t, \overline{V_iV_j}) \le \varepsilon[/math].
  • Создание графа [math]G_2[/math], в котором добавлены все возможные ребра, не нарушающие топологию. На этом этапе построение выполняется без учета [math]\varepsilon[/math].
  • Создание графа [math] G = G_1 \cap G_2[/math], в котором будет содержаться кратчайшая полигональная цепь без самопересечений по построению [math]G_1[/math] и [math]G_2[/math].
  • Поиск кратчайшего пути в [math]G[/math], как в невзвешенном графе, этот путь и будет являться ответом на задачу.

Ссылки