3622
правки
Изменения
Нет описания правки
== Wavefront-алгоритм ==
Рассмотрим оригинальный алгоритм, который был предложен авторами этой структуры.{{TODO | t = Алгоритм "Простой" алгоритм построения простой за n^3 log n (wavefront)}}
== Для монотонных многоугольников Другие алгоритмы ==Известен алгоритм<ref>[http://www.cs.bgu.ac.il/~eurocg14/papers/paper_9.pdf Straight Skeletons of Monotone Polygons]</ref> построения <tex> \mathrm{straight}\ \mathrm{TODO | t = Алгоритм 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{TODO | t = Алгоритм в общем виде skeleton} </tex> за n*m время <tex> \mathcal{O}(nm + n \log n)</tex>, где <tex> n </tex> {{---}}число вершин в полигоне, <tex> m </tex> {{---}} число вершин в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>.
== Примечания ==
== Источники информации ==
* [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]
