222
правки
Изменения
→Visibility graph
== Visibility graph Нахождение пути между точками с препятствиями ==
{|align="right"
|-valign="top"
Обычно эта задача решается с помощью [[Трапецоидная карта | трапецоидной карты]], по которой строится граф, ребра которого соединяют центры трапедоидов и вершины <tex> S </tex> и <tex> T </tex> с серединами вертикальных сторон трапецоидов. В этом графе любым алгоритмом поиска кратчайших путей (например, алгоритмом [[Алгоритм Дейкстры|Дейкстры]] или [[Алгоритм A*|A*]]) находится путь от <tex> S </tex> до <tex> T </tex>.
Данный алгоритм работает за <tex> O(n \log n) </tex> и за линейное количество памяти и идеально подходит для нахождения какого-нибудь пути между конечными вершинами. Но иногда нужно найти кратчайший путь, и этот алгоритм не подходит, хоть и дает хорошее приближение. Однако решения нахождения кратчайшего пути в лучшем случае работают за <tex> O(n^2) </tex> времени и памяти (здесь и далее <tex> n </tex> {{---}} количество всех вершин).
Для простоты рассуждений вершины <tex> S </tex> и <tex> T </tex> будем считать вершинами полигонов.
}}
По доказанным леммам любое ребро кратчайшего пути содержится в графе, таким образом для нахождения кратчайшего пути осталось найти кратчайший путь в этом графе от <tex> S </tex> до <tex> T </tex>. Рассмотрим алгоритмы построения графа видимости.
=== Построение visibility графа ===
==== Наивный алгоритм. <tex> O(n ^ 3) </tex> ====
Если делать наивно, т. е. то есть для каждой пары вершин проверять можно ли добавить ли такое ребро(нет ли пересечений с полигонами), будет <tex> O(n^3) </tex>.
==== Lee’s Algorithm. <tex> O(n ^ 2 \log n) </tex> ====
