222
правки
Изменения
м
Нет описания правки
== Visibility graph ==
[[Файл:trap.png|200px|thumb|left|Путь с препятствиями через трапецоидную карту]]
[[Файл:notShort.png|200px300px|thumb|right|Такой путь не самый короткий]]
В общем, когда мы ищем путь от точки <tex> S </tex> до <tex> T </tex> с препятствиями (надо уточнить, что двигаем мы точку, а не какой-то полигон), можно построить [[Трапецоидная карта | трапецоидную карту]], соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе [[Алгоритм Дейкстры | Дейкстрой]] найти путь от <tex> S </tex> до <tex> T </tex>. Но этот путь не будет кратчайшим(кэп).
==== <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>. Итого что хотели.
==== <tex> O(n ^ 2) </tex> ====
Каким-то магическим образом, можно избавиться и от логарифма в асимптотике. Это делается с помощью [http://bit.ly/1eEqTzk rotation tree]. Про него рассказывал Антон Ков., но как-то мутно и не очень понятно. Суть такова, что мы обходим вершины в таком хитром порядке, что почти не просматриваем лишнее и получаем асимптотику {{---}} квадрат.
== Motion planning ==
В общем тут все очевидно. Тут мы просто двигаем не точку, а произвольный выпуклый полигон. Если мы его не можем вращать, просто "обводим" препятствия нашим полигоном (запиливаем [[Сумма Минковского (определение, вычисление)|сумму Минковского]] препятствий и полигона) и получаем другие препятствия, но зато теперь мы двигаем точку. А это мы уже научились делать выше.
