222
правки
Изменения
м
Обычно эта Эта задача решается с помощью [[Трапецоидная карта | трапецоидной карты]]. По ней строится граф, ребра которого соединяют центры трапедоидов, а также начальную и конечную вершины с серединами вертикальных сторон трапецоидов. В таком графе ищется путь между начальной и конечной вершинами.
Нет описания правки
Для начала рассмотрим движение материальной точки. Случай, когда размером и формой движимого объекта пренебречь нельзя, будет рассмотрен [[Visibility graph и motion planning#Motion planning|позднее]].
Данный алгоритм работает за <tex> O(n \log n) </tex> и за линейное количество памяти и идеально хорошо подходит для нахождения какого-нибудь пути между конечными вершинами. Но иногда нужно найти кратчайший путь, и этот алгоритм не подходит, хоть и дает хорошее приближениеработает быстро. Однако, решения нахождения кратчайшего пути в лучшем случае работают за <tex> O(n^2) </tex> времени и памяти (здесь и далее <tex> n </tex> {{---}} количество всех вершин).
== Visibility graph ==
return visibilityGraph
</pre>
Здесь функция getVisibleVertices(<tex> v </tex>) возвращет возвращает все видимые из <tex> v </tex> вершины и выглядит так:
<pre>
vector<Vertex> getVisibleVertices(vertex v, set<segment> segments)
[[Файл:mink.png|200px|thumb|left|Изменяем препятствия]]
[[Файл:mink2.png|400px|thumb|right|Ищем путь для точки]]
Рассмотрим задачу нахождения кратчайшиго кратчайшего пути, когда движимый объект {{---}} это выпуклый полигон. Например, робот, которого надо доставить из начальной в конечную точку.
Если полигон вращать нельзя, задачу сводится к движению точки так : выбирается точка на полигоне, которая принимается за начало координат. В такой системе координат для каждого препятствия считается [[Сумма Минковского (определение, вычисление)|сумма Минковского]] с полигоном. Получаются бОльшие препятствия, но теперь достаточно двигать выбранную точку, что было описано выше.
