Straight skeleton — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм с изпользованием SLAV)
м (rollbackEdits.php mass rollback)
 
(не показаны 92 промежуточные версии 3 участников)
Строка 1: Строка 1:
Существует целый класс структур типа <tex>\mathrm{skeleton}</tex>, которые описывают базовые топологические свойства объектов. Структура <tex>\mathrm{straight}\ \mathrm{skeleton}</tex> была придумала Oswin Aichholzer. Она используются в различных практических задачах (проектирование крыш для зданий) и для доказательства некоторых теорем<ref>[http://en.wikipedia.org/wiki/Fold-and-cut_theorem Wikipedia {{---}} Fold-and-cut theorem]</ref>.
+
Структура <tex>\mathrm{straight}\ \mathrm{skeleton}</tex> была придумана Oswin Aichholzer. Она используется в различных практических задачах (проектирование крыш для зданий), для доказательства некоторых теорем<ref>[http://en.wikipedia.org/wiki/Fold-and-cut_theorem Wikipedia {{---}} Fold-and-cut theorem]</ref>, в обработке изображений {{---}} эрозия и дилатация, но самое главное {{---}} можно оффсетить полигоны и упрощать их.
 
== Топологические свойства ==
 
== Топологические свойства ==
{{Определение
+
Далее будет дано процедурное определение <tex>\mathrm{straight}\ \mathrm{skeleton}</tex>.
|id=defss
 
|definition='''Straight skeleton''' (Angular Bisector Network, ABN) полигона без самопересечений называется планарный [[Основные определения теории графов | граф]], определяющий разбиение полигона на регионы, границами которых являются стороны полигона, биссектрисы углов и отрезки, соединяющие вершины straight skeleton, образовавшиеся в результате сжатия полигона.
 
}}
 
  
Опишем подробней, как получается такое разбиение. Мы можем представить, будто все стороны прямоугольника параллельно двигаются внутрь с одинаковой постоянной скоростью, то есть многоугольник как бы сжимается внутрь. Тогда {{Acronym | вершины будут двигаться вдоль биссектрис | Очевидный факт}}, а точки пересечения биссектрис будут являться точками, в которых рёбра полностью сократились (выродились в точку). В каждый момент времени от начала движения рёбер мы получаем слоистую структуру (рис 1.). На рис. 2 синим цветом выделен <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> {{---}} множество отрезков, образованных точками пересечения при движении сторон полигона. Чем-то структура похожа на строение крыши в домах (рис. 3). И для решения этой задачи как раз <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> и может применяться: по стенам здания необходимо спроектировать его крышу.
+
Можно представить, будто все стороны многоугольника параллельно двигаются внутрь с одинаковой постоянной скоростью, то есть многоугольник как бы сжимается внутрь. Тогда {{Acronym | вершины будут двигаться вдоль биссектрис внутренних углов | Очевидный факт}}, а точки пересечения биссектрис будут являться точками, в которых рёбра полностью сократятся (выродятся в точку). В каждый момент времени от начала движения рёбер получается слоистая структура (рис 1.). На рис. 2 синим цветом выделен <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> {{---}} множество отрезков, образованных точками пересечения при движении сторон полигона. Эта структура напоминает построение крыши для дома (рис. 3), и, в самом деле, скелетон применяется для решения подобных задач: по стенам здания необходимо спроектировать его крышу.
  
 
{| cellpadding="3" style="margin-left: auto; margin-right: auto;"
 
{| cellpadding="3" style="margin-left: auto; margin-right: auto;"
Строка 16: Строка 13:
 
[[Файл:Straight_roof.png‎|500px|center|thumb|Проектирование крыши здания по готовым стенам]]
 
[[Файл:Straight_roof.png‎|500px|center|thumb|Проектирование крыши здания по готовым стенам]]
  
Процесса стягивания многоугольника продолжается до тех пор, пока происходят его топологические изменения, то есть меняется число вершин в стянутом многоугольнике, и таким образом появляются новые вершины дерева <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>. Существуют два типа изменений, в ходе которых образуются новые вершины дерева:
+
Процесс стягивания многоугольника продолжается до тех пор, пока все рёбра не сожмутся в точку, то есть пока меняется число вершин в стянутом многоугольнике, и таким образом появляются новые вершины <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>. Существуют два типа изменений, в ходе которых они образуются:
 
* <tex> Edge\ event </tex> {{---}} данное изменение происходит, когда сторона многоугольника полностью стягивается, делая соседние стороны инцидентными.
 
* <tex> Edge\ event </tex> {{---}} данное изменение происходит, когда сторона многоугольника полностью стягивается, делая соседние стороны инцидентными.
* <tex> Split\ event </tex> {{---}} происходит, когда ребро разбивается на два новых ребра, исходящих из точки преломления старого. Такое событие происходит на биссектрисе вогнутой вершины многоугольника. И тогда стягиваемая многоугольником область может разбивться на две непересекающиеся многоугольные области.
+
* <tex> Split\ event </tex> {{---}} происходит, когда ребро разбивается на два новых ребра, исходящих из точки преломления старого. Такое событие происходит на биссектрисе вогнутой вершины многоугольника. И тогда стягиваемая многоугольником область может разбиваться на две непересекающиеся многоугольные области.
  
На рисунке <tex>edge\ event'</tex>ы изображены зелёным кругом, а <tex>split\ event'</tex>ы {{---}} красным прямоугольником.
+
На рисунке <tex>edge\ event'</tex>ы отмечены зелёными окружностями, а <tex>split\ event'</tex>ы {{---}} красными квадратами.
  
 
[[Файл:skeleton_event_example.jpg|400px]]
 
[[Файл:skeleton_event_example.jpg|400px]]
  
Таким образом, <tex> event' </tex>ы соответствуют внутренним вершинам <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>, гранями являются области многоугольника, заметаемые сторонами многоугольника в процессе стягивания, дуги <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> соединяют либо две внутренние вершины либо внутреннюю вершину с листом {{---}} вершиной многоугольника.
+
Таким образом, можно предъявить соответствие между элементами <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> и происходящими событиями:
 +
* внутренние вершины {{---}} <tex> event' </tex>ы,
 +
* листья {{---}} вершины исходного многоугольника,
 +
* грани {{---}} области многоугольника, заметаемые сторонами многоугольника в процессе стягивания,
 +
* дуги {{---}} соединяют либо две внутренние вершины, либо внутреннюю вершину с листом.
  
 
Стоит также отметить, что в общем случае <tex> split\ event'</tex>ы могут быть нетривиальными. На рисунке ниже в случае <tex> (c) </tex> в вершине <tex> p </tex> совпали <tex>split\ event</tex> из вершины <tex> u </tex> и  ребра <tex> e </tex> и <tex> edge\ event</tex> ребра <tex> uv </tex>, а в случае <tex> (d) </tex> совпали два <tex> split\ event'</tex>а вершин <tex> u_1 </tex> и <tex> u_2 </tex>. Случаи <tex> (a) </tex> и <tex> (b) </tex> {{---}} простые <tex> edge </tex> и <tex> split\ event'</tex>ы.
 
Стоит также отметить, что в общем случае <tex> split\ event'</tex>ы могут быть нетривиальными. На рисунке ниже в случае <tex> (c) </tex> в вершине <tex> p </tex> совпали <tex>split\ event</tex> из вершины <tex> u </tex> и  ребра <tex> e </tex> и <tex> edge\ event</tex> ребра <tex> uv </tex>, а в случае <tex> (d) </tex> совпали два <tex> split\ event'</tex>а вершин <tex> u_1 </tex> и <tex> u_2 </tex>. Случаи <tex> (a) </tex> и <tex> (b) </tex> {{---}} простые <tex> edge </tex> и <tex> split\ event'</tex>ы.
Строка 30: Строка 31:
 
[[Файл:Event_example.png]]
 
[[Файл:Event_example.png]]
  
Задача построения такого <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> является частным случаем задачи построения  <tex> \mathrm{weighted}\ \mathrm{straight}\ \mathrm{skeleton} </tex>, где каждому ребру можно задавать ''вес'', то есть скорость движения ребра. И эта скорость может быть даже отрицательной. Таким образом можно оффсетить полигоны и решать задачу [[Visibility graph и motion planning | motion planning]]. Задача <tex> \mathrm{weighted}\ \mathrm{straight}\ \mathrm{skeleton} </tex> является более сложной, и здесь рассматриваться не будет.
+
Задача построения такого <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> является частным случаем задачи построения  <tex> \mathrm{weighted}\ \mathrm{straight}\ \mathrm{skeleton} </tex>, где каждому ребру можно задавать ''вес'', то есть скорость движения ребра. И эта скорость может быть даже отрицательной. Но задача построения <tex>\mathrm{WSS}</tex> является в общем случае неопределённой. В процессе её решения возникают неоднозначности<ref>[http://twak.blogspot.ru/2009/05/ambiguous-weighted-skeleton.html Ambiguous weighted skeleton]</ref>. Задача <tex> \mathrm{weighted}\ \mathrm{straight}\ \mathrm{skeleton} </tex> является более сложной, и здесь рассматриваться не будет.
 +
 
 +
Алгоритм построения <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> можно модифицировать, чтобы ''волновой фронт'' шёл  от полигона. То есть сначала можно построить <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>, тем самым упростив структуру полигона и сделав его более "гладким", а затем распространить волну в обратную сторону.
  
 
== Свойства Straight skeleton ==
 
== Свойства Straight skeleton ==
Из процесса построения <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> следует, что он является [[Укладка графа на плоскости#defplanar | планарным графом]]. Ранее уже упоминалось, что он также является [[Дерево, эквивалентные определения#tree |деревом]]. Будем обозначать <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> простого полигона без самопересечений <tex> P </tex>, в котором <tex> n </tex> вершин, как <tex> S(P) </tex>. Тогда справедливы следующие леммы:
+
Из процесса построения <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> следует, что он является [[Укладка графа на плоскости#defplanar | планарным графом]]. Ранее уже упоминалось, что он также является [[Дерево, эквивалентные определения#tree |деревом]]. Будем обозначать <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> простого полигона без самопересечений <tex> P </tex>, в котором <tex> n </tex> вершин, как <tex> S(P) </tex>. Тогда справедлива следующая лемма:
  
 
{{Лемма
 
{{Лемма
 
|id = lemma1  
 
|id = lemma1  
 
|about=1
 
|about=1
|statement=<tex> S(P) </tex> является деревом, содержит <tex> n </tex> граней, не более <tex> n - 2 </tex> внутренние вершины и не более <tex> 2 n - 3 </tex> рёбер.
+
|statement=<tex> S(P) </tex> является деревом, содержит <tex> n </tex> граней, не более <tex> n - 2 </tex> внутренних вершин и не более <tex> 2 n - 3 </tex> рёбер.
 
|proof=
 
|proof=
 +
 +
[[Файл:skeleton_lemma.png]]
 +
 
Каждая грань <tex> f(e) </tex> начинает образовываться во время стягивания ребра <tex> e </tex>, и даже если на ребре произошёл <tex> split\ event </tex>, сама грань не могла разделиться. Построение грани <tex> f(e) </tex> завершается, когда ребро <tex> e </tex> полностью стягивается. И это ребро дальше не может появиться снова, поэтому граней в <tex> S(P) </tex> столько, сколько сторон в многоугольнике, то есть ровно <tex> n </tex>.
 
Каждая грань <tex> f(e) </tex> начинает образовываться во время стягивания ребра <tex> e </tex>, и даже если на ребре произошёл <tex> split\ event </tex>, сама грань не могла разделиться. Построение грани <tex> f(e) </tex> завершается, когда ребро <tex> e </tex> полностью стягивается. И это ребро дальше не может появиться снова, поэтому граней в <tex> S(P) </tex> столько, сколько сторон в многоугольнике, то есть ровно <tex> n </tex>.
  
То, что <tex> S(P) </tex> является деревом, легко доказывается по индукции. База верна, когда внутренняя вершина всего одна. Тогда у <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> листьями будут вершины многоугольника. Такой граф очевидным образом будет деревом. Если в <tex> \mathrm{straight}\ \mathrm{skeleton}\ k </tex> внутренних вершин, то рассмотрим самый первый <tex> edge\ event</tex>. Он закончился в какой-то внутренней вершине <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>, у неё есть смежные листья {{---}} вершины, инцидентные этому ребру, {{---}} и из неё достижимы другие <tex> \mathrm{straight}\ \mathrm{skeleton}' </tex>ы, с не более чем <tex> k - 1 </tex> внутренними вершинами, и они являются деревьями по предположению индукцию. Тогда получаем, что <tex> S(P) </tex> для <tex> k </tex> вершин тоже будет деревом.
+
То, что <tex> S(P) </tex> является деревом, легко доказывается по индукции числа вершин в многоугольнике.  
 +
 
 +
'''База:''' многоугольник является треугольником, в его <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> будет одна внутренняя вершина {{---}} точка пересечения биссектрис, листьями будут вершины треугольника. Такой граф, очевидно, будет деревом.  
 +
 
 +
'''Переход:''' пусть для всех многоугольников с количеством вершин меньше <tex>k\ S(P)</tex> будет деревом. Рассмотрим самый первый <tex>event</tex> в многоугольнике из <tex>k</tex> вершин.  
 +
* Если это <tex>edge\ event</tex>, то появится новая вершина, которую мы соединим с инцидентными ребру вершинами, а также с какой-то вершиной <tex>\mathrm{straight}\ \mathrm{skeleton} </tex> полигона из <tex>k - 1</tex> вершин. Получившийся граф будет деревом.
 +
* Если это <tex>split\ event</tex>, то новая вершина соединяется с одной вершиной исходного полигона и с двумя вершинами <tex>\mathrm{straight}\ \mathrm{skeleton} </tex> для полигонов, в которых меньше <tex> k </tex> вершин. В этом случае также получаем дерево.
 +
 
  
 
Внутренние вершины в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> имеют [[Основные определения теории графов#def_graph_degree_1 | степень]] не меньше <tex> 3 </tex> {{---}} простой перебор всех случаев <tex> event'</tex>ов (степень будет больше, если в одной вершине совпало несколько событий). Так как <tex> S(P) </tex> имеет <tex>n</tex> листьев, то внутренних вершин будет не больше <tex> n - 2 </tex>, а так как <tex> S(P) </tex> является деревом, то рёбер у него будет не более <tex> 2 n  - 3 </tex>.
 
Внутренние вершины в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> имеют [[Основные определения теории графов#def_graph_degree_1 | степень]] не меньше <tex> 3 </tex> {{---}} простой перебор всех случаев <tex> event'</tex>ов (степень будет больше, если в одной вершине совпало несколько событий). Так как <tex> S(P) </tex> имеет <tex>n</tex> листьев, то внутренних вершин будет не больше <tex> n - 2 </tex>, а так как <tex> S(P) </tex> является деревом, то рёбер у него будет не более <tex> 2 n  - 3 </tex>.
 
}}
 
}}
  
'''Замечание:''' если мы рассмотрим <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> в какой-то момент времени, то он вполне может содержать циклы (это видно на рисунке ниже). Однако его конечная структура будет деревом.
+
Ещё один пример:
  
 
[[Файл:Skeleton_example1.png|500px]]
 
[[Файл:Skeleton_example1.png|500px]]
  
 
== Алгоритм с изпользованием SLAV ==
 
== Алгоритм с изпользованием SLAV ==
Далее будет описан алгоритм, придуманный Petr Felkel, который строит <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> за время <tex> \mathcal{O}(nm + n \log n)</tex>, или просто <tex> \mathcal{O}(n^2)</tex>, где <tex> n </tex> {{---}} общее число вершин в полигоне, <tex> m </tex> {{---}} число вогнутых вершин в полигоне. Немного модифицированный этот алгоритм используется в открытой библиотеке вычислительной геометрии CGAL<ref>[http://cmp.felk.cvut.cz/~xobdrzal/publications/bachelorthesis.pdf Stepan Obdrazalek, "The Angular bisector network Implementation and the CGAL library"]</ref>. Однако этот алгоритм всё равно ещё достаточно медленный. В реальной жизни используют его модификации или более сложные алгоритмы.
+
Далее будет описан алгоритм, придуманный Petr Felkel, который строит <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> за время <tex> \mathcal{O}(n^2 \log n)</tex>, где <tex> n </tex> {{---}} общее число вершин в полигоне. В оригинальной статье этому алгоритму даётся асимптотическая оценка <tex> \mathcal{O}(nm + n \log n)</tex>, или просто <tex> \mathcal{O}(n^2)</tex>, где <tex> m </tex> {{---}} число невыпуклых вершин в полигоне. Однако в статье содержатся ошибки, поэтому данная в ней оценка неверна.
  
Сначала алгоритм будет рассмотрен на простом случае {{---}} выпуклом многоугольнике, {{---}} а потом на невыпуклом многоугольнике.
+
Сначала алгоритм будет рассмотрен на простом случае {{---}} выпуклом многоугольнике, {{---}} а потом на невыпуклом.
  
 
=== Выпуклый полигон ===
 
=== Выпуклый полигон ===
В случае выпуклого многоугольника возникают только <tex> edge\ event'</tex>ы по определению. Поэтому просто алгоритм можно описать следующим образом: найдём точки пересечения биссектрис многоугольника для каждой вершины со всеми соседними вершинами, возьмём такую точку, в которой произойдёт самый первый  <tex> edge\ event</tex>, добавим полученную вершину в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>, соеденим её с вершинами ребра, которое исчезло в процессе текущего <tex> edge\ event'</tex>а, а потом перестроим полигон, создав новую вершину и подвинув все остальные вдоль биссектрис на одинаковое расстояние. Будем продолжать этот процесс до тех пор, пока многоугольник не превратится в треугольник.
+
В случае выпуклого многоугольника возникают только <tex> edge\ event'</tex>ы по определению. Объяснить алгоритм можно простым образом: найдём точки пересечения биссектрис многоугольника для каждой вершины со всеми соседними вершинами, возьмём такую точку, в которой произойдёт самый первый  <tex> edge\ event</tex>, добавим полученную вершину в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>, соединим её с вершинами ребра, которое исчезло в процессе текущего <tex> edge\ event'</tex>а, а потом перестроим полигон, создав новую вершину и подвинув все остальные вдоль биссектрис на одинаковое расстояние. Будем продолжать этот процесс до тех пор, пока многоугольник не превратится в треугольник.
  
Теперь реализуем этот алгоритм более эффективно. Для этого мы будем использовать специальную структуру данных {{---}} <tex> \mathrm{SLAV}</tex> (set of circular lists of active vertices). Эта структура хранит цикл всех вершин для внешней грани, а так же цикл для каждой дыры многоугольника и для всех многоугольников, возникающих в процессе построения <tex> S(P) </tex>. В данном случае у нас будет просто <tex> \mathrm{LAV}</tex> {{---}} [[Список#Циклический список | циклический список]] всех вершин многоугольника.
+
Теперь реализуем этот алгоритм более эффективно. Для этого мы будем использовать специальную структуру данных {{---}} <tex> \mathrm{SLAV}</tex> (set of circular lists of active vertices). Эта структура хранит цикл всех вершин для внешней грани, а также цикл для каждой дырки многоугольника и для всех многоугольников, возникающих в процессе построения <tex> S(P) </tex>. В данном случае у нас будет просто <tex> \mathrm{LAV}</tex> {{---}} [[Список#Циклический список | циклический список]] всех вершин многоугольника.
  
 
[[Файл:skeleton_lav.jpg]]
 
[[Файл:skeleton_lav.jpg]]
  
В таком списке частично найденного <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> вершины имеют указатели на следующую и предыдущую вершину в порядке обхода контура, а так же указатели на инцидентные рёбра. Если представить процесс стягивания многоугольника, как будто у нас уже построена для него крыша, а мы двигаем вверх некоторую заметающую плоскость, где пересечение крыши и плоскости будет обозначать текущий слой, то можно заметить, что область полигона разбивается на несколько частей. Каждой части будет соответствовать свой <tex> \mathrm{LAV}</tex>, отсюда нам и нужен <tex> \mathrm{SLAV}</tex>.
+
В таком списке частично найденного <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> вершины имеют указатели на следующую и предыдущую вершины в порядке обхода контура, а также указатели на инцидентные рёбра.
  
 
==== Алгоритм для выпуклых полигонов ====
 
==== Алгоритм для выпуклых полигонов ====
Далее считаем, что полигон представлен рёбрами вдоль движения по контуру полигона против часовой стрелки.
+
Далее считаем, что полигон представлен рёбрами, направленными вдоль движения по контуру против часовой стрелки.
  
 
'''Шаг 1.''' Инициализация:  
 
'''Шаг 1.''' Инициализация:  
:<tex>(a)</tex> Поместим все вершины многоугольника <tex> V_1, V_2 \dots V_n </tex> в двусвязный циклический список в порядке обхода вдоль контура. Все вершины в <tex> \mathrm{LAV}</tex> считаются активными сейчас.
+
:<tex>(a)</tex> Поместим все вершины многоугольника <tex> V_1, V_2 \dots V_n </tex> в двусвязный циклический список в порядке обхода вдоль контура. Все вершины в <tex> \mathrm{LAV}</tex> сейчас считаются активными.
 
:<tex>(b)</tex> Для каждой вершины <tex> V_i </tex> в  <tex> \mathrm{LAV}</tex> добавим указатели на инцидентные рёбра <tex> e_{i-1} = V_{i-1}V_i</tex> и <tex> e_i = V_i V_{i+1}</tex>, а также найдём луч биссектрисы <tex> b_i </tex>.
 
:<tex>(b)</tex> Для каждой вершины <tex> V_i </tex> в  <tex> \mathrm{LAV}</tex> добавим указатели на инцидентные рёбра <tex> e_{i-1} = V_{i-1}V_i</tex> и <tex> e_i = V_i V_{i+1}</tex>, а также найдём луч биссектрисы <tex> b_i </tex>.
:<tex>(c)</tex> Для каждой вершины <tex> V_i </tex> найдём ближайшее пересечение биссектрисы <tex> b_i </tex> с лучами <tex> b_{i-1} </tex> и <tex> b_{i+1} </tex>. Если это пересечение существует, то положим его в [[Двоичная куча | приоритетную очередь]] согласно <tex> L(e_i) </tex> {{---}} расстоянию от точки пересечения до одного из рёбер, инцидентных вершине <tex> V_i </tex>. Для каждой точки пересечения <tex> I_i </tex> будем так же хранить два указателя на вершины <tex> V_a </tex> и <tex> V_b </tex> {{---}} начала лучей биссектрис, которые пересекаются в точке <tex> I_i </tex>. Эти указатели понадобятся в будущем, когда нужно будет определять соответствующие вершинам рёбра <tex> e_a, e_b </tex> (см. рисунок ниже).
+
:<tex>(c)</tex> Для каждой вершины <tex> V_i </tex> найдём ближайшее пересечение биссектрисы <tex> b_i </tex> с биссектрисами <tex> b_{i-1} </tex> и <tex> b_{i+1} </tex>. Если это пересечение существует, то поместим его в [[Двоичная куча | приоритетную очередь]] согласно <tex> L(e_i) </tex> {{---}} расстоянию от точки пересечения до одного из рёбер, инцидентных вершине <tex> V_i </tex>. Для каждой точки пересечения <tex> I_i </tex> будем ещё хранить два указателя на вершины <tex> V_a </tex> и <tex> V_b </tex> {{---}} начала лучей биссектрис, которые пересекаются в точке <tex> I_i </tex>. Эти указатели понадобятся в будущем, когда нужно будет определять соответствующие вершинам рёбра <tex> e_a, e_b </tex> (см. рисунок ниже).
'''Шаг 2.''' Следующие действия выполняются в цикле, пока приоритетная очередь не пустая:
+
'''Шаг 2.''' Следующие действия выполняются в цикле, пока приоритетная очередь не пуста:
 
:<tex>(a)</tex> Извлечём точку пересечения <tex> I </tex> из приоритетной очереди.
 
:<tex>(a)</tex> Извлечём точку пересечения <tex> I </tex> из приоритетной очереди.
:<tex>(b)</tex> Если вершины  <tex> V_a </tex> и <tex> V_b </tex>, соответствующие данной точке пересечения помечены как обработанные, то переходим к следующей итерации цикла шага 2. Это означает, что ребро между данными вершинами полностью стянулось (обработанные вершины и стянутые рёбра помечены крестом на рисунке ниже).
+
:<tex>(b)</tex> Если вершины  <tex> V_a </tex> и <tex> V_b </tex>, соответствующие данной точке пересечения, помечены как обработанные, то переходим к следующей итерации цикла шага 2. Это означает, что ребро между данными вершинами полностью стянулось (обработанные вершины и стянутые рёбра помечены крестом на рисунке ниже). Эту проверку необходимо делать из-за того, что мы могли поместить в очередь обработанные вершины в момент получения новых <tex>event'</tex>ов.
:<tex>(c)</tex> Если осталось всего три вершины <tex> V_a, V_b, V_c </tex>, то добавим в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> рёбра <tex> IV_a, IV_b, IV_c </tex>. В случае выпуклого многоугольника в этом месте можно завершить алгоритм. Но в общем случае нужно будет перейти к началу цикла снова.
+
:<tex>(c)</tex> Если осталось всего три вершины <tex> V_a, V_b, V_c </tex>, то добавим в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> рёбра <tex> IV_a, IV_b, IV_c </tex>. В случае выпуклого многоугольника в этом месте можно завершить алгоритм. Но в общем случае нужно будет снова перейти к началу цикла.
 
:<tex>(d)</tex> Добавим в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> рёбра <tex> IV_a, IV_b </tex>.
 
:<tex>(d)</tex> Добавим в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> рёбра <tex> IV_a, IV_b </tex>.
 
:<tex>(e)</tex> Теперь необходимо модифицировать <tex> \mathrm{LAV}</tex> (детали на рисунке ниже):
 
:<tex>(e)</tex> Теперь необходимо модифицировать <tex> \mathrm{LAV}</tex> (детали на рисунке ниже):
 
::* пометим вершины <tex> V_a </tex> и <tex> V_b </tex> как обработанные (напомню, что они обозначаются крестом на рисунке к данному алгоритму),
 
::* пометим вершины <tex> V_a </tex> и <tex> V_b </tex> как обработанные (напомню, что они обозначаются крестом на рисунке к данному алгоритму),
 
::* создадим новую вершину <tex> V </tex> в точке пересечения <tex> I </tex> (отмечена квадратиком на рисунке),
 
::* создадим новую вершину <tex> V </tex> в точке пересечения <tex> I </tex> (отмечена квадратиком на рисунке),
::* добавим вершину <tex> V </tex> в <tex> \mathrm{LAV}</tex>, то есть между предыдущем к <tex> V_a </tex> и следующим к <tex> V_b </tex> узлами,
+
::* добавим вершину <tex> V </tex> в <tex> \mathrm{LAV}</tex>, то есть между предыдущим к <tex> V_a </tex> и следующим к <tex> V_b </tex> узлами,
 
::* добавим вершине <tex> V </tex> указатели на соответствующие рёбра <tex> e_a </tex> и <tex> e_b </tex>.
 
::* добавим вершине <tex> V </tex> указатели на соответствующие рёбра <tex> e_a </tex> и <tex> e_b </tex>.
 
:<tex>(f)</tex> Посчитаем дополнительные величины для вершины <tex> V </tex>:
 
:<tex>(f)</tex> Посчитаем дополнительные величины для вершины <tex> V </tex>:
 
::* луч биссектрисы <tex> b </tex> между рёбрами <tex> e_a </tex> и <tex> e_b </tex>,
 
::* луч биссектрисы <tex> b </tex> между рёбрами <tex> e_a </tex> и <tex> e_b </tex>,
::* точки пересечения луча b с соседями <tex> V </tex> в <tex> \mathrm{LAV}</tex>, как в шаге <tex> 1c </tex>
+
::* точки пересечения биссектрисы <tex>b</tex> с биссектрисами вершин, соседних к <tex> V </tex> в <tex> \mathrm{LAV}</tex>, как в шаге <tex> 1c </tex>,
::* сохраним ближайшие точки пересечения в приоритетной очереди.
+
::* сохраним ближайшие точки пересечения в приоритетной очереди. Ключом точки пересечения в приоритетной очереди будет расстояние <tex> L(e_i) </tex> до стянутого ребра <tex> e_i </tex>.
  
 
[[Файл:skeleton_convex_example.png|600px]]
 
[[Файл:skeleton_convex_example.png|600px]]
 
Заметим, что нам не нужно пересчитывать все расстояния в очереди приоритетов. Если мы стянем полигон до первого события исчезания ребра, то относительный порядок остальных событий не изменится. Нам необходимо только вставить новые точки пересечения в правильные места. Это можно эффективно сделать, если использовать структуру данных типа [[Список с пропусками | skip list]].
 
  
 
В этом случае асимптотика алгоритма составляет <tex> \mathcal{O}(n \log n)</tex>, так как на каждой итерации цикла нам нужно положить константное число элементов в очередь, а итераций цикла не больше <tex> n </tex>.
 
В этом случае асимптотика алгоритма составляет <tex> \mathcal{O}(n \log n)</tex>, так как на каждой итерации цикла нам нужно положить константное число элементов в очередь, а итераций цикла не больше <tex> n </tex>.
  
 
==== Частные случаи ====  
 
==== Частные случаи ====  
Частным случаем в алгоритме может быть совпадение нескольких <tex> edge\ event'</tex>ов в одной точке. Эти совпадения добавляются в шагах <tex> 1c </tex> и <tex> 2f </tex>, но могут быть относительно легко обработаны в шаге <tex> 2b </tex>.  
+
Частным случаем в алгоритме может быть совпадение нескольких <tex> edge\ event'</tex>ов в одной точке. Эти совпадения добавляются в шагах <tex> 1c </tex> и <tex> 2f </tex>, так как точки пересечения добавляются только в них, но могут быть относительно легко обработаны в шаге <tex> 2b </tex>. Или мы можем считать, что между <tex> edge\ event'</tex>ами в одной точке будут рёбра нулевого веса в полученном <tex> S(P) </tex>, а затем можно просто избавиться от лишних вершин в результирующей структуре.
 +
 
 +
Также может случиться, что какие-то рёбра не стянулись в итоге в одну вершину, а слились. Такое возможно, если какие-то стороны полигона были изначально параллельны (этот случай легко увидеть на прямоугольнике, не являющемся квадратом). С этим частным случаем можно разобраться в шаге <tex> 2c </tex>, проверив, не совпала ли одна из трёх вершин с другой. В выпуклом многоугольнике слияние двух рёбер может произойти только один раз (что неправда для невыпуклого многоугольника), поэтому с таким случаем несложно разобраться.
  
Также может случиться, что какие-то рёбра не стянулись в итоге в одну вершину, а слились. Такое возможно, если какие-то стороны полигона были изначально параллельны (этот случай легко увидеть на прямоугольнике, не являющемся квадратом). С этим частным случаем можно разобраться в шаге <tex> 2c </tex>, проверив, не совпала ли одна из трёх вершин с другой. В выпуклом многоугольнике слияние двух рёбер может произойти только один раз (что неправда для невыпуклого многоугольника), поэтому здесь несложно разобраться с таким случаем.
 
 
=== Невыпуклый полигон ===
 
=== Невыпуклый полигон ===
 
Основной принцип для невыпуклых полигонов такой же. Только с вершиной ещё хранится дополнительный атрибут, обозначающий событие, которое в ней произошло: <tex> edge\ event</tex> или <tex> split\ event</tex>.
 
Основной принцип для невыпуклых полигонов такой же. Только с вершиной ещё хранится дополнительный атрибут, обозначающий событие, которое в ней произошло: <tex> edge\ event</tex> или <tex> split\ event</tex>.
 +
 +
Если представить процесс стягивания многоугольника, как будто у нас уже построена для него крыша, а мы двигаем вверх некоторую заметающую плоскость, где пересечение крыши и плоскости будет обозначать текущий слой, то можно заметить, что область полигона разбивается на несколько частей. Каждой части будет соответствовать свой <tex> \mathrm{LAV}</tex>, отсюда нам и нужен <tex> \mathrm{SLAV}</tex>.
  
 
[[Файл:skeleton_split_event_example.png|400px]]
 
[[Файл:skeleton_split_event_example.png|400px]]
  
Наличие невыпуклой вершины может привести (а может и не привести) к разделению внутренней области. Невыпуклая вершина может так же участвовать в обычном <tex> edge\ event'</tex>е (точка <tex> A </tex> на рисунке выше). В таком случае <tex> edge\ event'</tex>ы обрабатываются так же, как и в алгоритме с выпуклым многоугольником.
+
Наличие невыпуклой вершины может привести (а может и не привести) к разделению внутренней области. Невыпуклая вершина может участвовать в обычном <tex> edge\ event'</tex>е (точка <tex> A </tex> на рисунке выше). <tex> Edge\ event'</tex>ы в случае невыпуклогого многоугольника обрабатываются так же, как и в алгоритме с выпуклым многоугольником.
  
 
Посмотрим теперь, что делать с точкой <tex> B </tex>, в которой возникает <tex> split\ event</tex>.
 
Посмотрим теперь, что делать с точкой <tex> B </tex>, в которой возникает <tex> split\ event</tex>.
Строка 109: Строка 123:
 
[[Файл:skeleton_b_point_coord.png|500px]]
 
[[Файл:skeleton_b_point_coord.png|500px]]
  
В простейшем случае точка <tex> B </tex> появляется, когда "волновой фронт" распространения движения рёбер от невыпуклой вершины натыкается на встречный фронт противолежащего ребра. В такой момент возникает <tex> split\ event</tex>. Поэтому точка <tex> B </tex> может быть изначально охарактеризована, как точка, находящаяся на одном расстоянии от противолежащего угла и прямых, содержащих рёбра невыпуклой вершины. Задача состоит в том, чтобы найти это самое противолежащее ребро (случай <tex> a) </tex> на рисунке выше). Но как показывает случай <tex> b) </tex>, простой тест на пересечение ребра и биссектрисы невыпуклой вершины не может быть использован (в этом случае луч биссектрисы пересекает сразу два ребра, непонятно, с каким из них произойдёт <tex> split\ event</tex>). Поэтому необходимо ещё проверять, что точка <tex> B </tex> лежит между лучами <tex> b_i </tex> и <tex> b_{i+1} </tex>, идущих из вершин, инцидентных противолежащему ребру <tex> e_i </tex>.  
+
В простейшем случае точка <tex> B </tex> появляется, когда "волновой фронт" распространения движения рёбер от невыпуклой вершины натыкается на встречный фронт противолежащего ребра. В такой момент возникает <tex> split\ event</tex>. Поэтому точка <tex> B </tex> может быть изначально охарактеризована как точка, находящаяся на одном расстоянии от противолежащего ребра и прямых, содержащих рёбра невыпуклой вершины. Задача состоит в том, чтобы найти это самое противолежащее ребро (случай <tex> a) </tex> на рисунке выше). Но как показывает случай <tex> b) </tex>, простой тест на пересечение ребра и биссектрисы невыпуклой вершины (то есть невыпуклая вершина как бы врезается в противолежащее ребро) не может быть использован (в этом случае луч биссектрисы пересекает сразу два ребра, непонятно, с каким из них произойдёт <tex> split\ event</tex>). Поэтому необходимо проверять, что точка <tex> B </tex> лежит в треугольнике, ограниченном противолежащим ребром и биссектрисами <tex> b_i </tex> и <tex> b_{i+1} </tex>, идущими из вершин, инцидентных противолежащему ребру <tex> e_i </tex> (этот треугольник может быть "бесконечным").  
  
'''Замечание:''' простой тест на пересечение биссектрисы вершины <tex> V </tex> и целой линии, содержащей ребро, отсекает случаи тех рёбер, которые лежат ''позади'' вершины <tex> V </tex>.  
+
Координаты возможной точки кандидата <tex> B_i </tex> вычисляются следующим образом: это точка пересечения биссектрисы вершины <tex> V </tex> и биссектрисы угла, который образуется в точке пересечения прямой, содержащей одно из рёбер, инцидентных <tex> V </tex>, и прямой, содержащей противолежащее ребро <tex> e_i </tex>. Все такие точки пересечения <tex> B_i </tex> нужно поместить в приоритетную очередь.
  
Координаты возможной точки кандидата <tex> B_i </tex> вычисляются следующим образом: это точка пересечения биссектрисы вершины <tex> V </tex> и биссектрисы угла, который образуется в точке пересечения прямой, содержащей одно из рёбер, инцидентных <tex> V </tex>, и прямой, содержащей противолежащее ребро <tex> e_i </tex>. Итоговая точка пересечения <tex> B </tex> выбирается как ближайшая среди всех найденных точек <tex> B_i </tex>.
+
[[Файл:Skeleton_felkel_contr.png]]
  
'''Частный случай:''' в этом месте также должна быть проверка на то, что противолежащее ребро не будет параллельно ни одному ребру вершины <tex> V </tex>. Тогда рёбра могут накладываться друг на друга. {{TODO | t = И что делать?(}}
+
'''Замечание:''' в оригинальной статье авторы предлагают класть в приоритетную очередь ближайшую из таких точек <tex> B_i </tex>, но тогда алгоритм будет работать некорректно (см. контрпример на рисунке выше). По алгоритму в очередь добавится <tex> split\ event</tex> <tex> p_e </tex> для вершины <tex> v </tex> и ребра <tex> e </tex>, но на самом деле этот <tex> split\ event</tex> произойдёт с ребром <tex>e'</tex> для данной вершины.
  
 
==== Работа с LAV в момент возникновения split event'a ====
 
==== Работа с LAV в момент возникновения split event'a ====
 
[[Файл:skeleton_lav_managing.png|600px]]
 
[[Файл:skeleton_lav_managing.png|600px]]
  
Когда происходит работа с точкой <tex> B\ split\ event'</tex>а, то необходимо разбить соответствующий полигон на две части, что соответствует разделению <tex> \mathrm{LAV} </tex> данного полигона на два списка. И в каждый новый список нужно вставить новую вершину <tex> X </tex>, образующуюся в точке пересечения <tex> B </tex>. Обе вершины <tex> X </tex> указывают на разделяющее ребро <tex> e_i </tex> (см. рисунок выше).
+
Когда происходит работа с точкой <tex> B\ split\ event'</tex>а, необходимо разбить соответствующий полигон на две части, что соответствует разделению <tex> \mathrm{LAV} </tex> данного полигона на два списка. И в каждый новый список нужно вставить копию вершины <tex> V </tex>, образующейся в точке пересечения <tex> I </tex>. Обе вершины <tex> V_1 </tex> и <tex> V_2 </tex> указывают на разделяющее ребро <tex> e_i </tex> (см. рисунок выше).
+
 
 
==== Частный случай множественных split event'ов на одном ребре ====
 
==== Частный случай множественных split event'ов на одном ребре ====
 
[[Файл:skeleton_collide_edge.jpg]]
 
[[Файл:skeleton_collide_edge.jpg]]
  
Уже должно было стать понятно, что алгоритм не строит промежуточного представления <tex> \mathrm{straight}\ \mathrm{skeleton}</tex>, а работает исключительно с рёбрами исходного полигона. Это приводит к ситуации (см. рисунок выше), когда одно ребро является общим для нескольких новых полигонов в промежуточном представлении (то есть одно ребро меняет свою топологию несколько раз), образовавшихся после разделения старого полигона. В случае, когда ребро уже разбито, и происходит следующий за ним <tex>event</tex>, необходимо правильно определить концы противолежащего ребра (то есть вершины/узлы, которые активный в текущем уровне конструирования крыши, как например вершины <tex> X </tex> и <tex> Y </tex> на рисунке ниже).
+
Уже должно было стать понятно, что алгоритм не строит промежуточного представления <tex> \mathrm{straight}\ \mathrm{skeleton}</tex>, а работает исключительно с рёбрами исходного полигона. Это приводит к ситуации (см. рисунок выше), когда одно ребро является общим для нескольких новых полигонов в промежуточном представлении (то есть одно ребро разбивается несколько раз), образовавшихся после разделения старого полигона. В случае, когда ребро уже разбито, и происходит следующий за ним <tex>event</tex>, необходимо правильно определить концы противолежащего ребра (то есть вершины/узлы, которые активны в текущем уровне конструирования крыши, как например вершины <tex> X </tex> и <tex> Y </tex> на рисунке ниже).
  
Например, в данном случае ребро <tex> SY </tex> является частью ребра <tex> e_i = ZY </tex>, которое стягивается и должно теперь указывать на вершину <tex> X </tex>. Когда произойдёт следующее событые в точке пересечения <tex> B </tex>, то нам необходимо правильно указать ребро новой вершине в этой точке в <tex> \mathrm{LAV} </tex>. Реальный конец ребра <tex> e_i </tex> {{---}} точка <tex> Z </tex>, но мы хотим указать на ребро <tex> XY </tex>. Это необходимо для поддержания корректности структуры <tex> \mathrm{SLAV} </tex>. Ниже будет представлено два способа решения этой проблемы.
+
[[Файл:skeleton_multi_edge.png|600px]]
===== Первый способ =====
 
Можно физически разделить исходное ребро на два, вставив новую точку <tex> S </tex>. Это решает проблему, так как никакое ребро не будет разделено дважды, а определение концов разделяемого ребра выполняется просто. Вставка вершины для точки <tex> B </tex> в <tex> \mathrm{LAV} </tex> тоже происходит относительно просто, потому что мы знаем точно, с каким ребром эта вершина связана. Но такой подход требует отдельно рассматривать вершины типа <tex> S </tex>, чтобы не добавить их случайно в <tex> \mathrm{straight}\ \mathrm{skeleton}</tex>.
 
===== Второй способ (используемый в авторском решении) =====
 
Идея заключается в том, чтобы хранить только вершины, которые реально будут в <tex> \mathrm{straight}\ \mathrm{skeleton}</tex>, а указатели на разделямое ребро хранятся во всех подполигонах, для которых это ребро является общим. Это приводит к множественным попаданиям <tex> split\ event'</tex>ов на одно ребро.
 
  
Для примера, два полигона на рисунке выше разделяют общую ссылку на ребро <tex> e_i </tex>. Во время процесса обработки вершины <tex> B </tex> многоугольник <tex> XMVNY </tex> разбивается на две части <tex> XMB </tex> и <tex> BNY </tex>, а вершина <tex> V </tex> помечается как обработанная.  
+
Например, в данном случае ребро <tex> SY </tex> является частью ребра <tex> e_i = ZY </tex>, которое стягивается и должно теперь указывать на вершину <tex> X </tex>. Когда произойдёт следующее событие в точке пересечения <tex> B </tex>, нам необходимо правильно указать ребро новой вершине в этой точке в <tex> \mathrm{LAV} </tex>. Реальный конец ребра <tex> e_i </tex> {{---}} точка <tex> Z </tex>, но мы хотим указать на ребро <tex> XY </tex>. Это необходимо для поддержания корректности структуры <tex> \mathrm{SLAV} </tex>.  
  
Всё это нужно для того, чтобы правильно связать <tex> B </tex> с вершинами <tex> X </tex> и <tex> Y </tex>, а не с <tex> Z </tex> и <tex> Y </tex>. Во время обхода <tex> \mathrm{SLAV} </tex> выбирается правильная часть ребра <tex> e_i </tex> данном случае она определяется вершинами <tex> X </tex> и <tex> Y </tex>). Определяется следующим образом: вершина <tex> B </tex> лежит справа от биссектрисы посещённой вершины <tex> Y </tex> и слева от биссектрисы предка посещённой вершины <tex> X </tex>.
+
Чтобы решить эту проблему, следует хранить <tex>split\ event</tex> как <tex>3</tex> вершины {{---}} невыпуклая вершина и две вершины противолежащего ребра. Дополнительно нужно хранить [[Хеш-таблица | ассоциативный массив]] из пары вершин в ребро для этих вершин. Тогда в момент разделения ребра <tex>ZY</tex> необходимо удалить это ребро из ассоциативного массива и поместить туда два новых ребра <tex>ZX</tex> и <tex>XY</tex>, которые будут ссылаться на исходное ребро <tex> e_i </tex>.
 +
 
 +
Но в очереди могло быть событие по трём вершинам исходного ребра, а после разделения этого ребра уже нет (например, такое может произойти, если с ребром одновременно сталкивается несколько невыпуклых вершин, лежащих на параллельной этому ребру прямой). Посмотрев в ассоциативный массив, можно обнаружить, что такой пары вершин нет. Однако нам нужно всё же получить по ребру требуемую пару вершин. Для этого можно хранить ещё один ассоциативный массив из пар в рёбра, только из него уже не удалять старые пары. Тогда станет возможным получение по паре вершин ребра, а потом по ребру можно будет получить все актуальные пары вершин, соответствующих этому ребру, и добавить <tex>split\ event</tex> с нужной парой вершин.
  
 
==== Алгоритм для невыпуклых полигонов ====
 
==== Алгоритм для невыпуклых полигонов ====
Строка 141: Строка 153:
 
:<tex>(a)</tex> Положим все вершины в <tex> \mathrm{LAV}</tex>, как это делается в алгоритме для выпуклых многоугольников, а потом <tex> \mathrm{LAV}</tex> поместим в <tex> \mathrm{SLAV}</tex>.
 
:<tex>(a)</tex> Положим все вершины в <tex> \mathrm{LAV}</tex>, как это делается в алгоритме для выпуклых многоугольников, а потом <tex> \mathrm{LAV}</tex> поместим в <tex> \mathrm{SLAV}</tex>.
 
:<tex>(b)</tex> Найдём биссектрисы как в случае с выпуклым многоугольником.
 
:<tex>(b)</tex> Найдём биссектрисы как в случае с выпуклым многоугольником.
:<tex>(c)</tex> Для каждой биссектрисы выпуклой вершины найдём ближайшую точку пересечения с биссектрисой соседней вершины, а для невыпуклых вершин найдём также точки пересечения с противолежащими рёбрами (как это описывалось раньше), и положим в приоритетную очередь ближайшую точку пересечения <tex> I </tex>. Будем также с этой точкой хранить её тип {{---}} <tex> edge\ event</tex> или <tex> split\ event</tex>.
+
:<tex>(c)</tex> Для каждой биссектрисы выпуклой вершины найдём ближайшую точку пересечения с биссектрисой соседней вершины, а для невыпуклых вершин найдём также точки пересечения с противолежащими рёбрами (как это описывалось раньше) и положим в приоритетную очередь ближайшую точку пересечения <tex> I </tex>. Будем также с этой точкой хранить её тип {{---}} <tex> edge\ event</tex> или <tex> split\ event</tex>.
 
'''Шаг 2.''' Пока очередь не пуста:
 
'''Шаг 2.''' Пока очередь не пуста:
:<tex>(a)</tex> Извлечём точку пересечения <tex> I </tex> из приоритетной очереди. Если она имеет тип <tex> edge\ event</tex>, то её надо обработать так же, как в шагах <tex> 2b-2f</tex> алгоритма для невыпуклых полигонов. Иначе выполнять шаги ниже.
+
:<tex>(a)</tex> Извлечём точку пересечения <tex> I </tex> из приоритетной очереди. Если она имеет тип <tex> edge\ event</tex>, то её надо обработать так же, как в шагах <tex> 2b-2f</tex> алгоритма для выпуклых полигонов. Иначе выполнять шаги ниже.
:<tex>(b)</tex> Если точка пересечения указывает на уже обработанные вершины, то продолжить со следующей итерации цикла шага 2, как в случае с выпуклым полигоном.
+
:<tex>(b)</tex> Если точка пересечения указывает на уже обработанные вершины, то продолжить со следующей итерации цикла шага 2, как в случае с выпуклым полигоном. По этой причине мы не будем обрабатывать лишние <tex> split\ event'</tex>ы, хотя вполне могли их добавить в очередь.
:<tex>(c)</tex> Нужно сделать примерно то же самое, что и шаге <tex>2c</tex> алгоритма для выпуклых многоугольников. Только на этом цикл не завершается, а продолжается с новой итерации, так как многоугольник мог разделиться на несколько частей, и, возможно, мы обработали лишь один подпалигон и не последний.
+
:<tex>(c)</tex> Нужно сделать примерно то же самое, что и шаге <tex>2c</tex> алгоритма для выпуклых многоугольников. Только на этом цикл не завершается, а продолжается с новой итерации, так как многоугольник мог разделиться на несколько частей, и, возможно, мы обработали лишь один подполигон и не последний.
 
:<tex>(d)</tex> Добавим в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> ребро <tex> IV </tex>, где точка <tex> I </tex> указывает на вершину <tex> V </tex>. Для <tex> split\ event'</tex>ов точки пересечения указывают ровно на одну вершину в <tex> \mathrm{SLAV}</tex>.
 
:<tex>(d)</tex> Добавим в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> ребро <tex> IV </tex>, где точка <tex> I </tex> указывает на вершину <tex> V </tex>. Для <tex> split\ event'</tex>ов точки пересечения указывают ровно на одну вершину в <tex> \mathrm{SLAV}</tex>.
 
:<tex>(e)</tex> Модифицируем теперь <tex> \mathrm{SLAV}</tex>:
 
:<tex>(e)</tex> Модифицируем теперь <tex> \mathrm{SLAV}</tex>:
Строка 151: Строка 163:
 
::* создадим две новые вершины <tex> V_1 </tex> и <tex> V_2 </tex> с одинаковыми координатами точки пересечения <tex> I </tex>,
 
::* создадим две новые вершины <tex> V_1 </tex> и <tex> V_2 </tex> с одинаковыми координатами точки пересечения <tex> I </tex>,
 
::* найдём для каждой вершины <tex> V_1 </tex> и <tex> V_2 </tex> противолежащее ребро в своём подпалигоне,
 
::* найдём для каждой вершины <tex> V_1 </tex> и <tex> V_2 </tex> противолежащее ребро в своём подпалигоне,
::* разделим <tex> \mathrm{LAV}</tex> с вершиной <tex> V </tex> на две части (как показано на рисунке выше), вставим в части вершины <tex> V_1 </tex> и <tex> V_2 </tex>, а затем обе части добавим в <tex> \mathrm{SLAV}</tex>. Вершина <tex> V_1 </tex> будет следующей для предыдующего к <tex> V </tex> узлу в <tex> \mathrm{LAV}</tex> и предыдущей для конца противолежащего ребра. Аналогично для вершины <tex> V_2 </tex>. Этот шаг в действительно разбивает полигон на две части,
+
::* разделим <tex> \mathrm{LAV}</tex> с вершиной <tex> V </tex> на две части (как показано на рисунке выше), вставим в части вершины <tex> V_1 </tex> и <tex> V_2 </tex>, а затем обе части добавим в <tex> \mathrm{SLAV}</tex>. Вершина <tex> V_1 </tex> будет следующей для предыдующего к <tex> V </tex> узла в <tex> \mathrm{LAV}</tex> и предыдущей для конца противолежащего ребра. Аналогично для вершины <tex> V_2 </tex>,
::* Добавим указатели вершинам <tex> V_1 </tex> и <tex> V_2 </tex> на соответствующие рёбра.
+
::* удалим из ассоциативного массива пару вершин ребра <tex> e_i </tex> и поместим две новых пары, в одной из которых будет вершина <tex> V_1 </tex> и конец ребра <tex> e_i </tex>, а в другом {{---}} начало <tex> e_i </tex> и вершина <tex> V_2 </tex>,
 +
::* добавим указатели на соответствующие рёбра вершинам <tex> V_1 </tex> и <tex> V_2 </tex>.
 
:<tex>(f)</tex> Для обеих вершин <tex> V_1 </tex> и <tex> V_2 </tex>:
 
:<tex>(f)</tex> Для обеих вершин <tex> V_1 </tex> и <tex> V_2 </tex>:
::* найдём биссектрисы между рёбрами, на которые эти вершины слинковались в шаге <tex>2e</tex>,
+
::* найдём биссектрисы между рёбрами, на которые эти вершины указывают в шаге <tex>2e</tex>,
::* найдём точки пересечения лучей с биссектрисами соседних вершин как в шаге <tex> 1c </tex> (тут могут получиться точки пересечения обоих типов),
+
::* найдём все события точек пересечения как в шаге <tex> 1c </tex> (тут могут получиться события обоих типов),
::* сохраним ближайшие точки пересечения в приоритетной очереди.
+
::* сохраним точки пересечения, отвечающие найденным событиям, в приоритетной очереди.
  
Обработка событий обоих типов выполняется с такой же асимптотикой, что и в алгоритме для выпуклых полигонов. Основной вклад в асимптотику вносит вычисление <tex> split\ event'</tex>ов, когда нам нужно пробежаться по всем рёбрам и найти противолежащее. Отсюда и получается итоговая асимптотика <tex> \mathcal{O}(n^2) </tex>.
+
Обработка <tex> edge\ event'</tex>ов выполняется с такой же асимптотикой, как и в алгоритме для выпуклых полигонов. Но из-за того, что в очередь кладутся всевозможные точки, в которых произошли <tex> split\ event'</tex>ы, в ней может оказаться <tex>\mathcal{O}(n^2)</tex> элементов. Хотя обработка <tex> split\ event'</tex>а может занять линейное время от числа вершин (если новая вершина в точке пересечения осталась невыпуклой), это произойдёт только для <tex> split\ event'</tex>ов, которые создают новые вершины <tex> S(P) </tex>, а их <tex>\mathcal{O}(n)</tex> по доказанной [[#lemma1 | лемме]]. Остальные <tex> split\ event'</tex>ы обработаются за <tex>\mathcal{O}(1)</tex> в шаге <tex> 2b </tex>, поэтому итоговая асимптотика составит <tex>\mathcal{O}(n^2 \log n)</tex>.
  
==== Случай полигонов с дырами ====
+
==== Случай полигонов с дырками ====
Данный алгоритм может работать и с многоугольниками, содержащими дыры, если они ориентированы по часовой стрелке, чтобы внутренняя область многоугольника лежала слева от рёбер. И в самом начале алгоритма каждый замкнутый контур помещается в свой <tex> \mathrm{LAV} </tex> в множестве <tex> \mathrm{SLAV} </tex>.
+
Данный алгоритм может работать и с многоугольниками, содержащими дырки, если они ориентированы по часовой стрелке, чтобы внутренняя область многоугольника лежала слева от рёбер. И в самом начале алгоритма каждый замкнутый контур помещается в свой <tex> \mathrm{LAV} </tex> в множестве <tex> \mathrm{SLAV} </tex>.
  
 
[[Файл:skeleton_hole_example.png|500px]]
 
[[Файл:skeleton_hole_example.png|500px]]
Строка 169: Строка 182:
  
 
==== Особенности реализации и другие частные случаи ====
 
==== Особенности реализации и другие частные случаи ====
{{TODO | t = Совпадение нескольких split event'ов в одной точке}}
+
Приведённый здесь алгоритм плох тем (кроме того, что медленно работает), что является довольно общим и не рассматривает возникающие на практике сложные частные случаи. Он будет работать на произвольных случайных полигонах, в которых возникают только простые события (картинка ниже) {{---}} в точке <tex> a </tex> произошёл <tex> edge\ event </tex>, в точке <tex> b </tex> {{---}} <tex> split\ event </tex>, а точки <tex> c </tex> и <tex> d </tex> уже внутри треугольников, и с ними разобраться просто.
{{TODO | t = Накладывание рёбер друг на друга}}
+
 
 +
[[Файл:skeleton_simple_event_example.jpg]]
 +
 
 +
Но на практике может возникнуть что-то менее тривиальное (картинка ниже): совпадение многих <tex> edge\ event'</tex>ов в одной точке, многих <tex> split\ event'</tex>ов, или даже в одной точке могут одновременно произойти события двух типов, а также многократное наложение параллельных рёбер друг на друга.
 +
 
 +
[[Файл:skeleton_complex_event_example.jpg]]
 +
 
 +
===== Параллельные противоположные рёбра =====
 +
С точками <tex> c </tex> и <tex> d </tex> необходимо разбираться следующим образом: как только параллельные рёбра становятся соседними перед событием, нужно проверить, что после произошедшего события они соединятся потом в одно ребро. Если в <tex> \mathrm{LAV} </tex> осталось только два параллельных ребра, то мы удаляем их из <tex> \mathrm{SLAV} </tex>.
 +
 
 +
Ещё примеры не для слабонервных.
 +
 
 +
[[Файл:skeleton_parallel_edges.jpg|300px]]
 +
 
 +
[[Файл:skeleton_more_complex_event_example3.jpg]]
 +
 
 +
===== Параллельные "соседние" рёбра =====
 +
[[Файл:skeleton_pce_event_example.jpg]]
 +
 
 +
Другой интересный случай возникает, когда несоседние параллельные рёбра становятся соседними после исчезания рёбер между ними. Такая проблема называется <tex> \mathrm{PCE} </tex> (''parallel consecutive edge problem''). В таком случае можно поступать по-разному.
 +
* На левом рисунке используется <tex>separate\ rule</tex> {{---}} согласно этому правилу два ребра рассматриваются отдельно. Тогда верно утверждение, что каждому ребру соответствует ровно одна грань. И в этом случае можно считать, что новая вершина на стыке двух рёбер движется перпендикулярно рёбрам.
 +
* На среднем рисунке используется <tex>merge\ rule</tex> {{---}} рёбра в таком случае объединяются в одно новое ребро.
 +
 
 +
Отличить этот случай от предыдущего можно, посмотрев на ориентацию двух рёбер. Если они направлены в одну сторону, то это <tex> \mathrm{PCE} </tex>, если в противоположную, то разбираемся как в предыдущем случае.
 +
 
 +
===== Множественные события в одной точке =====
 +
Первая проблема, возникающая в этом случае {{---}} точное определение того, что несколько событий произошли в одной точке. Для определения совпадения нескольких событий в одной точке можно поступать приближённо: вводить с каждой точкой <tex>\varepsilon</tex>-окрестность и смотреть, не попали ли другие точки в эту окрестность, или использовать более точную арифметику<ref>[http://www.mpfr.org/ The GNU MPFR Library]</ref>. В данном случае недостаточно использовать [[Интервальная арифметика | интервальную арифметику]] или даже рациональную арифметику. Потому что даже если координаты точек задаются абсолютно точно, то для подсчёта радиуса вписанной окружности необходимо уметь извлекать корни (напомним, что радиус вписанной окружности равен площади, поделённой на полупериметр, а длины сторон треугольников {{---}} корни из [[Гильбертовы пространства | скалярного произведения]] векторов разницы точек на самих себя).
 +
 
 +
Чтобы научиться разбираться с такими случаями в алгоритме, когда мы уже поняли, что в одной точке будет несколько событий, введём понятие '''обобщённого события пересечения''' (англ. ''GIE'', ''generalized intersection event'').
 +
 
 +
[[Файл:skeleton_chain1.jpg]]
 +
 
 +
Для начала введём понятие цепочек рёбер, которые вовлечены в событие {{---}} такие рёбра, которые сталкиваются в данном событии. Эти цепи упорядочим согласно направлению рёбер (см. рисунок выше).
 +
 
 +
[[Файл:skeleton_chain2.jpg]]
 +
 
 +
Мы можем также упорядочить сами цепи вокруг точки события, объединив эти цепи в один циклический список. Следовательно, событие получается как бы окружено списком рёбер, которые участвуют в нём, при этом никакие другие рёбра не участвуют. Можно заметить (рисунки <tex> c,\ d,\ e</tex> выше), что соседние рёбра в списке из изначально разных цепей становятся потом соседними в <tex>\mathrm{LAV}</tex>.
 +
 
 +
Алгоритм обработки GIE следующий:
 +
* '''Шаг внутри цепи:''' в каждой цепи удаляем внутренние рёбра (кроме первого и последнего) {{---}} это соответствует тому, что исчезает несколько рёбер, участвующих в одном <tex>edge\ event'</tex>е. После этого шага остаются цепи только длин <tex>1</tex> или <tex>2</tex>.
 +
* '''Шаг цепи из одного звена:''' цепи длины <tex>1</tex> разбиваются в точке события (это соответствует простому <tex>split\ event'</tex>у). Теперь все цепи имеют длину ровно <tex>2</tex>.
 +
* '''Шаг  межцепной:''' объединяем соседние цепи (соответствующие одному событию) в циклический список, соединяя конец одной цепи с началом следующей и так далее. Поэтому каждая цепь разбивается в середине, и образуются новые списки длины <tex>2</tex>.
 +
* '''Шаг циклы из двух рёбер:''' списки <tex>\mathrm{LAV}</tex> длины <tex>2</tex> состоящие из двух параллельных рёбер, то есть ограничивающие полигон нулевой площади, удаляются из <tex>\mathrm{SLAV}</tex>.
 +
* '''Шаг PCE:''' разбираемся с <tex> \mathrm{PCE} </tex> согласно принятому нами правилу решения {{---}} правилу слияния или правилу разделения.
 +
 
 +
В реализации это будет выглядеть следующим образом: можно посмотреть, что сейчас лежит в голове приоритетной очереди, и доставать события, пока они происходят в одной точке, а потом разбить эти события на цепочки и выполнять шаги из алгоритма выше.
  
== Алгоритм построения с помощью Motorcycle graph ==
+
==== Открытые реализации ====
Рассмотрим алгоритм построения <tex> \mathrm{straigt}\ \mathrm{skeleton}</tex> на основе [[Motorcycle graph | мотографов]].
+
Приведённый здесь алгоритм был реализован Fernando Cacciola<ref>[https://www.cgal.org/UserWorkshop/2004/straight_skeleton.pdf Fernando Cacciola, "A CGAL implementation of the Straight Skeleton of a Simple 2D Polygon with Holes "]</ref>, который исправил все ошибки в статье P. Felkel. И этот алгоритм используется в открытой библиотеке вычислительной геометрии CGAL<ref>[http://doc.cgal.org/latest/Straight_skeleton_2/index.html CGAL 4.5 {{---}} 2D Straight Skeleton and Polygon Offsetting]</ref>. Более того, он является одной из немногих открытых реализаций построения <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>. Но данный алгоритм достаточно медленный для решения практических задач. В реальной жизни используют его модификации или более сложные алгоритмы.
{{TODO | t = Алгоритм на мотографах}}
 
  
 
== Другие алгоритмы ==
 
== Другие алгоритмы ==
 
Существует простой в понимании и реализации алгоритм для построения <tex> \mathrm{straigt}\ \mathrm{skeleton}</tex> на основе [[Триангуляция полигонов (ушная + монотонная)|триангуляции]], который работает за время <tex> \mathcal{O}(n^3 \log n)</tex><ref>[http://www.sthu.org/research/publications/files/eurocg2010-slides.pdf Stefan Huber, Martin Held, "Straight Skeletons and their Relation to Triangulations"]</ref>. Aichholzer смог обобщить этот алгоритм для построения <tex> \mathrm{straigt}\ \mathrm{skeleton}</tex> произвольного планарного графа<ref>[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.2586 Oswin Aichholzer, Franz Aurenhammera, "Straight Skeletons for General Polygonal Figures in the Plane"]</ref>. Также автором в его оригинальной статье был представлен алгоритм построения данной структуры, базирующийся на понятии '''волнового фронта''' (англ. ''wavefront''). Этот алгоритм может быть реализован за время <tex> \mathcal{O}(n^3)</tex> с использованием <tex> \mathcal{O}(n)</tex> памяти либо с использованием [[Двоичная куча | приоритетной очереди]] за время <tex> \mathcal{O}(n^2 \log n)</tex> и <tex> \mathcal{O}(n^2)</tex> памяти<ref>[http://www.jucs.org/jucs_1_12/a_novel_type_of/Aichholzer_O.pdf Oswin Aichholzer, Franz Aurenhammera, "A Novel Type of Skeleton for Polygons"]</ref>. Известен алгоритм построения <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> для [[Триангуляция полигонов (ушная + монотонная)#def_monotone_polygon|монотонных полигонов]] за время <tex> \mathcal{O}(n \log n)</tex> с использованием <tex> \mathcal{O}(n)</tex> памяти<ref>[http://www.cs.bgu.ac.il/~eurocg14/papers/paper_9.pdf Therese Biedl, Martin Held, Stefan Huber, Dominik Kaaser, Peter Palfrader, "Straight Skeletons of Monotone Polygons"]</ref>.  
 
Существует простой в понимании и реализации алгоритм для построения <tex> \mathrm{straigt}\ \mathrm{skeleton}</tex> на основе [[Триангуляция полигонов (ушная + монотонная)|триангуляции]], который работает за время <tex> \mathcal{O}(n^3 \log n)</tex><ref>[http://www.sthu.org/research/publications/files/eurocg2010-slides.pdf Stefan Huber, Martin Held, "Straight Skeletons and their Relation to Triangulations"]</ref>. Aichholzer смог обобщить этот алгоритм для построения <tex> \mathrm{straigt}\ \mathrm{skeleton}</tex> произвольного планарного графа<ref>[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.2586 Oswin Aichholzer, Franz Aurenhammera, "Straight Skeletons for General Polygonal Figures in the Plane"]</ref>. Также автором в его оригинальной статье был представлен алгоритм построения данной структуры, базирующийся на понятии '''волнового фронта''' (англ. ''wavefront''). Этот алгоритм может быть реализован за время <tex> \mathcal{O}(n^3)</tex> с использованием <tex> \mathcal{O}(n)</tex> памяти либо с использованием [[Двоичная куча | приоритетной очереди]] за время <tex> \mathcal{O}(n^2 \log n)</tex> и <tex> \mathcal{O}(n^2)</tex> памяти<ref>[http://www.jucs.org/jucs_1_12/a_novel_type_of/Aichholzer_O.pdf Oswin Aichholzer, Franz Aurenhammera, "A Novel Type of Skeleton for Polygons"]</ref>. Известен алгоритм построения <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> для [[Триангуляция полигонов (ушная + монотонная)#def_monotone_polygon|монотонных полигонов]] за время <tex> \mathcal{O}(n \log n)</tex> с использованием <tex> \mathcal{O}(n)</tex> памяти<ref>[http://www.cs.bgu.ac.il/~eurocg14/papers/paper_9.pdf Therese Biedl, Martin Held, Stefan Huber, Dominik Kaaser, Peter Palfrader, "Straight Skeletons of Monotone Polygons"]</ref>.  
  
В данном конспект был (P.S. точнее, ещё будет) представлен алгоритм на основе мотографов, который придумали Stefan Huber и Martin Held. Они говорят, что даже смогли реализовать этот алгоритм, но код нигде не выкладывали.
+
Также существует более эффективный алгоритм на основе мотографов, который придумали Stefan Huber и Martin Held. Их реализация называется <tex>\mathrm{STALGO}</tex>, и она доступна на их сайте<ref>[https://www.sthu.org/code/stalgo/ STALGO {{---}} an industrial-strength C++ software package for computing straight skeletons and mitered offset-curves]</ref>.
  
 
== См. также ==
 
== См. также ==
Строка 193: Строка 250:
 
* [http://www.dma.fi.upm.es/mabellanas/tfcs/skeleton/html/documentacion/straight%20skeletons%20implementation.pdf Petr Felkel, Stepan Obdrazalek, "Straight Skeleton Implementation"]
 
* [http://www.dma.fi.upm.es/mabellanas/tfcs/skeleton/html/documentacion/straight%20skeletons%20implementation.pdf Petr Felkel, Stepan Obdrazalek, "Straight Skeleton Implementation"]
 
* [http://twak.blogspot.ru/2009/05/engineering-weighted-straight-skeleton.html Engineering a weighted straight skeleton algorithm]
 
* [http://twak.blogspot.ru/2009/05/engineering-weighted-straight-skeleton.html Engineering a weighted straight skeleton algorithm]
* [https://code.google.com/p/campskeleton/ Визуализатор алгоритма]
+
* [https://code.google.com/p/campskeleton/ Визуализатор алгоритма]  
* [http://doc.cgal.org/latest/Straight_skeleton_2/index.html CGAL 4.5 {{---}} 2D Straight Skeleton and Polygon Offsetting]
 
  
 
[[Категория: Вычислительная геометрия]]
 
[[Категория: Вычислительная геометрия]]
[[Категория: Скалярное произведение и мера]]
+
[[Категория: Триангуляция Делоне и диаграмма Вороного]]
 
[[Категория: Структуры данных]]
 
[[Категория: Структуры данных]]

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

Структура [math]\mathrm{straight}\ \mathrm{skeleton}[/math] была придумана Oswin Aichholzer. Она используется в различных практических задачах (проектирование крыш для зданий), для доказательства некоторых теорем[1], в обработке изображений — эрозия и дилатация, но самое главное — можно оффсетить полигоны и упрощать их.

Топологические свойства

Далее будет дано процедурное определение [math]\mathrm{straight}\ \mathrm{skeleton}[/math].

Можно представить, будто все стороны многоугольника параллельно двигаются внутрь с одинаковой постоянной скоростью, то есть многоугольник как бы сжимается внутрь. Тогда вершины будут двигаться вдоль биссектрис внутренних углов , а точки пересечения биссектрис будут являться точками, в которых рёбра полностью сократятся (выродятся в точку). В каждый момент времени от начала движения рёбер получается слоистая структура (рис 1.). На рис. 2 синим цветом выделен [math] \mathrm{straight}\ \mathrm{skeleton} [/math] — множество отрезков, образованных точками пересечения при движении сторон полигона. Эта структура напоминает построение крыши для дома (рис. 3), и, в самом деле, скелетон применяется для решения подобных задач: по стенам здания необходимо спроектировать его крышу.

Рис. 1 — слои в разные моменты времени
Рис. 2 — дерево [math] \mathrm{straight}\ \mathrm{skeleton} [/math]
Рис. 3 — пример крыши по [math] \mathrm{straight}\ \mathrm{skeleton} [/math]
Проектирование крыши здания по готовым стенам

Процесс стягивания многоугольника продолжается до тех пор, пока все рёбра не сожмутся в точку, то есть пока меняется число вершин в стянутом многоугольнике, и таким образом появляются новые вершины [math] \mathrm{straight}\ \mathrm{skeleton} [/math]. Существуют два типа изменений, в ходе которых они образуются:

  • [math] Edge\ event [/math] — данное изменение происходит, когда сторона многоугольника полностью стягивается, делая соседние стороны инцидентными.
  • [math] Split\ event [/math] — происходит, когда ребро разбивается на два новых ребра, исходящих из точки преломления старого. Такое событие происходит на биссектрисе вогнутой вершины многоугольника. И тогда стягиваемая многоугольником область может разбиваться на две непересекающиеся многоугольные области.

На рисунке [math]edge\ event'[/math]ы отмечены зелёными окружностями, а [math]split\ event'[/math]ы — красными квадратами.

Skeleton event example.jpg

Таким образом, можно предъявить соответствие между элементами [math] \mathrm{straight}\ \mathrm{skeleton} [/math] и происходящими событиями:

  • внутренние вершины — [math] event' [/math]ы,
  • листья — вершины исходного многоугольника,
  • грани — области многоугольника, заметаемые сторонами многоугольника в процессе стягивания,
  • дуги — соединяют либо две внутренние вершины, либо внутреннюю вершину с листом.

Стоит также отметить, что в общем случае [math] split\ event'[/math]ы могут быть нетривиальными. На рисунке ниже в случае [math] (c) [/math] в вершине [math] p [/math] совпали [math]split\ event[/math] из вершины [math] u [/math] и ребра [math] e [/math] и [math] edge\ event[/math] ребра [math] uv [/math], а в случае [math] (d) [/math] совпали два [math] split\ event'[/math]а вершин [math] u_1 [/math] и [math] u_2 [/math]. Случаи [math] (a) [/math] и [math] (b) [/math] — простые [math] edge [/math] и [math] split\ event'[/math]ы.

Event example.png

Задача построения такого [math] \mathrm{straight}\ \mathrm{skeleton} [/math] является частным случаем задачи построения [math] \mathrm{weighted}\ \mathrm{straight}\ \mathrm{skeleton} [/math], где каждому ребру можно задавать вес, то есть скорость движения ребра. И эта скорость может быть даже отрицательной. Но задача построения [math]\mathrm{WSS}[/math] является в общем случае неопределённой. В процессе её решения возникают неоднозначности[2]. Задача [math] \mathrm{weighted}\ \mathrm{straight}\ \mathrm{skeleton} [/math] является более сложной, и здесь рассматриваться не будет.

Алгоритм построения [math] \mathrm{straight}\ \mathrm{skeleton} [/math] можно модифицировать, чтобы волновой фронт шёл от полигона. То есть сначала можно построить [math] \mathrm{straight}\ \mathrm{skeleton} [/math], тем самым упростив структуру полигона и сделав его более "гладким", а затем распространить волну в обратную сторону.

Свойства Straight skeleton

Из процесса построения [math] \mathrm{straight}\ \mathrm{skeleton} [/math] следует, что он является планарным графом. Ранее уже упоминалось, что он также является деревом. Будем обозначать [math] \mathrm{straight}\ \mathrm{skeleton} [/math] простого полигона без самопересечений [math] P [/math], в котором [math] n [/math] вершин, как [math] S(P) [/math]. Тогда справедлива следующая лемма:

Лемма (1):
[math] S(P) [/math] является деревом, содержит [math] n [/math] граней, не более [math] n - 2 [/math] внутренних вершин и не более [math] 2 n - 3 [/math] рёбер.
Доказательство:
[math]\triangleright[/math]

Skeleton lemma.png

Каждая грань [math] f(e) [/math] начинает образовываться во время стягивания ребра [math] e [/math], и даже если на ребре произошёл [math] split\ event [/math], сама грань не могла разделиться. Построение грани [math] f(e) [/math] завершается, когда ребро [math] e [/math] полностью стягивается. И это ребро дальше не может появиться снова, поэтому граней в [math] S(P) [/math] столько, сколько сторон в многоугольнике, то есть ровно [math] n [/math].

То, что [math] S(P) [/math] является деревом, легко доказывается по индукции числа вершин в многоугольнике.

База: многоугольник является треугольником, в его [math] \mathrm{straight}\ \mathrm{skeleton} [/math] будет одна внутренняя вершина — точка пересечения биссектрис, листьями будут вершины треугольника. Такой граф, очевидно, будет деревом.

Переход: пусть для всех многоугольников с количеством вершин меньше [math]k\ S(P)[/math] будет деревом. Рассмотрим самый первый [math]event[/math] в многоугольнике из [math]k[/math] вершин.

  • Если это [math]edge\ event[/math], то появится новая вершина, которую мы соединим с инцидентными ребру вершинами, а также с какой-то вершиной [math]\mathrm{straight}\ \mathrm{skeleton} [/math] полигона из [math]k - 1[/math] вершин. Получившийся граф будет деревом.
  • Если это [math]split\ event[/math], то новая вершина соединяется с одной вершиной исходного полигона и с двумя вершинами [math]\mathrm{straight}\ \mathrm{skeleton} [/math] для полигонов, в которых меньше [math] k [/math] вершин. В этом случае также получаем дерево.


Внутренние вершины в [math] \mathrm{straight}\ \mathrm{skeleton} [/math] имеют степень не меньше [math] 3 [/math] — простой перебор всех случаев [math] event'[/math]ов (степень будет больше, если в одной вершине совпало несколько событий). Так как [math] S(P) [/math] имеет [math]n[/math] листьев, то внутренних вершин будет не больше [math] n - 2 [/math], а так как [math] S(P) [/math] является деревом, то рёбер у него будет не более [math] 2 n - 3 [/math].
[math]\triangleleft[/math]

Ещё один пример:

Skeleton example1.png

Алгоритм с изпользованием SLAV

Далее будет описан алгоритм, придуманный Petr Felkel, который строит [math] \mathrm{straight}\ \mathrm{skeleton} [/math] за время [math] \mathcal{O}(n^2 \log n)[/math], где [math] n [/math] — общее число вершин в полигоне. В оригинальной статье этому алгоритму даётся асимптотическая оценка [math] \mathcal{O}(nm + n \log n)[/math], или просто [math] \mathcal{O}(n^2)[/math], где [math] m [/math] — число невыпуклых вершин в полигоне. Однако в статье содержатся ошибки, поэтому данная в ней оценка неверна.

Сначала алгоритм будет рассмотрен на простом случае — выпуклом многоугольнике, — а потом на невыпуклом.

Выпуклый полигон

В случае выпуклого многоугольника возникают только [math] edge\ event'[/math]ы по определению. Объяснить алгоритм можно простым образом: найдём точки пересечения биссектрис многоугольника для каждой вершины со всеми соседними вершинами, возьмём такую точку, в которой произойдёт самый первый [math] edge\ event[/math], добавим полученную вершину в [math] \mathrm{straight}\ \mathrm{skeleton} [/math], соединим её с вершинами ребра, которое исчезло в процессе текущего [math] edge\ event'[/math]а, а потом перестроим полигон, создав новую вершину и подвинув все остальные вдоль биссектрис на одинаковое расстояние. Будем продолжать этот процесс до тех пор, пока многоугольник не превратится в треугольник.

Теперь реализуем этот алгоритм более эффективно. Для этого мы будем использовать специальную структуру данных — [math] \mathrm{SLAV}[/math] (set of circular lists of active vertices). Эта структура хранит цикл всех вершин для внешней грани, а также цикл для каждой дырки многоугольника и для всех многоугольников, возникающих в процессе построения [math] S(P) [/math]. В данном случае у нас будет просто [math] \mathrm{LAV}[/math] циклический список всех вершин многоугольника.

Skeleton lav.jpg

В таком списке частично найденного [math] \mathrm{straight}\ \mathrm{skeleton} [/math] вершины имеют указатели на следующую и предыдущую вершины в порядке обхода контура, а также указатели на инцидентные рёбра.

Алгоритм для выпуклых полигонов

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

Шаг 1. Инициализация:

[math](a)[/math] Поместим все вершины многоугольника [math] V_1, V_2 \dots V_n [/math] в двусвязный циклический список в порядке обхода вдоль контура. Все вершины в [math] \mathrm{LAV}[/math] сейчас считаются активными.
[math](b)[/math] Для каждой вершины [math] V_i [/math] в [math] \mathrm{LAV}[/math] добавим указатели на инцидентные рёбра [math] e_{i-1} = V_{i-1}V_i[/math] и [math] e_i = V_i V_{i+1}[/math], а также найдём луч биссектрисы [math] b_i [/math].
[math](c)[/math] Для каждой вершины [math] V_i [/math] найдём ближайшее пересечение биссектрисы [math] b_i [/math] с биссектрисами [math] b_{i-1} [/math] и [math] b_{i+1} [/math]. Если это пересечение существует, то поместим его в приоритетную очередь согласно [math] L(e_i) [/math] — расстоянию от точки пересечения до одного из рёбер, инцидентных вершине [math] V_i [/math]. Для каждой точки пересечения [math] I_i [/math] будем ещё хранить два указателя на вершины [math] V_a [/math] и [math] V_b [/math] — начала лучей биссектрис, которые пересекаются в точке [math] I_i [/math]. Эти указатели понадобятся в будущем, когда нужно будет определять соответствующие вершинам рёбра [math] e_a, e_b [/math] (см. рисунок ниже).

Шаг 2. Следующие действия выполняются в цикле, пока приоритетная очередь не пуста:

[math](a)[/math] Извлечём точку пересечения [math] I [/math] из приоритетной очереди.
[math](b)[/math] Если вершины [math] V_a [/math] и [math] V_b [/math], соответствующие данной точке пересечения, помечены как обработанные, то переходим к следующей итерации цикла шага 2. Это означает, что ребро между данными вершинами полностью стянулось (обработанные вершины и стянутые рёбра помечены крестом на рисунке ниже). Эту проверку необходимо делать из-за того, что мы могли поместить в очередь обработанные вершины в момент получения новых [math]event'[/math]ов.
[math](c)[/math] Если осталось всего три вершины [math] V_a, V_b, V_c [/math], то добавим в [math] \mathrm{straight}\ \mathrm{skeleton} [/math] рёбра [math] IV_a, IV_b, IV_c [/math]. В случае выпуклого многоугольника в этом месте можно завершить алгоритм. Но в общем случае нужно будет снова перейти к началу цикла.
[math](d)[/math] Добавим в [math] \mathrm{straight}\ \mathrm{skeleton} [/math] рёбра [math] IV_a, IV_b [/math].
[math](e)[/math] Теперь необходимо модифицировать [math] \mathrm{LAV}[/math] (детали на рисунке ниже):
  • пометим вершины [math] V_a [/math] и [math] V_b [/math] как обработанные (напомню, что они обозначаются крестом на рисунке к данному алгоритму),
  • создадим новую вершину [math] V [/math] в точке пересечения [math] I [/math] (отмечена квадратиком на рисунке),
  • добавим вершину [math] V [/math] в [math] \mathrm{LAV}[/math], то есть между предыдущим к [math] V_a [/math] и следующим к [math] V_b [/math] узлами,
  • добавим вершине [math] V [/math] указатели на соответствующие рёбра [math] e_a [/math] и [math] e_b [/math].
[math](f)[/math] Посчитаем дополнительные величины для вершины [math] V [/math]:
  • луч биссектрисы [math] b [/math] между рёбрами [math] e_a [/math] и [math] e_b [/math],
  • точки пересечения биссектрисы [math]b[/math] с биссектрисами вершин, соседних к [math] V [/math] в [math] \mathrm{LAV}[/math], как в шаге [math] 1c [/math],
  • сохраним ближайшие точки пересечения в приоритетной очереди. Ключом точки пересечения в приоритетной очереди будет расстояние [math] L(e_i) [/math] до стянутого ребра [math] e_i [/math].

Skeleton convex example.png

В этом случае асимптотика алгоритма составляет [math] \mathcal{O}(n \log n)[/math], так как на каждой итерации цикла нам нужно положить константное число элементов в очередь, а итераций цикла не больше [math] n [/math].

Частные случаи

Частным случаем в алгоритме может быть совпадение нескольких [math] edge\ event'[/math]ов в одной точке. Эти совпадения добавляются в шагах [math] 1c [/math] и [math] 2f [/math], так как точки пересечения добавляются только в них, но могут быть относительно легко обработаны в шаге [math] 2b [/math]. Или мы можем считать, что между [math] edge\ event'[/math]ами в одной точке будут рёбра нулевого веса в полученном [math] S(P) [/math], а затем можно просто избавиться от лишних вершин в результирующей структуре.

Также может случиться, что какие-то рёбра не стянулись в итоге в одну вершину, а слились. Такое возможно, если какие-то стороны полигона были изначально параллельны (этот случай легко увидеть на прямоугольнике, не являющемся квадратом). С этим частным случаем можно разобраться в шаге [math] 2c [/math], проверив, не совпала ли одна из трёх вершин с другой. В выпуклом многоугольнике слияние двух рёбер может произойти только один раз (что неправда для невыпуклого многоугольника), поэтому с таким случаем несложно разобраться.

Невыпуклый полигон

Основной принцип для невыпуклых полигонов такой же. Только с вершиной ещё хранится дополнительный атрибут, обозначающий событие, которое в ней произошло: [math] edge\ event[/math] или [math] split\ event[/math].

Если представить процесс стягивания многоугольника, как будто у нас уже построена для него крыша, а мы двигаем вверх некоторую заметающую плоскость, где пересечение крыши и плоскости будет обозначать текущий слой, то можно заметить, что область полигона разбивается на несколько частей. Каждой части будет соответствовать свой [math] \mathrm{LAV}[/math], отсюда нам и нужен [math] \mathrm{SLAV}[/math].

Skeleton split event example.png

Наличие невыпуклой вершины может привести (а может и не привести) к разделению внутренней области. Невыпуклая вершина может участвовать в обычном [math] edge\ event'[/math]е (точка [math] A [/math] на рисунке выше). [math] Edge\ event'[/math]ы в случае невыпуклогого многоугольника обрабатываются так же, как и в алгоритме с выпуклым многоугольником.

Посмотрим теперь, что делать с точкой [math] B [/math], в которой возникает [math] split\ event[/math].

Нахождение координат точки B

Skeleton b point coord.png

В простейшем случае точка [math] B [/math] появляется, когда "волновой фронт" распространения движения рёбер от невыпуклой вершины натыкается на встречный фронт противолежащего ребра. В такой момент возникает [math] split\ event[/math]. Поэтому точка [math] B [/math] может быть изначально охарактеризована как точка, находящаяся на одном расстоянии от противолежащего ребра и прямых, содержащих рёбра невыпуклой вершины. Задача состоит в том, чтобы найти это самое противолежащее ребро (случай [math] a) [/math] на рисунке выше). Но как показывает случай [math] b) [/math], простой тест на пересечение ребра и биссектрисы невыпуклой вершины (то есть невыпуклая вершина как бы врезается в противолежащее ребро) не может быть использован (в этом случае луч биссектрисы пересекает сразу два ребра, непонятно, с каким из них произойдёт [math] split\ event[/math]). Поэтому необходимо проверять, что точка [math] B [/math] лежит в треугольнике, ограниченном противолежащим ребром и биссектрисами [math] b_i [/math] и [math] b_{i+1} [/math], идущими из вершин, инцидентных противолежащему ребру [math] e_i [/math] (этот треугольник может быть "бесконечным").

Координаты возможной точки кандидата [math] B_i [/math] вычисляются следующим образом: это точка пересечения биссектрисы вершины [math] V [/math] и биссектрисы угла, который образуется в точке пересечения прямой, содержащей одно из рёбер, инцидентных [math] V [/math], и прямой, содержащей противолежащее ребро [math] e_i [/math]. Все такие точки пересечения [math] B_i [/math] нужно поместить в приоритетную очередь.

Skeleton felkel contr.png

Замечание: в оригинальной статье авторы предлагают класть в приоритетную очередь ближайшую из таких точек [math] B_i [/math], но тогда алгоритм будет работать некорректно (см. контрпример на рисунке выше). По алгоритму в очередь добавится [math] split\ event[/math] [math] p_e [/math] для вершины [math] v [/math] и ребра [math] e [/math], но на самом деле этот [math] split\ event[/math] произойдёт с ребром [math]e'[/math] для данной вершины.

Работа с LAV в момент возникновения split event'a

Skeleton lav managing.png

Когда происходит работа с точкой [math] B\ split\ event'[/math]а, необходимо разбить соответствующий полигон на две части, что соответствует разделению [math] \mathrm{LAV} [/math] данного полигона на два списка. И в каждый новый список нужно вставить копию вершины [math] V [/math], образующейся в точке пересечения [math] I [/math]. Обе вершины [math] V_1 [/math] и [math] V_2 [/math] указывают на разделяющее ребро [math] e_i [/math] (см. рисунок выше).

Частный случай множественных split event'ов на одном ребре

Skeleton collide edge.jpg

Уже должно было стать понятно, что алгоритм не строит промежуточного представления [math] \mathrm{straight}\ \mathrm{skeleton}[/math], а работает исключительно с рёбрами исходного полигона. Это приводит к ситуации (см. рисунок выше), когда одно ребро является общим для нескольких новых полигонов в промежуточном представлении (то есть одно ребро разбивается несколько раз), образовавшихся после разделения старого полигона. В случае, когда ребро уже разбито, и происходит следующий за ним [math]event[/math], необходимо правильно определить концы противолежащего ребра (то есть вершины/узлы, которые активны в текущем уровне конструирования крыши, как например вершины [math] X [/math] и [math] Y [/math] на рисунке ниже).

Skeleton multi edge.png

Например, в данном случае ребро [math] SY [/math] является частью ребра [math] e_i = ZY [/math], которое стягивается и должно теперь указывать на вершину [math] X [/math]. Когда произойдёт следующее событие в точке пересечения [math] B [/math], нам необходимо правильно указать ребро новой вершине в этой точке в [math] \mathrm{LAV} [/math]. Реальный конец ребра [math] e_i [/math] — точка [math] Z [/math], но мы хотим указать на ребро [math] XY [/math]. Это необходимо для поддержания корректности структуры [math] \mathrm{SLAV} [/math].

Чтобы решить эту проблему, следует хранить [math]split\ event[/math] как [math]3[/math] вершины — невыпуклая вершина и две вершины противолежащего ребра. Дополнительно нужно хранить ассоциативный массив из пары вершин в ребро для этих вершин. Тогда в момент разделения ребра [math]ZY[/math] необходимо удалить это ребро из ассоциативного массива и поместить туда два новых ребра [math]ZX[/math] и [math]XY[/math], которые будут ссылаться на исходное ребро [math] e_i [/math].

Но в очереди могло быть событие по трём вершинам исходного ребра, а после разделения этого ребра уже нет (например, такое может произойти, если с ребром одновременно сталкивается несколько невыпуклых вершин, лежащих на параллельной этому ребру прямой). Посмотрев в ассоциативный массив, можно обнаружить, что такой пары вершин нет. Однако нам нужно всё же получить по ребру требуемую пару вершин. Для этого можно хранить ещё один ассоциативный массив из пар в рёбра, только из него уже не удалять старые пары. Тогда станет возможным получение по паре вершин ребра, а потом по ребру можно будет получить все актуальные пары вершин, соответствующих этому ребру, и добавить [math]split\ event[/math] с нужной парой вершин.

Алгоритм для невыпуклых полигонов

Шаг 1. Инициализация:

[math](a)[/math] Положим все вершины в [math] \mathrm{LAV}[/math], как это делается в алгоритме для выпуклых многоугольников, а потом [math] \mathrm{LAV}[/math] поместим в [math] \mathrm{SLAV}[/math].
[math](b)[/math] Найдём биссектрисы как в случае с выпуклым многоугольником.
[math](c)[/math] Для каждой биссектрисы выпуклой вершины найдём ближайшую точку пересечения с биссектрисой соседней вершины, а для невыпуклых вершин найдём также точки пересечения с противолежащими рёбрами (как это описывалось раньше) и положим в приоритетную очередь ближайшую точку пересечения [math] I [/math]. Будем также с этой точкой хранить её тип — [math] edge\ event[/math] или [math] split\ event[/math].

Шаг 2. Пока очередь не пуста:

[math](a)[/math] Извлечём точку пересечения [math] I [/math] из приоритетной очереди. Если она имеет тип [math] edge\ event[/math], то её надо обработать так же, как в шагах [math] 2b-2f[/math] алгоритма для выпуклых полигонов. Иначе выполнять шаги ниже.
[math](b)[/math] Если точка пересечения указывает на уже обработанные вершины, то продолжить со следующей итерации цикла шага 2, как в случае с выпуклым полигоном. По этой причине мы не будем обрабатывать лишние [math] split\ event'[/math]ы, хотя вполне могли их добавить в очередь.
[math](c)[/math] Нужно сделать примерно то же самое, что и шаге [math]2c[/math] алгоритма для выпуклых многоугольников. Только на этом цикл не завершается, а продолжается с новой итерации, так как многоугольник мог разделиться на несколько частей, и, возможно, мы обработали лишь один подполигон и не последний.
[math](d)[/math] Добавим в [math] \mathrm{straight}\ \mathrm{skeleton} [/math] ребро [math] IV [/math], где точка [math] I [/math] указывает на вершину [math] V [/math]. Для [math] split\ event'[/math]ов точки пересечения указывают ровно на одну вершину в [math] \mathrm{SLAV}[/math].
[math](e)[/math] Модифицируем теперь [math] \mathrm{SLAV}[/math]:
  • пометим вершину [math] V [/math] как обработанную,
  • создадим две новые вершины [math] V_1 [/math] и [math] V_2 [/math] с одинаковыми координатами точки пересечения [math] I [/math],
  • найдём для каждой вершины [math] V_1 [/math] и [math] V_2 [/math] противолежащее ребро в своём подпалигоне,
  • разделим [math] \mathrm{LAV}[/math] с вершиной [math] V [/math] на две части (как показано на рисунке выше), вставим в части вершины [math] V_1 [/math] и [math] V_2 [/math], а затем обе части добавим в [math] \mathrm{SLAV}[/math]. Вершина [math] V_1 [/math] будет следующей для предыдующего к [math] V [/math] узла в [math] \mathrm{LAV}[/math] и предыдущей для конца противолежащего ребра. Аналогично для вершины [math] V_2 [/math],
  • удалим из ассоциативного массива пару вершин ребра [math] e_i [/math] и поместим две новых пары, в одной из которых будет вершина [math] V_1 [/math] и конец ребра [math] e_i [/math], а в другом — начало [math] e_i [/math] и вершина [math] V_2 [/math],
  • добавим указатели на соответствующие рёбра вершинам [math] V_1 [/math] и [math] V_2 [/math].
[math](f)[/math] Для обеих вершин [math] V_1 [/math] и [math] V_2 [/math]:
  • найдём биссектрисы между рёбрами, на которые эти вершины указывают в шаге [math]2e[/math],
  • найдём все события точек пересечения как в шаге [math] 1c [/math] (тут могут получиться события обоих типов),
  • сохраним точки пересечения, отвечающие найденным событиям, в приоритетной очереди.

Обработка [math] edge\ event'[/math]ов выполняется с такой же асимптотикой, как и в алгоритме для выпуклых полигонов. Но из-за того, что в очередь кладутся всевозможные точки, в которых произошли [math] split\ event'[/math]ы, в ней может оказаться [math]\mathcal{O}(n^2)[/math] элементов. Хотя обработка [math] split\ event'[/math]а может занять линейное время от числа вершин (если новая вершина в точке пересечения осталась невыпуклой), это произойдёт только для [math] split\ event'[/math]ов, которые создают новые вершины [math] S(P) [/math], а их [math]\mathcal{O}(n)[/math] по доказанной лемме. Остальные [math] split\ event'[/math]ы обработаются за [math]\mathcal{O}(1)[/math] в шаге [math] 2b [/math], поэтому итоговая асимптотика составит [math]\mathcal{O}(n^2 \log n)[/math].

Случай полигонов с дырками

Данный алгоритм может работать и с многоугольниками, содержащими дырки, если они ориентированы по часовой стрелке, чтобы внутренняя область многоугольника лежала слева от рёбер. И в самом начале алгоритма каждый замкнутый контур помещается в свой [math] \mathrm{LAV} [/math] в множестве [math] \mathrm{SLAV} [/math].

Skeleton hole example.png

Пример не для слабонервных

Skeleton big.png

Особенности реализации и другие частные случаи

Приведённый здесь алгоритм плох тем (кроме того, что медленно работает), что является довольно общим и не рассматривает возникающие на практике сложные частные случаи. Он будет работать на произвольных случайных полигонах, в которых возникают только простые события (картинка ниже) — в точке [math] a [/math] произошёл [math] edge\ event [/math], в точке [math] b [/math][math] split\ event [/math], а точки [math] c [/math] и [math] d [/math] уже внутри треугольников, и с ними разобраться просто.

Skeleton simple event example.jpg

Но на практике может возникнуть что-то менее тривиальное (картинка ниже): совпадение многих [math] edge\ event'[/math]ов в одной точке, многих [math] split\ event'[/math]ов, или даже в одной точке могут одновременно произойти события двух типов, а также многократное наложение параллельных рёбер друг на друга.

Skeleton complex event example.jpg

Параллельные противоположные рёбра

С точками [math] c [/math] и [math] d [/math] необходимо разбираться следующим образом: как только параллельные рёбра становятся соседними перед событием, нужно проверить, что после произошедшего события они соединятся потом в одно ребро. Если в [math] \mathrm{LAV} [/math] осталось только два параллельных ребра, то мы удаляем их из [math] \mathrm{SLAV} [/math].

Ещё примеры не для слабонервных.

Skeleton parallel edges.jpg

Skeleton more complex event example3.jpg

Параллельные "соседние" рёбра

Skeleton pce event example.jpg

Другой интересный случай возникает, когда несоседние параллельные рёбра становятся соседними после исчезания рёбер между ними. Такая проблема называется [math] \mathrm{PCE} [/math] (parallel consecutive edge problem). В таком случае можно поступать по-разному.

  • На левом рисунке используется [math]separate\ rule[/math] — согласно этому правилу два ребра рассматриваются отдельно. Тогда верно утверждение, что каждому ребру соответствует ровно одна грань. И в этом случае можно считать, что новая вершина на стыке двух рёбер движется перпендикулярно рёбрам.
  • На среднем рисунке используется [math]merge\ rule[/math] — рёбра в таком случае объединяются в одно новое ребро.

Отличить этот случай от предыдущего можно, посмотрев на ориентацию двух рёбер. Если они направлены в одну сторону, то это [math] \mathrm{PCE} [/math], если в противоположную, то разбираемся как в предыдущем случае.

Множественные события в одной точке

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

Чтобы научиться разбираться с такими случаями в алгоритме, когда мы уже поняли, что в одной точке будет несколько событий, введём понятие обобщённого события пересечения (англ. GIE, generalized intersection event).

Skeleton chain1.jpg

Для начала введём понятие цепочек рёбер, которые вовлечены в событие — такие рёбра, которые сталкиваются в данном событии. Эти цепи упорядочим согласно направлению рёбер (см. рисунок выше).

Skeleton chain2.jpg

Мы можем также упорядочить сами цепи вокруг точки события, объединив эти цепи в один циклический список. Следовательно, событие получается как бы окружено списком рёбер, которые участвуют в нём, при этом никакие другие рёбра не участвуют. Можно заметить (рисунки [math] c,\ d,\ e[/math] выше), что соседние рёбра в списке из изначально разных цепей становятся потом соседними в [math]\mathrm{LAV}[/math].

Алгоритм обработки GIE следующий:

  • Шаг внутри цепи: в каждой цепи удаляем внутренние рёбра (кроме первого и последнего) — это соответствует тому, что исчезает несколько рёбер, участвующих в одном [math]edge\ event'[/math]е. После этого шага остаются цепи только длин [math]1[/math] или [math]2[/math].
  • Шаг цепи из одного звена: цепи длины [math]1[/math] разбиваются в точке события (это соответствует простому [math]split\ event'[/math]у). Теперь все цепи имеют длину ровно [math]2[/math].
  • Шаг межцепной: объединяем соседние цепи (соответствующие одному событию) в циклический список, соединяя конец одной цепи с началом следующей и так далее. Поэтому каждая цепь разбивается в середине, и образуются новые списки длины [math]2[/math].
  • Шаг циклы из двух рёбер: списки [math]\mathrm{LAV}[/math] длины [math]2[/math] состоящие из двух параллельных рёбер, то есть ограничивающие полигон нулевой площади, удаляются из [math]\mathrm{SLAV}[/math].
  • Шаг PCE: разбираемся с [math] \mathrm{PCE} [/math] согласно принятому нами правилу решения — правилу слияния или правилу разделения.

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

Открытые реализации

Приведённый здесь алгоритм был реализован Fernando Cacciola[4], который исправил все ошибки в статье P. Felkel. И этот алгоритм используется в открытой библиотеке вычислительной геометрии CGAL[5]. Более того, он является одной из немногих открытых реализаций построения [math] \mathrm{straight}\ \mathrm{skeleton} [/math]. Но данный алгоритм достаточно медленный для решения практических задач. В реальной жизни используют его модификации или более сложные алгоритмы.

Другие алгоритмы

Существует простой в понимании и реализации алгоритм для построения [math] \mathrm{straigt}\ \mathrm{skeleton}[/math] на основе триангуляции, который работает за время [math] \mathcal{O}(n^3 \log n)[/math][6]. Aichholzer смог обобщить этот алгоритм для построения [math] \mathrm{straigt}\ \mathrm{skeleton}[/math] произвольного планарного графа[7]. Также автором в его оригинальной статье был представлен алгоритм построения данной структуры, базирующийся на понятии волнового фронта (англ. wavefront). Этот алгоритм может быть реализован за время [math] \mathcal{O}(n^3)[/math] с использованием [math] \mathcal{O}(n)[/math] памяти либо с использованием приоритетной очереди за время [math] \mathcal{O}(n^2 \log n)[/math] и [math] \mathcal{O}(n^2)[/math] памяти[8]. Известен алгоритм построения [math] \mathrm{straight}\ \mathrm{skeleton} [/math] для монотонных полигонов за время [math] \mathcal{O}(n \log n)[/math] с использованием [math] \mathcal{O}(n)[/math] памяти[9].

Также существует более эффективный алгоритм на основе мотографов, который придумали Stefan Huber и Martin Held. Их реализация называется [math]\mathrm{STALGO}[/math], и она доступна на их сайте[10].

См. также

Примечания

Источники информации