Straight skeleton
Существует целый класс структур типа , которые описывают базовые топологические свойства объектов. Структура была придумала Oswin Aichholzer[1]. Она используются в различных практических задачах (проектирование крыш для зданий), для доказательства некоторых теорем[2], а также имеет связь с диаграммой Вороного.
Топологические свойства
| Определение: |
| Straight skeleton (Angular Bisector Network, ABN) полигона без самопересечений определяет разбиение полигона на регионы, границами которых являются стороны полигона, биссектрисы углов и отрезки, соединяющие точки пересечения биссектрис. |
Опишем подробней, как получается такое разбиение. Мы можем представить, будто все стороны прямоугольника параллельно двигаются внутрь с одинаковой постоянной скоростью, то есть многоугольник как бы сжимается внутрь. Тогда вершины будут двигаться вдоль биссектрис , а точки пересечения биссектрис будут соединять совпавшие участки сторон прямоугольника в конце движения. В каждый момент времени от начала движения рёбер мы получаем слоистую структуру (рис 1.). На рис. 2 синим цветом выделен — множество отрезков, образованных точками пересечения при движении сторон полигона. Чем-то структура похожа на строение крыши в домах (рис. 3). И для решения этой задачи как раз и может применяться: по стенам здания необходимо спроектировать его крышу.
Процесса стягивания многоугольника продолжается до тех пор, пока происходят его топологические изменения, то есть меняется число вершин в стянутом многоугольнике, и таким образом появляются новые вершины дерева . Существуют два типа изменений, в ходе которых образуются новый вершины дерева:
- — данное изменение происходит, когда сторона многоугольника полностью стягивается, делая соседние стороны инцидентными.
- происходит, когда ребро разбивается на два новых ребра, исходящих из точки преломления старого. Такое событие происходит на биссектрисе вогнутой вершины многоугольника. И тогда стягиваемая многоугольником область разбивается на две непересекающиеся многоугольные области.
На рисунке ы изображён красным кругом, а ы — чёрным прямоугольником.
Таким образом, ы соответствуют внутренним вершинам , гранями являются области многоугольника, заметаемые сторонами многоугольника в процессе стягивания, дугам отвечают отрезки биссектрис.
Свойства Straight skeleton
Из процесса построения следует, что он является планарным графом. Ранее уже упоминалась, что он также является деревом. Будем обозначать полигона , в котором вершин (будем пока для простоты считать, что полигон не содержит внутри других полигонов), как . Тогда справедлива следующая лемма:
| Лемма (1): |
является деревом, содержит связных граней, внутренние вершины и рёбер. |
| Доказательство: |
| Каждая грань начинается образовываться во время стягивания ребра , и даже если на ребре произошёл , сама грань не могла разделиться. Построение грани завершается, когда ребро полностью стягивается. А новые рёбра появляться не могут, поэтому является деревом, а каждая грань будет связная. Поэтому граней в столько, сколько сторон в многоугольнике, внутренних вершин будет , а рёбер , что следует из того, что является деревом. |
| Лемма (2): |
ы могут исходить только из вогнутных вершин полигона. |
| Доказательство: |
| TODO: Доказательство |
Wavefront-алгоритм
Рассмотрим оригинальный алгоритм, который был предложен авторами этой структуры.
TODO: "Простой" алгоритм построения за n^3 (wavefront)
Другие алгоритмы
Известен алгоритм[3] построения для монотонных полигонов за время с использованием памяти. Существует и более сложный алгоритм[4], который строит за время , где — общее число вершин в полигоне, — число вогнутых вершин в полигоне.
