Изменения

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

Straight skeleton

23 байта убрано, 14:04, 2 декабря 2014
Алгоритм с изпользованием SLAV
== Алгоритм с изпользованием SLAV ==
Далее будет описан алгоритм, придуманный Petr Felkel, который строит <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> за время <tex> \mathcal{O}(nm + n \log n)</tex>, где <tex> n </tex> {{---}} общее число вершин в полигоне, <tex> m </tex> {{---}} число вогнутых вершин в полигоне. Немного модифицированный этот алгоритм используется в открытой библиотеке вычислительной геометрии CGAL<ref>[http://cmp.felk.cvut.cz/~xobdrzal/publications/bachelorthesis.pdf Stepan Obdrazalek, "The Angular bisector network Implementation and the CGAL library"]</ref>. Однако этот алгоритм всё равно ещё достаточно медленный. В реальной жизни используют его модификации этого алгоритма или более сложные алгоритмы.
== Алгоритм построения с помощью Motorcycle graph ==

Навигация