222
правки
Изменения
м
Эта задача решается Эту задачу можно решить с помощью [[Трапецоидная карта | трапецоидной карты]]. По ней строится граф, ребра которого соединяют центры трапедоидов, а также начальную и конечную вершины с серединами вертикальных сторон трапецоидов. В таком графе ищется путь между начальной и конечной вершинами.
Нет описания правки
Для начала рассмотрим движение материальной точки. Случай, когда размером и формой движимого объекта пренебречь нельзя, будет рассмотрен [[Visibility graph и motion planning#Motion planning|позднее]].
Данный алгоритм работает за <tex> O(n \log n) </tex> и за линейное количество памяти и хорошо подходит для нахождения какого-нибудь пути между конечными вершинами. Но иногда нужно найти кратчайший путь, и этот алгоритм не подходит, хоть и работает быстро. Однако, решения нахождения кратчайшего пути в лучшем случае работают за <tex> O(n^2) </tex> времени и памяти (здесь и далее <tex> n </tex> {{---}} количество всех вершин).
