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}$ и может применяться: по стенам здания необходимо спроектировать его крышу.

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

Процесса стягивания многоугольника продолжается до тех пор, пока происходят его топологические изменения, то есть меняется число вершин в стянутом многоугольнике, и таким образом появляются новые вершины дерева $\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$ и $edge\ event$ ребра $e$, а в случае $(d)$ совпали два $split\ event'$а вершин $u_1$ и $u_2$. Случаи $(a)$ и $(b)$ — простые $edge$ и $split\ event'$ы.

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

$\triangleleft$

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

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

Далее будет описан алгоритм, придуманный Petr Felkel, который строит $\mathrm{straight}\ \mathrm{skeleton}$ за время $\mathcal{O}(nm + n \log n)$, где $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}$ — циклический список всех вершин многоугольника.

Эффективный алгоритм

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

Шаг 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.

Частным случаем в алгоритме может быть совпадение нескольких $edge\ event'$ов в одной точке. Эти совпадения добавляются в шагах $1c$ и $2f$, но могут быть относительно легко обработаны в шаге $2b$. Также может случиться, что какие-то рёбра не стянулись в итоге в одну вершину, а слились. Такое возможно, если какие-то стороны полигона были изначально параллельны (этот случай легко увидеть на прямоугольнике, не являющемся квадратом). TODO: И что делать?(

Алгоритм построения с помощью 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
• Визуализатор алгоритма