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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Другие алгоритмы)
Строка 29: Строка 29:
  
 
== Другие алгоритмы ==
 
== Другие алгоритмы ==
Известен алгоритм<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 Straight Skeleton Implementation]</ref>, который строит <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> за время <tex> \mathcal{O}(nm + n \log n)</tex>, где <tex> n </tex> {{---}} общее число вершин в полигоне, <tex> m </tex> {{---}} число вогнутых вершин в полигоне.
+
Известен алгоритм<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, St�ep�an Obdr�z�alek, "Straight Skeleton Implementation"]</ref>, который строит <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> за время <tex> \mathcal{O}(nm + n \log n)</tex>, где <tex> n </tex> {{---}} общее число вершин в полигоне, <tex> m </tex> {{---}} число вогнутых вершин в полигоне.
  
 
== Примечания ==
 
== Примечания ==

Версия 22:24, 20 октября 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] и может применяться: по стенам здания необходимо спроектировать его крышу (рис. 5).

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

Процесса стягивания многоугольника продолжается до тех пор, пока происходят его топологические изменения, то есть меняется число вершин в стянутом многоугольнике, и таким образом появляются новые вершины дерева [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

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

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

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] — число вогнутых вершин в полигоне.

Примечания

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