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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Источники информации)
(Алгоритм с изпользованием SLAV)
Строка 167: Строка 167:
 
===== Пример не для слабонервных =====
 
===== Пример не для слабонервных =====
 
[[Файл:skeleton_big.png|800px]]
 
[[Файл:skeleton_big.png|800px]]
 +
 +
==== Особенности реализации и другие частные случаи ====
 +
{{TODO | t = Совпадение нескольких split event'ов в одной точке}}
 +
{{TODO | t = Накладывание рёбер друг на друга}}
  
 
== Алгоритм построения с помощью Motorcycle graph ==
 
== Алгоритм построения с помощью Motorcycle graph ==

Версия 17:28, 4 декабря 2014

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

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

Определение:
Straight skeleton (Angular Bisector Network, ABN) полигона без самопересечений называется планарный граф, определяющий разбиение полигона на регионы, границами которых являются стороны полигона, биссектрисы углов и отрезки, соединяющие вершины straight skeleton, образовавшиеся в результате сжатия полигона.


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

Рис. 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] event' [/math]ы соответствуют внутренним вершинам [math] \mathrm{straight}\ \mathrm{skeleton} [/math], гранями являются области многоугольника, заметаемые сторонами многоугольника в процессе стягивания, дуги [math] \mathrm{straight}\ \mathrm{skeleton} [/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], где каждому ребру можно задавать вес, то есть скорость движения ребра. И эта скорость может быть даже отрицательной. Таким образом можно оффсетить полигоны и решать задачу motion planning. Задача [math] \mathrm{weighted}\ \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]

Каждая грань [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] \mathrm{straight}\ \mathrm{skeleton}\ k [/math] внутренних вершин, то рассмотрим самый первый [math] edge\ event[/math]. Он закончился в какой-то внутренней вершине [math] \mathrm{straight}\ \mathrm{skeleton} [/math], у неё есть смежные листья — вершины, инцидентные этому ребру, — и из неё достижимы другие [math] \mathrm{straight}\ \mathrm{skeleton}' [/math]ы, с не более чем [math] k - 1 [/math] внутренними вершинами, и они являются деревьями по предположению индукцию. Тогда получаем, что [math] S(P) [/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]

Замечание: если мы рассмотрим [math] \mathrm{straight}\ \mathrm{skeleton} [/math] в какой-то момент времени, то он вполне может содержать циклы (это видно на рисунке ниже). Однако его конечная структура будет деревом.

Skeleton example1.png

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

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

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

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

В случае выпуклого многоугольника возникают только [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] вершины имеют указатели на следующую и предыдущую вершину в порядке обхода контура, а так же указатели на инцидентные рёбра. Если представить процесс стягивания многоугольника, как будто у нас уже построена для него крыша, а мы двигаем вверх некоторую заметающую плоскость, где пересечение крыши и плоскости будет обозначать текущий слой, то можно заметить, что область полигона разбивается на несколько частей. Каждой части будет соответствовать свой [math] \mathrm{LAV}[/math], отсюда нам и нужен [math] \mathrm{SLAV}[/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](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],
  • точки пересечения луча b с соседями [math] V [/math] в [math] \mathrm{LAV}[/math], как в шаге [math] 1c [/math]
  • сохраним ближайшие точки пересечения в приоритетной очереди.

Skeleton convex example.png

Заметим, что нам не нужно пересчитывать все расстояния в очереди приоритетов. Если мы стянем полигон до первого события исчезания ребра, то относительный порядок остальных событий не изменится. Нам необходимо только вставить новые точки пересечения в правильные места. Это можно эффективно сделать, если использовать структуру данных типа skip list.

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

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

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

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

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

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

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

Частный случай: в этом месте также должна быть проверка на то, что противолежащее ребро не будет параллельно ни одному ребру вершины [math] V [/math]. Тогда рёбра могут накладываться друг на друга. TODO: И что делать?(

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

Skeleton lav managing.png

Когда происходит работа с точкой [math] B\ split\ event'[/math]а, то необходимо разбить соответствующий полигон на две части, что соответствует разделению [math] \mathrm{LAV} [/math] данного полигона на два списка. И в каждый новый список нужно вставить новую вершину [math] X [/math], образующуюся в точке пересечения [math] B [/math]. Обе вершины [math] X [/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] на рисунке ниже).

Например, в данном случае ребро [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] S [/math]. Это решает проблему, так как никакое ребро не будет разделено дважды, а определение концов разделяемого ребра выполняется просто. Вставка вершины для точки [math] B [/math] в [math] \mathrm{LAV} [/math] тоже происходит относительно просто, потому что мы знаем точно, с каким ребром эта вершина связана. Но такой подход требует отдельно рассматривать вершины типа [math] S [/math], чтобы не добавить их случайно в [math] \mathrm{straight}\ \mathrm{skeleton}[/math].

Второй способ (используемый в авторском решении)

Идея заключается в том, чтобы хранить только вершины, которые реально будут в [math] \mathrm{straight}\ \mathrm{skeleton}[/math], а указатели на разделямое ребро хранятся во всех подполигонах, для которых это ребро является общим. Это приводит к множественным попаданиям [math] split\ event'[/math]ов на одно ребро.

Для примера, два полигона на рисунке выше разделяют общую ссылку на ребро [math] e_i [/math]. Во время процесса обработки вершины [math] B [/math] многоугольник [math] XMVNY [/math] разбивается на две части [math] XMB [/math] и [math] BNY [/math], а вершина [math] V [/math] помечается как обработанная.

Всё это нужно для того, чтобы правильно связать [math] B [/math] с вершинами [math] X [/math] и [math] Y [/math], а не с [math] Z [/math] и [math] Y [/math]. Во время обхода [math] \mathrm{SLAV} [/math] выбирается правильная часть ребра [math] e_i [/math] (в данном случае она определяется вершинами [math] X [/math] и [math] Y [/math]). Определяется следующим образом: вершина [math] B [/math] лежит справа от биссектрисы посещённой вершины [math] Y [/math] и слева от биссектрисы предка посещённой вершины [math] X [/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](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] 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] split\ event'[/math]ов, когда нам нужно пробежаться по всем рёбрам и найти противолежащее. Отсюда и получается итоговая асимптотика [math] \mathcal{O}(n^2) [/math].

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

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

Skeleton hole example.png

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

Skeleton big.png

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

TODO: Совпадение нескольких split event'ов в одной точке

TODO: Накладывание рёбер друг на друга

Алгоритм построения с помощью Motorcycle graph

Рассмотрим алгоритм построения [math] \mathrm{straigt}\ \mathrm{skeleton}[/math] на основе мотографов.

TODO: Алгоритм на мотографах

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

Существует простой в понимании и реализации алгоритм для построения [math] \mathrm{straigt}\ \mathrm{skeleton}[/math] на основе триангуляции, который работает за время [math] \mathcal{O}(n^3 \log n)[/math][3]. Aichholzer смог обобщить этот алгоритм для построения [math] \mathrm{straigt}\ \mathrm{skeleton}[/math] произвольного планарного графа[4]. Также автором в его оригинальной статье был представлен алгоритм построения данной структуры, базирующийся на понятии волнового фронта (англ. 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] памяти[5]. Известен алгоритм построения [math] \mathrm{straight}\ \mathrm{skeleton} [/math] для монотонных полигонов за время [math] \mathcal{O}(n \log n)[/math] с использованием [math] \mathcal{O}(n)[/math] памяти[6].

В данном конспект был (P.S. точнее, ещё будет) представлен алгоритм на основе мотографов, который придумали Stefan Huber и Martin Held. Они говорят, что даже смогли реализовать этот алгоритм, но код нигде не выкладывали.

См. также

Примечания

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