Straight skeleton — различия между версиями
Shersh (обсуждение | вклад) |
Shersh (обсуждение | вклад) |
||
| Строка 17: | Строка 17: | ||
== Wavefront-алгоритм == | == Wavefront-алгоритм == | ||
| − | {{TODO | t = | + | Рассмотрим оригинальный алгоритм, который был предложен авторами этой структуры. |
| + | {{TODO | t = "Простой" алгоритм построения за n^3 (wavefront)}} | ||
| − | == | + | == Другие алгоритмы == |
| − | {{ | + | Известен алгоритм<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> {{---}} число вершин в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>. |
| − | |||
| − | |||
| − | {{ | ||
== Примечания == | == Примечания == | ||
| Строка 30: | Строка 28: | ||
== Источники информации == | == Источники информации == | ||
* [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] | * [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] | ||
Версия 01:33, 16 сентября 2014
Существует целый класс структур типа , которые описывают базовые топологические свойства объектов. Структура была придумала Oswin Aichholzer[1]. Она используются в различных практических задачах, для доказательства некоторых теорем[2], а также имеет связь с диаграммой Вороного.
Содержание
Топологические свойства
| Определение: |
| Straight skeleton (Angular Bisector Network, ABN) полигона без самопересечений определяет разбиение полигона на регионы, границами которых являются стороны полигона, биссектрисы углов и отрезки, соединяющие точки пересечения биссектрис. |
Опишем подробней, как получается такое разбиение. Мы можем представить, будто все стороны прямоугольника параллельно двигаются внутрь с одинаковой постоянной скоростью. Тогда вершины будут двигаться вдоль биссектрис , а точки пересечения биссектрис будут соединять совпавшие участки сторон прямоугольника в конце движения. В каждый момент времени от начала движения рёбер мы получаем слоистую структуру (рис 1.). Чем-то она похожа на строение крыши в домах (рис. 3). На рис. 2 синим цветом выделен — множество отрезков, образованных точками пересечения при движении сторон полигона.
Свойства дерева Straight skeleton
TODO: Леммы о свойствах структуры Straight skeleton
Wavefront-алгоритм
Рассмотрим оригинальный алгоритм, который был предложен авторами этой структуры.
TODO: "Простой" алгоритм построения за n^3 (wavefront)
Другие алгоритмы
Известен алгоритм[3] построения для монотонных полигонов за время с использованием памяти. Существует и более сложный алгоритм[4], который строит за время , где — число вершин в полигоне, — число вершин в .
