Visibility graph и motion planning

Конспект написан не до конца, но основные вещи уже есть.

Эта статья находится в разработке!

Visibility graph

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

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

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

Лемма:

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

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

[math]\triangleright[/math]

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

[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 графа, так что мы нашли то, что нужно.

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

[math] O(n ^ 3) [/math]

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

Дерево поиска пересекаемых ребер

[math] O(n ^ 2 \log n) [/math]

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

Для этого посортим все вершины по полярному углу (только те, которые справа нашей, ибо очевидно, что назад можно уже не смотреть) и запилим сбалансированное двоичное дерево поиска.

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

[math] O(n ^ 2) [/math]

Каким-то магическим образом, можно избавиться и от логарифма в асимптотике. Это делается с помощью rotation tree. Про него рассказывал Антон Ков., но как-то мутно и не очень понятно. Суть такова, что мы обходим вершины в таком хитром порядке, что почти не просматриваем лишнее и получаем асимптотику — квадрат.

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