Straight skeleton — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Источники информации)
м
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
  
−
Существует целый класс структур типа <tex>\mathrm{skeleton}</tex>, которые описывают базовые топологические свойства объектов. Структура <tex>\mathrm{straight}\ \mathrm{skeleton}</tex> была придумала Oswin Aichholzer<ref>[http://www.jucs.org/jucs_1_12/a_novel_type_of/Aichholzer_O.pdf Oswin Aichholzer, Franz Aurenhammera, "A Novel Type of Skeleton for Polygons"]</ref>. Она используются в различных практических задачах (проектирование крыш для зданий), для доказательства некоторых теорем<ref>[http://en.wikipedia.org/wiki/Fold-and-cut_theorem Wikipedia {{---}} Fold-and-cut theorem]</ref>, а также имеет связь с [[Диаграмма Вороного | диаграммой Вороного]].
+
Существует целый класс структур типа <tex>\mathrm{skeleton}</tex>, которые описывают базовые топологические свойства объектов. Структура <tex>\mathrm{straight}\ \mathrm{skeleton}</tex> была придумала Oswin Aichholzer<ref>[http://www.jucs.org/jucs_1_12/a_novel_type_of/Aichholzer_O.pdf Oswin Aichholzer, Franz Aurenhammera, "A Novel Type of Skeleton for Polygons"]</ref>. Она используются в различных практических задачах (проектирование крыш для зданий) и для доказательства некоторых теорем<ref>[http://en.wikipedia.org/wiki/Fold-and-cut_theorem Wikipedia {{---}} Fold-and-cut theorem]</ref>.
−
 
 
 
== Топологические свойства ==
 
== Топологические свойства ==
 
{{Определение
 
{{Определение

Версия 23:30, 25 октября 2014

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

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

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

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

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

Sk example1.jpg

Таким образом, [math] event' [/math]ы соответствуют внутренним вершинам [math] \mathrm{straight}\ \mathrm{skeleton} [/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] S(P) [/math] столько, сколько сторон в многоугольнике, внутренних вершин будет [math] n - 2 [/math], а рёбер [math] 2n - 3 [/math], что следует из того, что [math] S(P) [/math] является деревом.
[math]\triangleleft[/math]
Лемма (2):
[math] Split\ event'[/math]ы могут исходить только из вогнутных вершин полигона.
Доказательство:
[math]\triangleright[/math]
TODO: Доказательство
[math]\triangleleft[/math]

Wavefront-алгоритм

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

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

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

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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Straight_skeleton&oldid=40519»