3622
правки
Изменения
→Алгоритм с изпользованием SLAV
== Алгоритм с изпользованием SLAV ==
Далее будет описан алгоритм, придуманный Petr Felkel, который строит <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> за время <tex> \mathcal{O}(n^2 \log n)</tex>, где <tex> n </tex> {{---}} общее число вершин в полигоне. В оригинальной статье этому алгоритму даётся асимптотическая оценка <tex> \mathcal{O}(nm + n \log n)</tex>, или просто <tex> \mathcal{O}(n^2)</tex>, где <tex> m </tex> {{---}} число невыпуклых вершин в полигоне. Однако в статье содержатся ошибки. Модифицированный и исправленный Fernando Cacciola<ref>[https://www.cgal.org/UserWorkshop/2004/straight_skeleton.pdf Fernando Cacciola, "A CGAL implementation of the Straight Skeleton of a Simple 2D Polygon with Holes "]</ref> этот алгоритм используется поэтому данная в открытой библиотеке вычислительной геометрии CGAL<ref>[http://doc.cgal.org/latest/Straight_skeleton_2/index.html CGAL 4.5 {{---}} 2D Straight Skeleton and Polygon Offsetting]</ref>. Это единственная открытая реализация построения <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>. Однако данный алгоритм всё равно ещё достаточно медленный. В реальной жизни используют его модификации или более сложные алгоритмыней оценка неверна.
Сначала алгоритм будет рассмотрен на простом случае {{---}} выпуклом многоугольнике, {{---}} а потом на невыпуклом.
* '''Шаг циклы из двух рёбер:''' списки <tex>\mathrm{LAV}</tex> длины <tex>2</tex> состоящие из двух параллельных рёбер, то есть ограничивающие полигон нулевой площади, удаляются из <tex>\mathrm{SLAV}</tex>.
* '''Шаг PCE:''' разбираемся с <tex> \mathrm{PCE} </tex> согласно принятому нами правилу решения {{---}} правила слияния или правила разделения.
==== Открытые реализации ====
Приведённый здесь алгоритм был реализован Fernando Cacciola<ref>[https://www.cgal.org/UserWorkshop/2004/straight_skeleton.pdf Fernando Cacciola, "A CGAL implementation of the Straight Skeleton of a Simple 2D Polygon with Holes "]</ref>, который исправил все ошибки в статье P. Felkel. И этот алгоритм используется в открытой библиотеке вычислительной геометрии CGAL<ref>[http://doc.cgal.org/latest/Straight_skeleton_2/index.html CGAL 4.5 {{---}} 2D Straight Skeleton and Polygon Offsetting]</ref>. Более того он является одной из немногих открытых реализаций построения <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>. Однако данный алгоритм всё равно ещё достаточно медленный. В реальной жизни используют его модификации или более сложные алгоритмы.
== Алгоритм построения с помощью Motorcycle graph ==
