Изменения

Пусть мы ищем какой-то путь от точки <tex> S </tex> до <tex> T </tex> с препятствиями (сначала будем двигать точку, а не полигон). Для нахождения можно построить [[Трапецоидная карта | трапецоидную карту]], соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе [[Алгоритм Дейкстры | Дейкстрой]] найти путь от <tex> S </tex> до <tex> T </tex>. Но этот путь, очевидно, не будет кратчайшим.  Однако этот алгоритм обширно используется из-за быстроты(, так как трапецоидная карта дает хорошее приближение, строится за <tex> O(n \log n) </tex> и занимает <tex> O(n) </tex> памяти, в то время как visibility graph в лучшем случае строится за <tex> O(n^2) </tex> и хранит <tex> O(n^2) </tex> ребер.

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

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

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

[[Файл:mink2.png|400px|thumb|right|Логично жеИщем путь для точки]]Тут мы двигаем не точку, а произвольный выпуклый полигон. Если мы его не можем вращать, просто считаем configuration space, т. е. "обводим" препятствия нашим полигоном (делаем [[Сумма Минковского (определение, вычисление)|сумму Минковского]] препятствий и полигона, сдвинутого в начало координат какой-нибудь точкой) и получаем другие препятствия, но зато теперь мы двигаем точку. А это мы уже научились делать выше. Теперь рассмотрим случай, когда мы можем вращать полигон.