222
правки
Изменения
м
[[Файл:search.png|400px|thumb|right|Дерево поиска пересекаемых ребер]]
Ковалев сказал что это C помощью [http://bit.ly/1eEqTzk rotation tree] можно рассказывать по желаниюдостичь асимптотики <tex> O(n^2) </tex>.
Каким-то магическим образом, можно избавиться и от логарифма в асимптотике. Это делается с помощью [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>". /*мне лень это переводить, и так понятно/непонятно*/
В общем тут все очевидно. Тут мы просто двигаем не точку, а произвольный выпуклый полигон. Если мы его не можем вращать, просто "обводим" препятствия нашим полигоном (запиливаем делаем [[Сумма Минковского (определение, вычисление)|сумму Минковского]] препятствий и полигона, сдвинутого в начало координат какой-нибудь точкой) и получаем другие препятствия, но зато теперь мы двигаем точку. А это мы уже научились делать выше. Если же этот полигон можно вращать, то делаем примерно то же самое, только как-то по-хитрому. Нам про это, кажется, не рассказывали(или рассказывали так же:))
Нет описания правки
==== Наивный алгоритм. <tex> O(n ^ 3) </tex> ====
Если делать наивно, т. е. для каждой пары вершин проверять можно ли добавить ли такое ребро(нет ли пересечений с полигонами), будет <tex> O(n^3) </tex>.
==== Lee’s Algorithm. <tex> O(n ^ 2 \log n) </tex> ====
[[Файл:zam.png|400px300px|thumb|left|Заметание плоскости вращающимся лучом]][[Файл:zamrefr1.png|400px300px|thumb|right|Обновление статуса заметающей прямой]][[Файл:zamrefr2.png|400px300px|thumb|right|Обновление статуса заметающей прямой]][[Файл:zamrefr3.png|400px300px|thumb|right|Обновление статуса заметающей прямой]]
Однако можно это сделать за <tex> O(n ^ 2 \log n) </tex>. Для каждой вершины найдём все видимые из неё вершины при помощи метода плоского заметания. Нам нужно решить следующую задачу: на плоскости дано множество отрезков (рёбер препятствий) и точка <tex> p </tex>. Найти все концы отрезков, видимые из точки <tex> p </tex>. Будем заметать плоскость вращающимся лучом с началом в точке <tex> p </tex>. Статусом заметающей прямой будет отрезки, которые её пересекают, упорядоченные по возрастанию расстояния от точки <tex> p </tex> до точки пересечения. Точками событий будут концы отрезков. Итак, первым делом вершины <tex> w \in W </tex> сортируются по углу между лучом <tex> vw </tex> и вертикальной полуосью, проходящей через <tex> v </tex>. Затем происходит инициализация множества видимых вершин (по умолчанию, такое множество пустое). Далее начинается заметание плоскости. В порядке сортировки вершин для каждой из них выполняется проверка: видна ли вершина <tex> w </tex> из вершины <tex> v </tex>. Поскольку такая проверка означает наличие пересечений, которые хранятся в сбалансированном дереве, она может быть выполнена за <tex> O(\log n) </tex>. Если вершина видима, необходимо добавить её в список видимых вершин. И, наконец, вне зависимости от видимости вершины, необходимо изменить статус заметающей прямой. Для этого, для текущей вершины <tex> w </tex> необходимо удалить из списка текущих пересечений все рёбра (отрезки), которые заканчиваются в этой вершине (лежат слева от прямой <tex> vw </tex>) и добавить все рёбра (отрезки), которые в ней начинаются (лежат справа от прямой <tex> vw </tex>).
[http://igitur-archive.library.uu.nl/math/2006-1214-201604/overmars_88_new_methods.pdf visibility graph при помощи rotation tree]
== Motion planning ==
[[Файл:mink.png|200px|thumb|left|Раздуваем препятствия]]
[[Файл:mink2.png|400px|thumb|right|Логично же]]
== Источники ==
