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

Версия 01:51, 5 декабря 2014

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

Содержание

1 Топологические свойства
2 Свойства Straight skeleton
3 Алгоритм с изпользованием SLAV
- 3.1 Выпуклый полигон
  - 3.1.1 Алгоритм для выпуклых полигонов
  - 3.1.2 Частные случаи
- 3.2 Невыпуклый полигон
4 Алгоритм построения с помощью Motorcycle graph
5 Другие алгоритмы
6 См. также
7 Примечания
8 Источники информации

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

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

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

Рис. 1 — слои в разные моменты времени

Рис. 2 — дерево

Рис. 3 — пример крыши по

Проектирование крыши здания по готовым стенам

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

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

На рисунке [math]edge\ event'[/math]ы изображены зелёным кругом, а [math]split\ event'[/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]ы.

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

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

Свойства Straight skeleton

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

Лемма (1):

является деревом, содержит граней, не более внутренние вершины и не более рёбер.

Доказательство:

Каждая грань [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]k[/math] будет деревом. Рассмотрим самый первый [math]event[/math] в многоугольнике из [math]k[/math] вершин.

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

Внутренние вершины в имеют степень не меньше — простой перебор всех случаев ов (степень будет больше, если в одной вершине совпало несколько событий). Так как имеет листьев, то внутренних вершин будет не больше , а так как является деревом, то рёбер у него будет не более .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Извлечём точку пересечения из приоритетной очереди.

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

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

Добавим в рёбра .

Теперь необходимо модифицировать (детали на рисунке ниже):

пометим вершины [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] 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] \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].

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

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

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

В простейшем случае точка [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].

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

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

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

Уже должно было стать понятно, что алгоритм не строит промежуточного представления , а работает исключительно с рёбрами исходного полигона. Это приводит к ситуации (см. рисунок выше), когда одно ребро является общим для нескольких новых полигонов в промежуточном представлении (то есть одно ребро разбивается несколько раз), образовавшихся после разделения старого полигона. В случае, когда ребро уже разбито, и происходит следующий за ним [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]split\ event[/math] как [math]3[/math] вершины — невыпуклая вершина и две вершины противолежащего ребра. Дополнительно нужно хранить ассоциативный массив из пары вершин в ребро для этих вершин. Тогда в момент разделения ребра [math]ZY[/math] необходимо удалить это ребро из ассоциативного массива и поместить туда два новых ребра [math]ZX[/math] и [math]XY[/math], которые будут ссылаться на исходное ребро [math] e_i [/math].

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

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

Положим все вершины в , как это делается в алгоритме для выпуклых многоугольников, а потом поместим в .

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

Для каждой биссектрисы выпуклой вершины найдём ближайшую точку пересечения с биссектрисой соседней вершины, а для невыпуклых вершин найдём также точки пересечения с противолежащими рёбрами (как это описывалось раньше), и положим в приоритетную очередь ближайшую точку пересечения . Будем также с этой точкой хранить её тип — или .

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

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

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

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

Добавим в ребро , где точка указывает на вершину . Для ов точки пересечения указывают ровно на одну вершину в .

Модифицируем теперь :

пометим вершину [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]2e[/math],
найдём точки пересечения лучей с биссектрисами соседних вершин как в шаге [math] 1c [/math] (тут могут получиться точки пересечения обоих типов),
сохраним ближайшие точки пересечения в приоритетной очереди.

Обработка событий обоих типов выполняется с такой же асимптотикой, что и в алгоритме для выпуклых полигонов. Основной вклад в асимптотику вносит вычисление [math] split\ event'[/math]ов, когда нам нужно пробежаться по всем рёбрам и найти противолежащее. Отсюда и получается итоговая асимптотика [math] \mathcal{O}(n^2) [/math].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим алгоритм построения на основе мотографов.

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

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

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

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

См. также

Примечания

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

[1] Wikipedia — Fold-and-cut theorem

[2] Ambiguous weighted skeleton

[3] CGAL 4.5 — 2D Straight Skeleton and Polygon Offsetting

[4] Stefan Huber, Martin Held, "Straight Skeletons and their Relation to Triangulations"

[5] Oswin Aichholzer, Franz Aurenhammera, "Straight Skeletons for General Polygonal Figures in the Plane"

[6] Oswin Aichholzer, Franz Aurenhammera, "A Novel Type of Skeleton for Polygons"

[7] Therese Biedl, Martin Held, Stefan Huber, Dominik Kaaser, Peter Palfrader, "Straight Skeletons of Monotone Polygons"

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Строка 66: / Строка 66: @@
 === Выпуклый полигон ===
-В случае выпуклого многоугольника возникают только <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> {{---}} [[Список#Циклический список | циклический список]] всех вершин многоугольника.
@@ Строка 72: / Строка 72: @@
 [[Файл:skeleton_lav.jpg]]
-В таком списке частично найденного <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> вершины имеют указатели на следующую и предыдущую вершину в порядке обхода контура, а так же указатели на инцидентные рёбра. Если представить процесс стягивания многоугольника, как будто у нас уже построена для него крыша, а мы двигаем вверх некоторую заметающую плоскость, где пересечение крыши и плоскости будет обозначать текущий слой, то можно заметить, что область полигона разбивается на несколько частей. Каждой части будет соответствовать свой <tex> \mathrm{LAV}</tex>, отсюда нам и нужен <tex> \mathrm{SLAV}</tex>.
+В таком списке частично найденного <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> вершины имеют указатели на следующую и предыдущую вершину в порядке обхода контура, а так же указатели на инцидентные рёбра.
 ==== Алгоритм для выпуклых полигонов ====
-Далее считаем, что полигон представлен рёбрами вдоль движения по контуру полигона против часовой стрелки.
+Далее считаем, что полигон представлен рёбрами вдоль движения по контуру против часовой стрелки.
 '''Шаг 1.''' Инициализация:
 :<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>(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.''' Следующие действия выполняются в цикле, пока приоритетная очередь не пустая:
 :<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>(d)</tex> Добавим в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> рёбра <tex> IV_a, IV_b </tex>.
@@ Строка 93: / Строка 93: @@
 :<tex>(f)</tex> Посчитаем дополнительные величины для вершины <tex> V </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>.
 [[Файл:skeleton_convex_example.png|600px]]
-Заметим, что нам не нужно пересчитывать все расстояния в очереди приоритетов. Если мы стянем полигон до первого события исчезания ребра, то относительный порядок остальных событий не изменится. Нам необходимо только вставить новые точки пересечения в правильные места. Это можно эффективно сделать, если использовать структуру данных типа [[Список с пропусками | skip list]].
 В этом случае асимптотика алгоритма составляет <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> edge\ event</tex> или <tex> split\ event</tex>.
+Если представить процесс стягивания многоугольника, как будто у нас уже построена для него крыша, а мы двигаем вверх некоторую заметающую плоскость, где пересечение крыши и плоскости будет обозначать текущий слой, то можно заметить, что область полигона разбивается на несколько частей. Каждой части будет соответствовать свой <tex> \mathrm{LAV}</tex>, отсюда нам и нужен <tex> \mathrm{SLAV}</tex>.
 [[Файл:skeleton_split_event_example.png|400px]]
@@ Строка 118: / Строка 118: @@
 [[Файл: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>.
@@ Строка 127: / Строка 127: @@
 [[Файл: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> B </tex>. Обе вершины <tex> V_1 </tex> и <tex> V_2 </tex> указывают на разделяющее ребро <tex> e_i </tex> (см. рисунок выше).
 ==== Частный случай множественных split event'ов на одном ребре ====
 [[Файл: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> на рисунке ниже).
 [[Файл: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> 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> 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> 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>.
 ==== Алгоритм для невыпуклых полигонов ====
@@ Строка 152: / Строка 146: @@
 :<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>(a)</tex> Извлечём точку пересечения <tex> I </tex> из приоритетной очереди. Если она имеет тип <tex> edge\ event</tex>, то её надо обработать так же, как в шагах <tex> 2b-2f</tex> алгоритма для выпуклых полигонов. Иначе выполнять шаги ниже.
 :<tex>(b)</tex> Если точка пересечения указывает на уже обработанные вершины, то продолжить со следующей итерации цикла шага 2, как в случае с выпуклым полигоном.
 :<tex>(c)</tex> Нужно сделать примерно то же самое, что и шаге <tex>2c</tex> алгоритма для выпуклых многоугольников. Только на этом цикл не завершается, а продолжается с новой итерации, так как многоугольник мог разделиться на несколько частей, и, возможно, мы обработали лишь один подпалигон и не последний.
@@ Строка 161: / Строка 155: @@
 ::* найдём для каждой вершины <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>:
@@ Строка 169: / Строка 164: @@
 Обработка событий обоих типов выполняется с такой же асимптотикой, что и в алгоритме для выпуклых полигонов. Основной вклад в асимптотику вносит вычисление <tex> split\ event'</tex>ов, когда нам нужно пробежаться по всем рёбрам и найти противолежащее. Отсюда и получается итоговая асимптотика <tex> \mathcal{O}(n^2) </tex>.
-==== Случай полигонов с дырами ====
+==== Случай полигонов с дырками ====
-Данный алгоритм может работать и с многоугольниками, содержащими дыры, если они ориентированы по часовой стрелке, чтобы внутренняя область многоугольника лежала слева от рёбер. И в самом начале алгоритма каждый замкнутый контур помещается в свой <tex> \mathrm{LAV} </tex> в множестве <tex> \mathrm{SLAV} </tex>.
+Данный алгоритм может работать и с многоугольниками, содержащими дырки, если они ориентированы по часовой стрелке, чтобы внутренняя область многоугольника лежала слева от рёбер. И в самом начале алгоритма каждый замкнутый контур помещается в свой <tex> \mathrm{LAV} </tex> в множестве <tex> \mathrm{SLAV} </tex>.
 [[Файл:skeleton_hole_example.png|500px]]
@@ Строка 215: / Строка 210: @@
 [[Файл:skeleton_chain2.jpg]]
-Мы можем также упорядочить сами цепи вокруг точки события, объединив эти цепи в один циклический список. Таким образом событие получается как бы окружено списком рёбер, которые участвуют в этом событии, и никакие другие рёбра не участвуют. Можно заметить (рисунки <tex> c,\ d,\ e</tex> выше), что соседние рёбра в списке из изначально разных цепей становятся потом соседними в <tex>\mathrm{LAV}</tex>.
+Мы можем также упорядочить сами цепи вокруг точки события, объединив эти цепи в один циклический список. Таким образом событие получается как бы окружено списком рёбер, которые участвуют в этом событии, и никакие другие рёбра не участвуют. Можно заметить (рисунки <tex> c,\ d,\ e</tex> выше), что соседние рёбра в списке из изначально разных цепей становятся потом соседними в <tex>\mathrm{LAV}</tex>. И эти цепочки рёбер на самом деле не хранятся отдельными цепочками. Эти цепи и есть <tex>\mathrm{LAV}</tex>.
 Алгоритм обработки GIE следующий: