Straight skeleton
Существует целый класс структур типа [1].
, которые описывают базовые топологические свойства объектов. Структура была придумала Oswin Aichholzer. Она используются в различных практических задачах (проектирование крыш для зданий) и для доказательства некоторых теоремТопологические свойства
Определение: |
Straight skeleton (Angular Bisector Network, ABN) полигона без самопересечений называется планарный граф, определяющий разбиение полигона на регионы, границами которых являются стороны полигона, биссектрисы углов и отрезки, соединяющие вершины straight skeleton, образовавшиеся в результате сжатия полигона. |
Опишем подробней, как получается такое разбиение. Мы можем представить, будто все стороны прямоугольника параллельно двигаются внутрь с одинаковой постоянной скоростью, то есть многоугольник как бы сжимается внутрь. Тогда вершины будут двигаться вдоль биссектрис , а точки пересечения биссектрис будут соединять совпавшие участки сторон прямоугольника в конце движения. В каждый момент времени от начала движения рёбер мы получаем слоистую структуру (рис 1.). На рис. 2 синим цветом выделен — множество отрезков, образованных точками пересечения при движении сторон полигона. Чем-то структура похожа на строение крыши в домах (рис. 3). И для решения этой задачи как раз и может применяться: по стенам здания необходимо спроектировать его крышу.
Процесса стягивания многоугольника продолжается до тех пор, пока происходят его топологические изменения, то есть меняется число вершин в стянутом многоугольнике, и таким образом появляются новые вершины дерева
. Существуют два типа изменений, в ходе которых образуются новые вершины дерева:- — данное изменение происходит, когда сторона многоугольника полностью стягивается, делая соседние стороны инцидентными.
- происходит, когда ребро разбивается на два новых ребра, исходящих из точки преломления старого. Такое событие происходит на биссектрисе вогнутой вершины многоугольника. И тогда стягиваемая многоугольником область разбивается на две непересекающиеся многоугольные области.
На рисунке
ы изображён красным кругом, а ы — чёрным прямоугольником.Таким образом,
ы соответствуют внутренним вершинам , гранями являются области многоугольника, заметаемые сторонами многоугольника в процессе стягивания, дуги соединяют либо две внутренние вершины либо внутреннюю вершину с листом — вершиной многоугольника.Стоит также отметить, что в общем случае
ы могут быть нетривиальными. На рисунке ниже в случае в вершине совпали из вершины и ребра , а в случае совпали два а вершин и . Случаи и — простые и ы.Свойства Straight skeleton
Из процесса построения планарным графом. Ранее уже упоминалось, что он также является деревом. Будем обозначать простого полигона без самопересечений , в котором вершин, как . Тогда справедливы следующие леммы:
следует, что он являетсяЛемма (1): |
является деревом, содержит граней, не более внутренние вершины и не более рёбер. |
Доказательство: |
Каждая грань начинает образовываться во время стягивания ребра , и даже если на ребре произошёл , сама грань не могла разделиться. Построение грани завершается, когда ребро полностью стягивается. И это ребро дальше не может появиться снова, поэтому граней в столько, сколько сторон в многоугольнике, то есть ровно .То, что Внутренние вершины в является деревом, легко доказывается по индукции. База верна, когда внутренняя вершина всего одна. Тогда у листьями будут вершины многоугольника. Такой граф очевидным образом будет деревом. Если в внутренних вершин, то рассмотрим самый первый . Он закончился в какой-то внутренней вершине , у неё есть смежные листья — вершины, инцидентные этому ребру, — и из неё достижимы другие ы, с не более чем внутренними вершинами, и они являются деревьями по предположению индукцию. Тогда получаем, что для вершин тоже будет деревом. имеют степень не меньше — простой перебор всех случаев ов (степень будет больше, если в одной вершине совпало несколько событий). Так как имеет листьев, то внутренних вершин будет не больше , а так как является деревом, то рёбер у него будет не более . |
Замечание: если мы рассмотрим
в какой-то момент времени, то он вполне может содержать циклы (это видно на одном из рисунков выше). Однако его конечная структура будет деревом.Алгоритм с изпользованием SLAV
Далее будет описан алгоритм, придуманный Petr Felkel, который строит [2]. Однако этот алгоритм всё равно ещё достаточно медленный. В реальной жизни используют его модификации или более сложные алгоритмы.
за время , где — общее число вершин в полигоне, — число вогнутых вершин в полигоне. Немного модифицированный этот алгоритм используется в открытой библиотеке вычислительной геометрии CGALСначала алгоритм будет рассмотрен на простом случае — выпуклом многоугольнике, — а потом на невыпуклом многоугольнике.
Выпуклый полигон
В случае выпуклого многоугольника возникают только
ы по определению. Поэтому просто алгоритм можно описать следующим образом: найдём точки пересечения биссектрис многоугольника для каждой вершины со всеми соседними вершинами, возьмём такую точку, в которой произойдёт самый первый , добавим полученную вершину в , соеденим её с вершинами ребра, которое исчезло в процессе текущего а, а потом перестроим полигон, создав новую вершину и подвинув все остальные вдоль биссектрис на одинаковое расстояние. Будем продолжать этот процесс до тех пор, пока многоугольник не превратится в треугольник.Теперь реализуем этот алгоритм более эффективно. Для этого мы будем использовать специальную структуру данных — циклический список всех вершин многоугольника.
(set of circular lists of active vertices). Эта структура хранит цикл всех вершин для внешней грани, а так же цикл для каждой дыры многоугольника и для всех многоугольников, возникающих в процессе построения . В данном случае у нас будет просто —Эффективный алгоритм
Далее считаем, что полигон представлен рёбрами вдоль движения по контуру полигона против часовой стрелки.
Шаг 1. Инициализация:
- Поместим все вершины многоугольника в двусвязный циклический список в порядке обхода вдоль контура. Все вершины в считаются активными сейчас.
- Для каждой вершины в добавим указатели на инцидентные рёбра и , а также найдём луч биссектрисы .
- приоритетную очередь согласно — расстоянию от точки пересечения до одного из рёбер, инцидентных вершине . Для каждой точки пересечения будем так же хранить два указателя на вершины и — начала лучей биссектрис, которые пересекаются в точке . Эти указатели понадобятся в будущем, когда нужно будет определять соответствующие вершинам рёбра (см. рисунок ниже). Для каждой вершины найдём ближайшее пересечение биссектрисы лучами и . Если это пересечение существует, то положим его в
Шаг 2. Следующие действия выполняются в цикле, пока приоритетная очередь не пустая:
- Извлечём точку пересечения из приоритетной очереди.
- Если вершины и , соответствующие данной точке пересечения помечены как обработанные, то переходим к следующей итерации цикла шага 2. Это означает, что ребро между данными вершинами полностью стянулось (обработанные вершины и стянутые рёбра помечены крестом на рисунке ниже).
- Если осталось всего три вершины , то добавим в рёбра . В случае выпуклого многоугольника в этом месте можно завершить алгоритм. Но в общем случае нужно будет перейти к началу цикла снова.
- Добавим в рёбра .
- пометим вершины и как обработанные (напомню, что они обозначаются крестом на рисунке к данному алгоритму),
- создадим новую вершину в точке пересечения (отмечена квадратиком на рисунке),
- добавим вершину в , то есть между предыдущем к и следующим к узлами,
- добавим вершине указатели на соответствующие рёбра и .
Теперь необходимо модифицировать (детали на рисунке ниже):
- луч биссектрисы между рёбрами и ,
- точки пересечения луча b с соседями в , как в шаге
- сохраним ближайшие точки пересечения в приоритетной очереди.
Посчитаем дополнительные величины для вершины :
Заметим, что нам не нужно пересчитывать все расстояния в очереди приоритетов. Если мы стянем полигон до первого события исчезания ребра, то относительный порядок остальных событий не изменится. Нам необходимо только вставить новые точки пересечения в правильные места. Это можно эффективно сделать, если использовать структуру данных типа skip list.
Частным случаем в алгоритме может быть совпадение нескольких TODO: И что делать?(
ов в одной точке. Эти совпадения добавляются в шагах и , но могут быть относительно легко обработаны в шаге . Также может случиться, что какие-то рёбра не стянулись в итоге в одну вершину, а слились. Такое возможно, если какие-то стороны полигона были изначально параллельны (этот случай легко увидеть на прямоугольнике, не являющемся квадратом).Невыпуклый полигон
Алгоритм построения с помощью Motorcycle graph
Рассмотрим алгоритм построения мотографов.
на основеTODO: Алгоритм на мотографах
Другие алгоритмы
Существует простой в понимании и реализации алгоритм для построения триангуляции, который работает за время [3]. Aichholzer смог обобщить этот алгоритм для построения произвольного планарного графа[4]. Также автором в его оригинальной статье был представлен алгоритм построения данной структуры, базирующийся на понятии волнового фронта (англ. wavefront). Этот алгоритм может быть реализован за время с использованием памяти либо с использованием приоритетной очереди за время и памяти[5]. Известен алгоритм построения для монотонных полигонов за время с использованием памяти[6].
на основеВ данном конспект был (P.S. точнее, ещё будет) представлен алгоритм на основе мотографов, который придумали Stefan Huber и Martin Held. Они говорят, что даже смогли реализовать этот алгоритм, но код нигде не выкладывали.
Примечания
- ↑ Wikipedia — Fold-and-cut theorem
- ↑ Stepan Obdrazalek, "The Angular bisector network Implementation and the CGAL library"
- ↑ Stefan Huber, Martin Held, "Straight Skeletons and their Relation to Triangulations"
- ↑ Oswin Aichholzer, Franz Aurenhammera, "Straight Skeletons for General Polygonal Figures in the Plane"
- ↑ Oswin Aichholzer, Franz Aurenhammera, "A Novel Type of Skeleton for Polygons"
- ↑ Therese Biedl, Martin Held, Stefan Huber, Dominik Kaaser, Peter Palfrader, "Straight Skeletons of Monotone Polygons"
Источники информации
- 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
- Визуализатор алгоритма