Изменения

<div style== Нахождение любого пути между точками с препятствиями =={|align="backgroundright"|-colorvalign="top"|[[Файл: #ABCDEF; font-sizetrap.png|200px|thumb|right|Путь с препятствиями через трапецоидную карту]]|[[Файл: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>notShort.png|300px|thumb|right|Такой путь не самый короткий]]|}<includeonly>Для начала рассмотрим движение материальной точки. Случай, когда размером и формой движимого объекта пренебречь нельзя, будет рассмотрен [[Категория: В разработкеVisibility graph и motion planning#Motion planning|позднее]]</includeonly>.

Если точки лежат внутри одного трапецоида {{---}} ответ найден. Иначе идём из стартовой точки в центр её трапецоида, далее по построенным рёбрам ищем трапецоид содержащий финальную точку. Для этого можно использовать поиск в ширину или другой алгоритм нахождения кратчайшего пути в графе. В общемконечном итоге, когда мы ищем соединяем середину последнего трапецоида с конечной вершиной. Данный алгоритм работает за <tex> O(n \log n) </tex> и за линейное количество памяти и хорошо подходит для нахождения какого-нибудь пути между парой данных вершин. Но если нужно найти кратчайший путь от точки , этот алгоритм не подходит, хоть и работает быстро. Однако, решения нахождения кратчайшего пути в лучшем случае работают за <tex> S O(n^2) </tex> до времени и памяти (здесь и далее <tex> T n </tex> {{---}} количество всех вершин). == Нахождение кратчайшего пути между точками с препятствиями===== Visibility graph ===Рассмотрим точное решение нахождения кратчайшего пути на плоскости между двумя точками с полигональными препятствиями с помощью построения графа видимости. После его построения, можно построить как и в случае с трапецоидной картой, кратчайший путь ищется любым стандартным алгоритмом поиска (например, алгоритмом [[Алгоритм Дейкстры|Дейкстры]] или [[Трапецоидная карта Алгоритм A*| трапецоидную картуA*]]). Для простоты рассуждений начальную и конечную вершины будем считать вершинами полигонов. {{Лемма|about=О кратчайшем пути|statement=Любой кратчайший путь между двумя вершинами с полигональными препятствиями представляет собой ломаную, соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе вершины которой {{---}} вершины полигонов.|proof=[[Алгоритм Дейкстры Файл:short.png|150px|thumb|right| ДейкстройShort cut]] найти Пусть кратчайший путь от {{---}} не ломаная. В таком случае, на пути существует такая точка <tex> S p </tex> до , которая не принадлежит ни одному прямому отрезку. Это означает, что существует <tex> T \epsilon</tex>-окрестность точки <tex> p </tex>, в которую не попадает ни одно препятствие (случай, когда точка попала на ребро рассматривается аналогично). В таком случае, подпуть, который находится внутри <tex>\epsilon</tex>-окрестности, по неравенству треугольника может быть сокращён по хорде, соединяющий точки пересечения границы <tex>\epsilon</tex>-окрестности с путем. Но этот Раз часть пути может быть уменьшена, значит и весь путь может быть уменьшен, а значит исходное предположение некорректно.}}{{Определение|definition =Говорят, что вершина <tex> u </tex> ''видна'' (англ. mutually visible) из <tex> v </tex>, если отрезок <tex> uv </tex> не будет кратчайшимпересекает ни одного препятствия.}}{{Определение|definition =''Граф видимости'' (кэпангл. visibility graph){{---}} граф, вершины которого {{---}} вершины полигонов. Между вершинами <tex> u </tex> и <tex> v </tex> существует ребро, если из <tex> u </tex> видна <tex> v </tex>.}} В худшем случае в таком графе может быть <tex> O(n^2) </tex> ребер. Однако по некоторым ребрам кратчайший путь точно не пройдет, и такие ребра из графа можно удалить.

Любой кратчайший путь от [[Файл:edgeToDelete.png|150px|thumb|right|Удаляем <tex> S BD </tex> до ]]# Если существуют вершины <tex> A, B, C </tex> одного препятствия и вершина <tex> D </tex> такая, что поворот <tex> T DBA </tex> не совпадает с полигональными препятствиями представляет собой ломануюповоротом <tex> DBC </tex>, то ребро <tex> DB </tex> не принадлежит кратчайшему пути и его можно удалить из графа. (См. поясняющую картинку справа)# Все внутренние вершины которой {{---}} вершины полигонов, кроме вырожденного случая, (начальная/конечная точка лежит внутри выпуклой оболочки фигуры) можно игнорировать.

Пусть путь проходит(в смысле вершины) [[Файл:edgeNotToDelete.png|200px|thumb|right|Не удаляем <tex> BS </tex>]]# Путь проходящий через ребро <tex> BD </tex> будет длиннее, чем через какую-то другую точку. Рассмотрим окрестность этой соседей точки. По <tex> B </tex>, так как по неравенству треугольника мы сможем немножко<tex> AB + BD > AD </tex># Если случай не вырожденный, да срезать. Значит этот значит заход внутрь фигуры только увеличит суммарный путь не кратчайший. Противоречие, значит лемма доказано и все офигеннотак как по неравенству треугольника расстояние между соседними выпуклыми вершинами всегда меньше суммы расстояний с учётом внутренней.

Здесь могла быть Ваша рекламаЕсли полигон вращать нельзя, задачу сводится к движению точки так: выбирается точка на полигоне, которая принимается за начало координат. Но скоро будет конспектВ такой системе координат для каждого препятствия считается [[Сумма Минковского (определение, вычисление)|сумма Минковского]] с полигоном. Получаются бОльшие препятствия, но теперь достаточно двигать выбранную точку, что было описано выше.

== Источники ==* Mark de BergЕсли полигон можно вращать, Otfried Cheongзадача нахождения ''кратчайшего'' пути становится достаточно ресурсоёмка, Marc van Kreveld, Mark Overmars (2008), Computational Geometry: Algorithms and Applications (3rd edition), Springer-Verlag, ISBN 978-3-540-77973-5 Chapter 15 page 324поэтому обычно рассматривают задачу нахождения какого-331нибудь пути между конечными точками.