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://en.wikipedia.org/wiki/Fold-and-cut_theorem Wikipedia {{---}} Fold-and-cut theorem]</ref>.
 
== Топологические свойства ==
 
== Топологические свойства ==
 
{{Определение
 
{{Определение
Строка 42: Строка 42:
  
 
== Wavefront-алгоритм ==
 
== Wavefront-алгоритм ==
Существует простой в понимании и реализации алгоритм для построения <tex> \mathrm{straigt}\ \mathrm{skeleton}</tex> на основе [[Триангуляция полигонов (ушная + монотонная)|триангуляции]], который работает за время <tex> \mathcal{O}(n^3 \log n)</tex><ref>[http://www.sthu.org/research/publications/files/eurocg2010-slides.pdf Stefan Huber, Martin Held, "Straight Skeletons and their Relation to Triangulations"]</ref>
+
Рассмотрим алгоритм построения <tex> \mathrm{straigt}\ \mathrm{skeleton}</tex> на основе мотографов.
 +
{{TODO | t = Алгоритм на мотографах}}
  
Рассмотрим оригинальный алгоритм, который был предложен авторами этой структуры.
+
== Другие алгоритмы ==
{{TODO | t = "Простой" алгоритм построения за n^3 (wavefront)}}
+
Существует простой в понимании и реализации алгоритм для построения <tex> \mathrm{straigt}\ \mathrm{skeleton}</tex> на основе [[Триангуляция полигонов (ушная + монотонная)|триангуляции]], который работает за время <tex> \mathcal{O}(n^3 \log n)</tex><ref>[http://www.sthu.org/research/publications/files/eurocg2010-slides.pdf Stefan Huber, Martin Held, "Straight Skeletons and their Relation to Triangulations"]</ref>. Aichholzer смог обобщить этот алгоритм для построения <tex> \mathrm{straigt}\ \mathrm{skeleton}</tex> произвольного планарного графа<ref>[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.2586 Oswin Aichholzer, Franz Aurenhammera, "Straight Skeletons for General Polygonal Figures in the Plane"]</ref>. Также автором в его оригинальной статье был представлен алгоритм построения данной структуры, базирующийся на понятии '''волнового фронта''' (англ. ''wavefront''). Этот алгоритм может быть реализован за время <tex> \mathcal{O}(n^3)</tex> с использованием <tex> \mathcal{O}(n)</tex> памяти либо с использованием [[Двоичная куча | приоритетной очереди]] за время <tex> \mathcal{O}(n^2 \log n)</tex> и <tex> \mathcal{O}(n^2)</tex> памяти<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>. Известен алгоритм построения <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> для [[Триангуляция полигонов (ушная + монотонная)#def_monotone_polygon|монотонных полигонов]] за время <tex> \mathcal{O}(n \log n)</tex> с использованием <tex> \mathcal{O}(n)</tex> памяти<ref>[http://www.cs.bgu.ac.il/~eurocg14/papers/paper_9.pdf Therese Biedl, Martin Held, Stefan Hubert, Dominik Kaaser, Peter Palfrader, "Straight Skeletons of Monotone Polygons"]</ref>.
  
== Другие алгоритмы ==
+
Существует и более сложный алгоритм, придуманный Petr Felkel, который строит <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> за время <tex> \mathcal{O}(nm + n \log n)</tex>, где <tex> n </tex> {{---}} общее число вершин в полигоне, <tex> m </tex> {{---}} число вогнутых вершин в полигоне<ref>[http://www.dma.fi.upm.es/mabellanas/tfcs/skeleton/html/documentacion/straight%20skeletons%20implementation.pdf Petr Felkel, Stepan Obdrazalek, "Straight Skeleton Implementation"]</ref>. Немного модифицированный этот алгоритм используется в открытой библиотеке вычислительной геометрии CGAL<ref>[http://cmp.felk.cvut.cz/~xobdrzal/publications/bachelorthesis.pdf Stepan Obdrazalek, "The Angular bisector network Implementation and the CGAL library"]</ref>. Однако этот алгоритм всё равно ещё достаточно медленный. В реальной жизни используют модификации этого алгоритма или более сложные алгоритмы.
Известен алгоритм<ref>[http://www.cs.bgu.ac.il/~eurocg14/papers/paper_9.pdf Straight Skeletons of Monotone Polygons]</ref> построения <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> для монотонных полигонов за время <tex> \mathcal{O}(n \log n)</tex> с использованием <tex> \mathcal{O}(n)</tex> памяти. Существует и более сложный алгоритм<ref>[http://www.dma.fi.upm.es/mabellanas/tfcs/skeleton/html/documentacion/straight%20skeletons%20implementation.pdf Petr Felkel, Stepan Obdrazalek, "Straight Skeleton Implementation"]</ref>, который строит <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> за время <tex> \mathcal{O}(nm + n \log n)</tex>, где <tex> n </tex> {{---}} общее число вершин в полигоне, <tex> m </tex> {{---}} число вогнутых вершин в полигоне.
+
 
 +
В данном конспект был (P.S. точнее, ещё будет) представлен алгоритм на основе мотографов, который придумали Stefan Huber и Martin Held. Они говорят, что даже смогли реализовать этот алгоритм, но код нигде не выкладывали.
  
 
== Примечания ==
 
== Примечания ==
Строка 55: Строка 57:
 
== Источники информации ==
 
== Источники информации ==
 
* [http://en.wikipedia.org/wiki/Straight_skeleton Wikipedia {{---}} Straight skeleton]
 
* [http://en.wikipedia.org/wiki/Straight_skeleton Wikipedia {{---}} Straight skeleton]
* [http://www.sthu.org/research/publications/files/phdthesis.pdf Computing Straight Skeletons and Motorcycle Graphs: Theory and Practice]
 
 
* [https://liorpachter.wordpress.com/tag/straight-skeleton/ Designing roofs and drawing phylogenetic trees]
 
* [https://liorpachter.wordpress.com/tag/straight-skeleton/ Designing roofs and drawing phylogenetic trees]
 
* [http://resources.mpi-inf.mpg.de/departments/d1/teaching/ss10/Seminar_CGGC/Slides/09_Dinu_SSke.pdf Eric Berberich, "Straight Skeleton, Computational Geometry and Geometric Computing Seminar"]
 
* [http://resources.mpi-inf.mpg.de/departments/d1/teaching/ss10/Seminar_CGGC/Slides/09_Dinu_SSke.pdf Eric Berberich, "Straight Skeleton, Computational Geometry and Geometric Computing Seminar"]
* [http://cmp.felk.cvut.cz/~xobdrzal/publications/bachelorthesis.pdf Stepan Obdrazalek, "The Angular bisector network Implementation and the CGAL library"]
 
  
 
[[Категория: Вычислительная геометрия]]
 
[[Категория: Вычислительная геометрия]]
 
[[Категория: Скалярное произведение и мера]]
 
[[Категория: Скалярное произведение и мера]]
 
[[Категория: Структуры данных]]
 
[[Категория: Структуры данных]]

Версия 13:48, 26 октября 2014

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

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

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

Определение:
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]ы — чёрным прямоугольником.

Sk example1.jpg

Таким образом, [math] event' [/math]ы соответствуют внутренним вершинам [math] \mathrm{straight}\ \mathrm{skeleton} [/math], гранями являются области многоугольника, заметаемые сторонами многоугольника в процессе стягивания, дуги [math] \mathrm{straight}\ \mathrm{skeleton} [/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]ы.

Event example.png

Свойства 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] n [/math].

То, что [math] S(P) [/math] является деревом, легко доказывается по индукции. База верна, когда внутренняя вершина всего одна. Тогда у [math] \mathrm{straight}\ \mathrm{skeleton} [/math] листьями будут вершины многоугольника. Такой граф очевидным образом будет деревом. Если в [math] \mathrm{straight}\ \mathrm{skeleton}\ k [/math] внутренних вершин, то рассмотрим самый первый [math] edge\ event[/math]. Он закончился в какой-то внутренней вершине [math] \mathrm{straight}\ \mathrm{skeleton} [/math], у неё есть смежные листья — вершины, инцидентные этому ребру, — и из неё достижимы другие [math] \mathrm{straight}\ \mathrm{skeleton}' [/math]ы, с не более чем [math] k - 1 [/math] внутренними вершинами, и они являются деревьями по предположению индукцию. Тогда получаем, что [math] S(P) [/math] для [math] k [/math] вершин тоже будет деревом.

Внутренние вершины в [math] \mathrm{straight}\ \mathrm{skeleton} [/math] имеют степень не меньше [math] 3 [/math] — простой перебор всех случаев [math] event'[/math]ов (степень будет больше, если в одной вершине совпало несколько событий). Так как [math] S(P) [/math] имеет [math]n[/math] листьев, то внутренних вершин будет не больше [math] n - 2 [/math], а так как [math] S(P) [/math] является деревом, то рёбер у него будет не более [math] 2 n - 3 [/math].
[math]\triangleleft[/math]

Wavefront-алгоритм

Рассмотрим алгоритм построения [math] \mathrm{straigt}\ \mathrm{skeleton}[/math] на основе мотографов.

TODO: Алгоритм на мотографах

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

Существует простой в понимании и реализации алгоритм для построения [math] \mathrm{straigt}\ \mathrm{skeleton}[/math] на основе триангуляции, который работает за время [math] \mathcal{O}(n^3 \log n)[/math][2]. Aichholzer смог обобщить этот алгоритм для построения [math] \mathrm{straigt}\ \mathrm{skeleton}[/math] произвольного планарного графа[3]. Также автором в его оригинальной статье был представлен алгоритм построения данной структуры, базирующийся на понятии волнового фронта (англ. wavefront). Этот алгоритм может быть реализован за время [math] \mathcal{O}(n^3)[/math] с использованием [math] \mathcal{O}(n)[/math] памяти либо с использованием приоритетной очереди за время [math] \mathcal{O}(n^2 \log n)[/math] и [math] \mathcal{O}(n^2)[/math] памяти[4]. Известен алгоритм построения [math] \mathrm{straight}\ \mathrm{skeleton} [/math] для монотонных полигонов за время [math] \mathcal{O}(n \log n)[/math] с использованием [math] \mathcal{O}(n)[/math] памяти[5].

Существует и более сложный алгоритм, придуманный Petr Felkel, который строит [math] \mathrm{straight}\ \mathrm{skeleton} [/math] за время [math] \mathcal{O}(nm + n \log n)[/math], где [math] n [/math] — общее число вершин в полигоне, [math] m [/math] — число вогнутых вершин в полигоне[6]. Немного модифицированный этот алгоритм используется в открытой библиотеке вычислительной геометрии CGAL[7]. Однако этот алгоритм всё равно ещё достаточно медленный. В реальной жизни используют модификации этого алгоритма или более сложные алгоритмы.

В данном конспект был (P.S. точнее, ещё будет) представлен алгоритм на основе мотографов, который придумали Stefan Huber и Martin Held. Они говорят, что даже смогли реализовать этот алгоритм, но код нигде не выкладывали.

Примечания

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