Visibility graph и motion planning

Visibility graph

Путь с препятствиями через трапецоидную карту

Такой путь не самый короткий

Пусть мы ищем какой-то путь от точки [math] S [/math] до [math] T [/math] с препятствиями (сначала будем двигать точку, а не полигон). Для нахождения можно построить трапецоидную карту, соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе Дейкстрой найти путь от [math] S [/math] до [math] T [/math]. Но этот путь, очевидно, не будет кратчайшим.

Однако этот алгоритм обширно используется, так как трапецоидная карта дает хорошее приближение, строится за [math] O(n \log n) [/math] и занимает [math] O(n) [/math] памяти, в то время как visibility graph в лучшем случае строится за [math] O(n^2) [/math] и хранит [math] O(n^2) [/math] ребер.

Лемма:

Любой кратчайший путь от [math] S [/math] до [math] T [/math] с полигональными препятствиями представляет собой ломаную, вершины которой — вершины полигонов.

Доказательство:

[math]\triangleright[/math]

Short cut Пусть путь проходит(в смысле вершины) через какую-то другую точку. Рассмотрим окрестность этой точки. По неравенству треугольника мы сможем немножко срезать. Значит этот путь не кратчайший. Противоречие, значит лемма доказана.

[math]\triangleleft[/math]

Таким образом создадим visibility graph. Его вершины — вершины полигонов. Между вершинами [math] u [/math] и [math] v [/math] существует ребро, если из [math] u [/math] видна (mutually visible) [math] v [/math] (ребра полигонов тоже входят в этот граф). Теперь, если мы добавим к множеству вершин [math] S [/math] и [math] T [/math] (и ребра в видимые вершины), у нас получится граф, в котором опять же Дейкстрой находим кратчайший путь. По лемме любое ребро кратчайшего пути — ребро visibility графа, так что мы нашли то, что нужно.

Чтобы уменьшить объем графа, из него можно удалить ребра, по которым точно не пройдет путь.

Лемма:

Если из вершины [math] D [/math] видны вершины [math] A, B, C [/math], а из вершины [math] B [/math] видны [math] A, C [/math] и поворот [math] DBA [/math] не совпадает с поворотом [math] DBC [/math], то ребро [math] DB [/math] можно удалить. (См. поясняющую картинку справа)

Доказательство:

[math]\triangleright[/math]

Удаляем [math] BD [/math] Очевидно, что путь проходящий через ребро [math] BD [/math] будет длинее, чем через соседей точки [math] B [/math]. Так как по неравенству треугольника [math] AB + BD \lt AD [/math]

[math]\triangleleft[/math]

Построение visibility графа

Наивный алгоритм. [math] O(n ^ 3) [/math]

Если делать наивно, т. е. для каждой пары вершин проверять можно ли добавить ли такое ребро(нет ли пересечений с полигонами), будет [math] O(n^3) [/math].

Lee’s Algorithm. [math] O(n ^ 2 \log n) [/math]

Заметание плоскости вращающимся лучом

Обновление статуса заметающей прямой

Обновление статуса заметающей прямой

Обновление статуса заметающей прямой

Однако можно это сделать за [math] O(n ^ 2 \log n) [/math]. Для каждой вершины найдём все видимые из неё вершины при помощи метода плоского заметания. Нам нужно решить следующую задачу: на плоскости дано множество отрезков (рёбер препятствий) и точка [math] p [/math]. Найти все концы отрезков, видимые из точки [math] p [/math]. Будем заметать плоскость вращающимся лучом с началом в точке [math] p [/math]. Статусом заметающей прямой будет отрезки, которые её пересекают, упорядоченные по возрастанию расстояния от точки [math] p [/math] до точки пересечения. Точками событий будут концы отрезков. Итак, первым делом вершины [math] w \in W [/math] сортируются по углу между лучом [math] vw [/math] и вертикальной полуосью, проходящей через [math] v [/math]. Затем происходит инициализация множества видимых вершин (по умолчанию, такое множество пустое). Далее начинается заметание плоскости. В порядке сортировки вершин для каждой из них выполняется проверка: видна ли вершина [math] w [/math] из вершины [math] v [/math]. Поскольку такая проверка означает наличие пересечений, которые хранятся в сбалансированном дереве, она может быть выполнена за [math] O(\log n) [/math]. Если вершина видима, необходимо добавить её в список видимых вершин. И, наконец, вне зависимости от видимости вершины, необходимо изменить статус заметающей прямой. Для этого, для текущей вершины [math] w [/math] необходимо удалить из списка текущих пересечений все рёбра (отрезки), которые заканчиваются в этой вершине (лежат слева от прямой [math] vw [/math]) и добавить все рёбра (отрезки), которые в ней начинаются (лежат справа от прямой [math] vw [/math]).

Вершин у нас [math] O(n) [/math], сортим за [math] O(n \log n) [/math] плюс запросы в дереве за [math] O(n) * O(\log n) [/math]. Итого что хотели.

Overmars and Welzl’s Algorithm [math] O(n ^ 2) [/math]

visibility graph при помощи rotation tree

C помощью rotation tree можно достичь асимптотики [math] O(n^2) [/math].

Идея такова, что для каждой вершины заметающий луч пробегается от [math] -\pi / 2 [/math] до [math] \pi / 2 [/math]. В основном цикле получается, что мы вращаем все лучи одновременно. По определенным правилам определяем следующую вершину, таким образом некоторые вершины могут закончить свою "жизнь" раньше других. Чтобы понять эти правила, нужно разобраться в rotation tree, что можно сделать по желанию.

Motion planning

Раздуваем препятствия

Ищем путь для точки

Тут мы двигаем не точку, а произвольный выпуклый полигон. Если мы его не можем вращать, просто считаем configuration space, т. е. "обводим" препятствия нашим полигоном (делаем сумму Минковского препятствий и полигона, сдвинутого в начало координат какой-нибудь точкой) и получаем другие препятствия, но зато теперь мы двигаем точку. А это мы уже научились делать выше.

Теперь рассмотрим случай, когда мы можем вращать полигон.

Источники

• 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
• статья про visibility graphs
• Хабр