3622
правки
Изменения
выпилено про мотографы так как про них никогда не будет написано
[[Файл: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_i </tex> вычисляются следующим образом: это точка пересечения биссектрисы вершины <tex> V </tex> и биссектрисы угла, который образуется в точке пересечения прямой, содержащей одно из рёбер, инцидентных <tex> V </tex>, и прямой, содержащей противолежащее ребро <tex> e_i </tex>. Все такие точки пересечения <tex> B_i </tex> нужно поместить в приоритетную очередь.
[[Файл:skeleton_lav_managing.png|600px]]
Когда происходит работа с точкой <tex> B\ split\ event'</tex>а, необходимо разбить соответствующий полигон на две части, что соответствует разделению <tex> \mathrm{LAV} </tex> данного полигона на два списка. И в каждый новый список нужно вставить копию вершины <tex> V </tex>, образующейся в точке пересечения <tex> B I </tex>. Обе вершины <tex> V_1 </tex> и <tex> V_2 </tex> указывают на разделяющее ребро <tex> e_i </tex> (см. рисунок выше).
==== Частный случай множественных split event'ов на одном ребре ====
[[Файл:skeleton_multi_edge.png|600px]]
Например, в данном случае ребро <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>split\ event</tex> как <tex>3</tex> вершины {{---}} невыпуклая вершина и две вершины противолежащего ребра. Дополнительно нужно хранить [[Хеш-таблица | ассоциативный массив]] из пары вершин в ребро для этих вершин. Тогда в момент разделения ребра <tex>ZY</tex> необходимо удалить это ребро из ассоциативного массива и поместить туда два новых ребра <tex>ZX</tex> и <tex>XY</tex>, которые будут ссылаться на исходное ребро <tex> e_i </tex>.
Но в очереди могло быть событие по трём вершинам исходного ребра, однако а после разделения этого ребра уже нет (например, такое может произойти, если с ребром одновременно сталкивается несколько невыпуклых вершин, лежащих на параллельной этому ребру прямой). Посмотрев в ассоциативный массив, можно обнаружить, что такой пары вершин нет. Хотя Однако нам нужно всё же получить по ребру требуемую пару вершин. Для этого можно хранить ещё один ассоциативный массив из пар в рёбра, только из него уже не удалять старые пары. Тогда станет возможным получение по паре вершин ребра, а потом по ребру можно будет получить все актуальные пары вершин, соответствующих этому ребру, и добавить <tex>split\ event</tex> с нужной парой вершин.
==== Алгоритм для невыпуклых полигонов ====
:<tex>(a)</tex> Положим все вершины в <tex> \mathrm{LAV}</tex>, как это делается в алгоритме для выпуклых многоугольников, а потом <tex> \mathrm{LAV}</tex> поместим в <tex> \mathrm{SLAV}</tex>.
:<tex>(b)</tex> Найдём биссектрисы как в случае с выпуклым многоугольником.
:<tex>(c)</tex> Для каждой биссектрисы выпуклой вершины найдём ближайшую точку пересечения с биссектрисой соседней вершины, а для невыпуклых вершин найдём также точки пересечения с противолежащими рёбрами (как это описывалось раньше), и положим в приоритетную очередь ближайшую точку пересечения <tex> I </tex>. Будем также с этой точкой хранить её тип {{---}} <tex> edge\ event</tex> или <tex> split\ event</tex>.
'''Шаг 2.''' Пока очередь не пуста:
:<tex>(a)</tex> Извлечём точку пересечения <tex> I </tex> из приоритетной очереди. Если она имеет тип <tex> edge\ event</tex>, то её надо обработать так же, как в шагах <tex> 2b-2f</tex> алгоритма для выпуклых полигонов. Иначе выполнять шаги ниже.
:<tex>(b)</tex> Если точка пересечения указывает на уже обработанные вершины, то продолжить со следующей итерации цикла шага 2, как в случае с выпуклым полигоном. По этой причине мы не будем обрабатывать лишние <tex> split\ event'</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>(e)</tex> Модифицируем теперь <tex> \mathrm{SLAV}</tex>:
::* создадим две новые вершины <tex> V_1 </tex> и <tex> V_2 </tex> с одинаковыми координатами точки пересечения <tex> I </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> 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>2e</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>.
==== Случай полигонов с дырками ====
[[Файл: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>.
Ещё примеры не для слабонервных.
Другой интересный случай возникает, когда несоседние параллельные рёбра становятся соседними после исчезания рёбер между ними. Такая проблема называется <tex> \mathrm{PCE} </tex> (''parallel consecutive edge problem''). В таком случае можно поступать по-разному.
* На левом рисунке используется <tex>separate\ rule</tex> {{---}} правило, когда согласно этому правилу два ребра рассматриваются отдельно. Тогда верно утверждение, что каждому ребру соответствует ровно одна грань. И в этом случае можно считать, что новая вершина на стыке двух рёбер движется перпендикулярно рёбрам.
* На среднем рисунке используется <tex>merge\ rule</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> согласно принятому нами правилу решения {{---}} правила правилу слияния или правила правилу разделения. В реализации это будет выглядеть следующим образом: можно посмотреть, что сейчас лежит в голове приоритетной очереди, и доставать события, пока они происходят в одной точке, а потом разбить эти события на цепочки и выполнять шаги из алгоритма выше.
==== Открытые реализации ====
Приведённый здесь алгоритм был реализован 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>. Однако Но данный алгоритм всё равно ещё достаточно медленныйдля решения практических задач. В реальной жизни используют его модификации или более сложные алгоритмы. == Алгоритм построения с помощью Motorcycle graph ==Рассмотрим алгоритм построения <tex> \mathrm{straigt}\ \mathrm{skeleton}</tex> на основе [[Motorcycle graph | мотографов]].{{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>.
== См. также ==
[[Категория: Вычислительная геометрия]]
[[Категория: Скалярное произведение Триангуляция Делоне и мерадиаграмма Вороного]]
[[Категория: Структуры данных]]
