Изменения

Перейти к: навигация, поиск

Straight skeleton

2410 байт добавлено, 01:08, 16 сентября 2014
Нет описания правки
{{В разработке}}
Структуры Существует целый класс структур типа <tex> \mathrm{skeleton }</tex> часто используются для описания топологических свойств , которые описывают базовые топологические свойства объектов. Структура <tex> \mathrm{2Dstraight}\ \mathrm{skeleton} </tex> объектовбыла придумала Oswin Aichholzer<ref>[http://www.jucs.org/jucs_1_12/a_novel_type_of/Aichholzer_O.pdf A Novel Type of Skeleton for Polygons]</ref>. НеформальноОна используются в различных практических задачах, а также для доказательства некоторых теорем<texref> skeleton <[http://en.wikipedia.org/wiki/tex> {{Fold-and-cut_theorem Fold-and-}} множество растровых точек, расположенных в центрах окружностей, включенных в объект и касающихся данной фигуры хотя бы в двух разных точкахcut theorem]</ref>.
== Топологические свойства ==
{{Определение
|id=defss
|definition=<tex> '''Straight\ skeleton</tex> ''' (Angular Bisector Network, ABN) {{---}} структура данныхполигона без самопересечений определяет разбиение полигона на регионы, состоящая из сегментов с прямыми сторонамиграницами которых являются стороны полигона, а стороны являются биссектрисами биссектрисы углов полигонаи отрезки, соединяющие точки пересечения биссектрис.
}}
[[Файл:Straight_skeleton_definition.png|right]]
Опишем подробней, как получается такое разбиение. Мы можем представить, будто все стороны прямоугольника параллельно двигаются внутрь с одинаковой постоянной скоростью. Тогда {{Acronym | вершины будут двигаться вдоль биссектрис | Очевидный факт}}, а точки пересечения биссектрис будут соединять совпавшие участки сторон прямоугольника в конце движения. В каждый момент времени от начала движения рёбер мы получаем слоистую структуру (рис 1.). Чем-то она похожа на строение крыши в домах (рис. 3). На рис. 2 синим цветом выделен <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> {{---}} множество отрезков, образованных точками пересечения при движении сторон полигона.
 
[[Файл:sk_example1.jpg|400px]]
 
== Свойства дерева Straigh skeleton ==
{{TODO | t = Леммы о свойствах структуры Straight skeleton}}
 
== Wavefront-алгоритм ==
{{TODO | t = Алгоритм построения простой за n^3 log n (wavefront)}}
 
== Для монотонных многоугольников ==
{{TODO | t = Алгоритм для монотонных многоугольников за n log n}}
 
== Сложный алгоритм ==
{{TODO | t = Алгоритм в общем виде за n*m + n log n}}
 
== Примечания ==
<references />
== Источники информации ==
* [http://en.wikipedia.org/wiki/Straight_skeleton Wikipedia {{---}} Straight skeleton]
* [http://www.dma.fi.upm.es/mabellanas/tfcs/skeleton/html/documentacion/straight%20skeletons%20implementation.pdf Straight Skeleton Implementation]
* [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]
[[Категория: Вычислительная геометрия]]
[[Категория: Скалярное произведение и мера]]
[[Категория: Структуры данных]]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/40008»

Навигация