Straight skeleton

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

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

Определение:

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

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

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

Рис. 2 — дерево $\mathrm{straight}\ \mathrm{skeleton}$

Рис. 3 — пример крыши по $\mathrm{straight}\ \mathrm{skeleton}$

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

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

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

На рисунке $edge\ event'$ы изображены зелёным кругом, а $split\ event'$ы — красным прямоугольником.

Таким образом, $event'$ы соответствуют внутренним вершинам $\mathrm{straight}\ \mathrm{skeleton}$, гранями являются области многоугольника, заметаемые сторонами многоугольника в процессе стягивания, дуги $\mathrm{straight}\ \mathrm{skeleton}$ соединяют либо две внутренние вершины либо внутреннюю вершину с листом — вершиной многоугольника.

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

Задача построения такого $\mathrm{straight}\ \mathrm{skeleton}$ является частным случаем задачи построения $\mathrm{weighted}\ \mathrm{straight}\ \mathrm{skeleton}$, где каждому ребру можно задавать вес, то есть скорость движения ребра. И эта скорость может быть даже отрицательной. Таким образом можно оффсетить полигоны и решать задачу motion planning. Задача $\mathrm{weighted}\ \mathrm{straight}\ \mathrm{skeleton}$ является более сложной, и здесь рассматриваться не будет.

Свойства Straight skeleton

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

Лемма (1):

$S(P)$ является деревом, содержит $n$ граней, не более $n - 2$ внутренние вершины и не более $2 n - 3$ рёбер.

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

$\triangleright$

Каждая грань $f(e)$ начинает образовываться во время стягивания ребра $e$, и даже если на ребре произошёл $split\ event$, сама грань не могла разделиться. Построение грани $f(e)$ завершается, когда ребро $e$ полностью стягивается. И это ребро дальше не может появиться снова, поэтому граней в $S(P)$ столько, сколько сторон в многоугольнике, то есть ровно $n$. То, что $S(P)$ является деревом, легко доказывается по индукции числа вершин в многоугольнике. База: многоугольник является треугольником, в его $\mathrm{straight}\ \mathrm{skeleton}$ будет одна внутренняя вершина — точка пересечения биссектрис, — листьями будут вершины треугольника. Такой граф очевидным образом будет деревом. Переход: пусть для всех многоугольников с количеством вершин меньше $k$ $\mathrm{straight}\ \mathrm{skeleton}$ будет деревом. Рассмотрим самый первый $event$ в многоугольнике из $k$ вершин. Если это $edge\ event$, то появится новая вершина, которую мы соединим с инцидентными ребру вершинами, а так же с какой-то вершиной $\mathrm{straight}\ \mathrm{skeleton}$ полигона из $k - 1$ вершин. Получившийся граф будет деревом. Если это $split\ event$, то новая вершина соединяется с одной вершиной исходного полигона и с двумя вершинами $\mathrm{straight}\ \mathrm{skeleton}$ для полигонов, в которых меньше $k$ вершин. В этом случае также получаем дерево. Внутренние вершины в $\mathrm{straight}\ \mathrm{skeleton}$ имеют степень не меньше $3$ — простой перебор всех случаев $event'$ов (степень будет больше, если в одной вершине совпало несколько событий). Так как $S(P)$ имеет $n$ листьев, то внутренних вершин будет не больше $n - 2$, а так как $S(P)$ является деревом, то рёбер у него будет не более $2 n - 3$.

$\triangleleft$

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

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

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

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

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

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

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

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

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

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

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

$(a)$ Поместим все вершины многоугольника $V_1, V_2 \dots V_n$ в двусвязный циклический список в порядке обхода вдоль контура. Все вершины в $\mathrm{LAV}$ считаются активными сейчас.

$(b)$ Для каждой вершины $V_i$ в $\mathrm{LAV}$ добавим указатели на инцидентные рёбра $e_{i-1} = V_{i-1}V_i$ и $e_i = V_i V_{i+1}$, а также найдём луч биссектрисы $b_i$.

$(c)$ Для каждой вершины $V_i$ найдём ближайшее пересечение биссектрисы $b_i$ с лучами $b_{i-1}$ и $b_{i+1}$. Если это пересечение существует, то положим его в приоритетную очередь согласно $L(e_i)$ — расстоянию от точки пересечения до одного из рёбер, инцидентных вершине $V_i$. Для каждой точки пересечения $I_i$ будем так же хранить два указателя на вершины $V_a$ и $V_b$ — начала лучей биссектрис, которые пересекаются в точке $I_i$. Эти указатели понадобятся в будущем, когда нужно будет определять соответствующие вершинам рёбра $e_a, e_b$ (см. рисунок ниже).

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

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

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

$(c)$ Если осталось всего три вершины $V_a, V_b, V_c$, то добавим в $\mathrm{straight}\ \mathrm{skeleton}$ рёбра $IV_a, IV_b, IV_c$. В случае выпуклого многоугольника в этом месте можно завершить алгоритм. Но в общем случае нужно будет перейти к началу цикла снова.

$(d)$ Добавим в $\mathrm{straight}\ \mathrm{skeleton}$ рёбра $IV_a, IV_b$.

$(e)$ Теперь необходимо модифицировать $\mathrm{LAV}$ (детали на рисунке ниже):

• пометим вершины $V_a$ и $V_b$ как обработанные (напомню, что они обозначаются крестом на рисунке к данному алгоритму),
• создадим новую вершину $V$ в точке пересечения $I$ (отмечена квадратиком на рисунке),
• добавим вершину $V$ в $\mathrm{LAV}$, то есть между предыдущем к $V_a$ и следующим к $V_b$ узлами,
• добавим вершине $V$ указатели на соответствующие рёбра $e_a$ и $e_b$.

$(f)$ Посчитаем дополнительные величины для вершины $V$:

• луч биссектрисы $b$ между рёбрами $e_a$ и $e_b$,
• точки пересечения луча b с соседями $V$ в $\mathrm{LAV}$, как в шаге $1c$
• сохраним ближайшие точки пересечения в приоритетной очереди.

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

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

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

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

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

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

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

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

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

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

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

Замечание: простой тест на пересечение биссектрисы вершины $V$ и целой линии, содержащей ребро, отсекает случаи тех рёбер, которые лежат позади вершины $V$.

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

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

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

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

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

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

Первый способ

Можно физически разделить исходное ребро на два, вставив новую точку $S$. Это решает проблему, так как никакое ребро не будет разделено дважды, а определение концов разделяемого ребра выполняется просто. Вставка вершины для точки $B$ в $\mathrm{LAV}$ тоже происходит относительно просто, потому что мы знаем точно, с каким ребром эта вершина связана. Но такой подход требует отдельно рассматривать вершины типа $S$, чтобы не добавить их случайно в $\mathrm{straight}\ \mathrm{skeleton}$.

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

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

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

Всё это нужно для того, чтобы правильно связать $B$ с вершинами $X$ и $Y$, а не с $Z$ и $Y$. Во время обхода $\mathrm{SLAV}$ выбирается правильная часть ребра $e_i$ (в данном случае она определяется вершинами $X$ и $Y$). Определяется следующим образом: вершина $B$ лежит справа от биссектрисы посещённой вершины $Y$ и слева от биссектрисы предка посещённой вершины $X$.

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

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

$(a)$ Положим все вершины в $\mathrm{LAV}$, как это делается в алгоритме для выпуклых многоугольников, а потом $\mathrm{LAV}$ поместим в $\mathrm{SLAV}$.

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

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

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

$(a)$ Извлечём точку пересечения $I$ из приоритетной очереди. Если она имеет тип $edge\ event$, то её надо обработать так же, как в шагах $2b-2f$ алгоритма для невыпуклых полигонов. Иначе выполнять шаги ниже.

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

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

$(d)$ Добавим в $\mathrm{straight}\ \mathrm{skeleton}$ ребро $IV$, где точка $I$ указывает на вершину $V$. Для $split\ event'$ов точки пересечения указывают ровно на одну вершину в $\mathrm{SLAV}$.

$(e)$ Модифицируем теперь $\mathrm{SLAV}$:

• пометим вершину $V$ как обработанную,
• создадим две новые вершины $V_1$ и $V_2$ с одинаковыми координатами точки пересечения $I$,
• найдём для каждой вершины $V_1$ и $V_2$ противолежащее ребро в своём подпалигоне,
• разделим $\mathrm{LAV}$ с вершиной $V$ на две части (как показано на рисунке выше), вставим в части вершины $V_1$ и $V_2$, а затем обе части добавим в $\mathrm{SLAV}$. Вершина $V_1$ будет следующей для предыдующего к $V$ узлу в $\mathrm{LAV}$ и предыдущей для конца противолежащего ребра. Аналогично для вершины $V_2$. Этот шаг в действительно разбивает полигон на две части,
• Добавим указатели вершинам $V_1$ и $V_2$ на соответствующие рёбра.

$(f)$ Для обеих вершин $V_1$ и $V_2$:

• найдём биссектрисы между рёбрами, на которые эти вершины слинковались в шаге $2e$,
• найдём точки пересечения лучей с биссектрисами соседних вершин как в шаге $1c$ (тут могут получиться точки пересечения обоих типов),
• сохраним ближайшие точки пересечения в приоритетной очереди.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

• Диаграмма Вороного
• Триангуляция Делоне

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

• Wikipedia — Straight skeleton
• Designing roofs and drawing phylogenetic trees
• Eric Berberich, "Straight Skeleton, Computational Geometry and Geometric Computing Seminar"
• Petr Felkel, Stepan Obdrazalek, "Straight Skeleton Implementation"
• Engineering a weighted straight skeleton algorithm
• Визуализатор алгоритма