Straight skeleton

Эта статья находится в разработке!

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

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

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

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]ы — красным прямоугольником.

Таким образом, [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]ы.

Свойства 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] в какой-то момент времени, то он вполне может содержать циклы (это видно на рисунке ниже). Однако его конечная структура будет деревом.

Алгоритм с изпользованием 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. Однако этот алгоритм всё равно ещё достаточно медленный. В реальной жизни используют его модификации или более сложные алгоритмы.

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

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

В случае выпуклого многоугольника возникают только [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] — циклический список всех вершин многоугольника.

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

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

Шаг 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]
• сохраним ближайшие точки пересечения в приоритетной очереди.

Заметим, что нам не нужно пересчитывать все расстояния в очереди приоритетов. Если мы стянем полигон до первого события исчезания ребра, то относительный порядок остальных событий не изменится. Нам необходимо только вставить новые точки пересечения в правильные места. Это можно эффективно сделать, если использовать структуру данных типа 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].

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

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

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

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

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

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

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

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

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

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

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

В данном конспект был (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
• Визуализатор алгоритма