222
правки
Изменения
Нет описания правки
Каким-то магическим образом, можно избавиться и от логарифма в асимптотике. Это делается с помощью [http://bit.ly/1eEqTzk rotation tree]. Про него рассказывал Антон Ков., но как-то мутно и не очень понятно. Суть такова, что мы обходим вершины в таком хитром порядке, что почти не просматриваем лишнее и получаем асимптотику {{---}} квадрат.
Короче тут мы делаем то же самое, что и н2логн, только сортим не для каждой вершины отдельно, а рассматриваем все одновременно.
"The idea is simple: for each vertex, a scanline is kept which runs from <tex> -\pi / 2 </tex> to <tex> \pi / 2 </tex> hopping from vertex to vertex in its path. During the main loop, it appears that all of the scanlines are proceeding simultaneously. In fact, there are exact rules about determining the next vertex to process, and some vertices may finish their scan before others. To understand the rules about finding the next vertex, the rotation tree must be understood. A rotation tree is a rooted planar tree where each vertex is a node and points to its parent. There are two special nodes: <tex> +\infty </tex> and <tex> -\infty </tex>. Initially, all vertices point to <tex> -\infty </tex> as their parent and <tex> -\infty </tex> points to <tex> +\infty </tex>. Also stored is the rightmost child (if a node is a parent), and its right and left siblings (if they exist). The ordering of children is by slope: the one with the smallest slope is the leftmost. The loop that examines all pairs simply takes the rightmost leftmost leaf as the next segment to process and then reattaches it to the tree (while maintaining the property of being a rotation tree). It can reattach to the left of its parent or to the tangent of the chain above it. When a vertex attaches to <tex> +\infty </tex>, it is finished. The loop continues when all points have attached to <tex> +\infty </tex>".
/*мне лень это переводить, и так понятно/непонятно*/
== Motion planning ==
В общем тут все очевидно. Тут мы просто двигаем не точку, а произвольный выпуклый полигон. Если мы его не можем вращать, просто "обводим" препятствия нашим полигоном (запиливаем [[Сумма Минковского (определение, вычисление)|сумму Минковского]] препятствий и полигона) и получаем другие препятствия, но зато теперь мы двигаем точку. А это мы уже научились делать выше.
== Источники ==
* Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (2008), Computational Geometry: Algorithms and Applications (3rd edition), Springer-Verlag, ISBN 978-3-540-77973-5 Chapter 15 page 324-331
* [http://www.academia.edu/2845047/3D_Visibility_Graph not_bad.jpg статья про visibility graphs]
[[Категория: Вычислительная геометрия]]
