Изменения

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

Visibility graph и motion planning

297 байт добавлено, 19:18, 24 января 2014
м
Lee’s Algorithm. O(n ^ 2 \log n)
[[Файл:search.png|400px|thumb|right|Дерево поиска пересекаемых ребер]]
==== Lee’s Algorithm. <tex> O(n ^ 2 \log n) </tex> ====
[[Файл:1.png|200px|thumb|left|Заметание плоскости вращающимся лучом]] Однако можно это сделать за <tex> O(n ^ 2 \log n) </tex>. Для каждой вершины найдём все видимые из неё вершины при помощи метода плоского заметания. Нам нужно решить следующую задачу: на плоскости дано множество отрезков (рёбер препятствий) и точка p. Найти все концы отрезков, видимые из точки p. Будем заметать плоскость вращающимся лучом с началом в точке p. Статусом заметающей прямой будет отрезки, которые её пересекают, упорядоченные по возрастанию расстояния от точки p до точки пересечения. Точками событий будут концы отрезков. Итак, первым делом вершины w ∈ W сортируются по углу между лучом vw и вертикальной полуосью, проходящей через v. Такая сортировка выполняется за O(nlog(n)), например, сортировкой слияниями. Затем происходит инициализация множества видимых вершин (по умолчанию, такое множество пустое). Далее начинается заметание плоскости. В порядке сортировки вершин для каждой из них выполняется проверка: видна ли вершина w из вершины v. Поскольку такая проверка означает наличие пересечений, которые хранятся в сбалансированном дереве, она может быть выполнена за O(log(n)). Если вершина видима, необходимо добавить её в список видимых вершин. И, наконец, вне зависимости от видимости вершины, необходимо изменить статус заметающей прямой. Для этого, для текущей вершины w необходимо удалить из списка текущих пересечений все рёбра (отрезки), которые заканчиваются в этой вершине (лежат слева от прямой vw) и добавить все рёбра (отрезки), которые в ней начинаются (лежат справа от прямой vw).
Вершин у нас <tex> O(n) </tex>, сортим за <tex> O(n \log n) </tex> плюс запросы в дереве за <tex> O(n) * O(\log n) </tex>. Итого что хотели.
[[Файл:2.png|200px|thumb|left|Обновление статуса заметающей прямой]]
[[Файл:3.png|200px|thumb|center|Обновление статуса заметающей прямой]]
[[Файл:4.png|200px|thumb|right|Обновление статуса заметающей прямой]]
==== Overmars and Welzl’s Algorithm <tex> O(n ^ 2) </tex> ====
222
правки

Навигация