Изменения

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

Visibility graph и motion planning

262 байта убрано, 22:46, 8 февраля 2015
м
Visibility graph
{{Определение
|definition =
Говорят, что вершина <tex> u </tex> <i> ''видна </i>'' (англ. mutually visible) из <tex> v </tex>, если отрезок <tex> uv </tex> не пересекает ни одного препятствия.
}}
{{Определение
|definition =
''Граф видимости'' (англ. visibility graph''' ) {{---}} граф, вершины которого {{---}} вершины полигонов. Между вершинами <tex> u </tex> и <tex> v </tex> существует ребро, если из <tex> u </tex> видна <tex> v </tex>.
}}
}}
По доказанным леммам любое ребро кратчайшего пути содержится в графе. Таким образом, таким образом для нахождения кратчайшего пути осталось найти кратчайший путь в этом графе от <tex> S </tex> начальной до <tex> T </tex>конечной вершины.
=== Построение visibility графа ===
==== Наивный алгоритм. <tex> O(n ^ 3) </tex> ====
Если делать наивно, то есть для Для каждой пары вершин проверять проверяем, можно ли добавить ли такое ребро(между ними, то есть нет ли пересечений с полигонами. <tex> O(n^2)</tex> пар вершин и <tex> O(n) </tex> ребер, будет то есть <tex> O(n^3) </tex>.
==== Lee’s Algorithm. <tex> O(n ^ 2 \log n) </tex> ====
|
[[Файл:Zam.png|300px|thumb|left|Заметание плоскости вращающимся лучом]]
Однако можно это сделать за <tex> O(n ^ 2 \log n) </tex>. Идея алгоритма проста : для каждой вершины найдем видимые из нее вершины независимо. Если научиться делать это за <tex> O(n \log n) </tex>, задача решена, так как всего точек <tex> n </tex>. Будем рассматривать точки слева направо, таким образом потребуется рассматривать только правую половину плоскости, так как ребра, которые должны идти в левую будут уже добавлены ранее.
Переформулируем задачу : дана точка <tex> v </tex> и множество отрезков {{---}} ребер препятствий.
222
правки

Навигация