Straight skeleton

Материал из Викиконспекты
Версия от 22:32, 20 октября 2014; Shersh (обсуждение | вклад) (Другие алгоритмы)
Перейти к: навигация, поиск
Эта статья находится в разработке!

Существует целый класс структур типа skeleton, которые описывают базовые топологические свойства объектов. Структура straight skeleton была придумала Oswin Aichholzer[1]. Она используются в различных практических задачах, для доказательства некоторых теорем[2], а также имеет связь с диаграммой Вороного.

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

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

Опишем подробней, как получается такое разбиение. Мы можем представить, будто все стороны прямоугольника параллельно двигаются внутрь с одинаковой постоянной скоростью, то есть многоугольник как бы сжимается внутрь. Тогда вершины будут двигаться вдоль биссектрис , а точки пересечения биссектрис будут соединять совпавшие участки сторон прямоугольника в конце движения. В каждый момент времени от начала движения рёбер мы получаем слоистую структуру (рис 1.). На рис. 2 синим цветом выделен straight skeleton — множество отрезков, образованных точками пересечения при движении сторон полигона. Чем-то структура похожа на строение крыши в домах (рис. 3). И для решения этой задачи как раз straight skeleton и может применяться: по стенам здания необходимо спроектировать его крышу (рис. 5).

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

Процесса стягивания многоугольника продолжается до тех пор, пока происходят его топологические изменения, то есть меняется число вершин в стянутом многоугольнике, и таким образом появляются новые вершины дерева straight skeleton. Существуют два типа изменений, в ходе которых образуются новый вершины дерева:

  • Edge event — данное изменение происходит, когда сторона многоугольника полностью стягивается, делая соседние стороны инцидентными.
  • Split event происходит, когда ребро разбивается на два новых ребра, исходящих из точки преломления старого. Такое событие происходит на биссектрисе вогнутой вершины многоугольника.

На рисунке edge event изображён красным кругом, а split event — чёрным прямоугольником.

Sk example1.jpg

Свойства дерева Straight skeleton

TODO: Леммы о свойствах структуры Straight skeleton

Wavefront-алгоритм

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

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

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

Известен алгоритм[3] построения straight skeleton для монотонных полигонов за время O(nlogn) с использованием O(n) памяти. Существует и более сложный алгоритм[4], который строит straight skeleton за время O(nm+nlogn), где n — общее число вершин в полигоне, m — число вогнутых вершин в полигоне.

Примечания

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