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> нужно поместить в приоритетную очередь.
===== Множественные события в одной точке =====
Первая проблема, возникающая в этом случае {{---}} точное определение того, что несколько событий произошли в одной точке. Для определения совпадения нескольких событий в одной точке можно поступать приближённо: вводить с каждой точкой <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>.
== См. также ==
[[Категория: Вычислительная геометрия]]
[[Категория: Скалярное произведение Триангуляция Делоне и мерадиаграмма Вороного]]
[[Категория: Структуры данных]]
