222
правки
Изменения
м
→Построение visibility графа
=== Построение visibility графа ===
==== <tex> O(n ^ 3) </tex> ====
Если делать <s> в тупую</s> наивно, т. е. для каждой пары вершин проверять можно ли добавить ли такое ребро(нет ли пересечений с полигонами), будет <tex> O(n^3) </tex> (зато просто пилится).
[[Файл:search.png|400px|thumb|right|Дерево поиска пересекаемых ребер]]
==== <tex> O(n ^ 2 log n) </tex> ====
Однако можно это сделать за <tex> O(n ^ 2 log n) </tex>. Пусть мы хотим из вершины <tex> v </tex> найти все видимые из нее вершины. Теперь мы будем перебирать ребра не в случайном порядке, а так чтобы можно было проверять за логарифм.
Для этого посортим все вершины по полярному углу (только те, которые справа нашей, ибо очевидно, что назад можно уже не смотреть) и запилим сбалансированное двоичное дерево поиска.
Вершин у нас <tex> O(n) </tex>, сортим за <tex> O(n log n) </tex> плюс запросы в дереве за <tex> O(n) * O(log n) </tex>. Итого что хотели.
== Motion planning ==
