Изменения

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

Visibility graph и motion planning

238 байт добавлено, 18:56, 9 февраля 2015
→‎Motion planning
== Motion planning ==
[[Файл:mink.png|200px|thumb|left|Раздуваем Изменяем препятствия]]
[[Файл:mink2.png|400px|thumb|right|Ищем путь для точки]]
Тут мы двигаем не точкуРассмотрим задачу нахождения кратчайшиго пути, а произвольный когда движимый объект {{---}} это выпуклый полигон. Например, робот, которого надо доставить из начальной в конечную точку. Если мы его не можем полигон вращатьнельзя, просто считаем configuration spaceзадача сводится к движению точки. Выбирается точка на полигоне, ткоторая принимается за начало координат. е. "обводим" В такой системе координат для каждого препятствия нашим полигоном (делаем считается [[Сумма Минковского (определение, вычисление)|сумму сумма Минковского]] препятствий и полигона, сдвинутого в начало координат какой-нибудь точкой) и получаем другие с полигоном. Получаются бОльшие препятствия, но зато теперь мы двигаем достаточно двигать точку. А это мы уже научились делать , что было описано выше.
Теперь рассмотрим случай, когда мы можем вращать полигон. Для начала построим [[Трапецоидная карта|трапецоидную карту]], как будто мы не можем вращать полигон. Теперь будем вращать полигон на малый угол, пока он не сделает полный оборот вокруг своей оси, и для каждого угла сделаем трапецоидную карту. Теперь разместим(мысленно) все карты друг над другом. Таким образом получится, что поворот на малый угол {{---}} это движение вверх/вниз между слоями. Осталось [[Пересечение многоугольников (PSLG overlaying)|попересекать]] соседние слои и добавить между ними ребра (помним что первый и последний слои одинаковы) и уже в этом графе найти путь.
Igorjan94
222
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/44814»

Навигация