Straight skeleton

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

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

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

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

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

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

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

Лемма (2):

ы могут исходить только из вогнутных вершин полигона.

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

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

Wavefront-алгоритм

Рассмотрим оригинальный алгоритм, который был предложен авторами этой структуры.

TODO: "Простой" алгоритм построения за n^3 (wavefront)

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

Известен алгоритм^[3] построения для монотонных полигонов за время [math] \mathcal{O}(n \log n)[/math] с использованием [math] \mathcal{O}(n)[/math] памяти. Существует и более сложный алгоритм^[4], который строит за время , где [math] n [/math] — общее число вершин в полигоне, [math] m [/math] — число вогнутых вершин в полигоне.

Примечания

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

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

[2] Wikipedia — Fold-and-cut theorem

[3] Straight Skeletons of Monotone Polygons

[4] Petr Felkel, Stepan Obdrazalek, "Straight Skeleton Implementation"

[1]

[2]

[3]

[4]

Straight skeleton

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

Свойства Straight skeleton

Wavefront-алгоритм

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

Примечания

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

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты