Изменения

== Нахождение любого пути между точками с препятствиями ==

Обычно эта задача решается Эту задачу можно решить с помощью [[Трапецоидная карта | трапецоидной карты]]. По ней строится граф, ребра которого соединяют центры трапедоидов, а также начальную и конечную вершины с серединами вертикальных сторон трапецоидов. В таком графе ищется путь между начальной и конечной вершинами.

Данный алгоритм работает за <tex> O(n \log n) </tex> и за линейное количество памяти и идеально подходит для нахождения какогоЕсли точки лежат внутри одного трапецоида {{---нибудь пути между конечными вершинами}} ответ найден. Но иногда нужно найти кратчайший путьИначе идём из стартовой точки в центр её трапецоида, и этот далее по построенным рёбрам ищем трапецоид содержащий финальную точку. Для этого можно использовать поиск в ширину или другой алгоритм не подходит, хоть и дает хорошее приближение. Однако, решения нахождения кратчайшего пути в лучшем случае работают за <tex> O(n^2) </tex> времени и памяти (здесь и далее <tex> n </tex> {{---}} количество всех вершин)графе. В конечном итоге, соединяем середину последнего трапецоида с конечной вершиной.

Данный алгоритм работает за <tex> O(n \log n) </tex> и за линейное количество памяти и хорошо подходит для нахождения какого-нибудь пути между парой данных вершин. Но если нужно найти кратчайший путь, этот алгоритм не подходит, хоть и работает быстро. Однако, решения нахождения кратчайшего пути в лучшем случае работают за <tex> O(n^2) </tex> времени и памяти (здесь и далее <tex> n </tex> {{---}} количество всех вершин). == Нахождение кратчайшего пути между точками с препятствиями ===== Visibility graph ===

# Если существуют вершины <tex> A, B, C </tex> одного препятствия и вершина <tex> D </tex> такая, что поворот <tex> DBA </tex> не совпадает с поворотом <tex> DBC </tex>, то ребро <tex> DB </tex> не принадлежит кратчайшему пути и его можно удалить из графа. (См. поясняющую картинку справа)# Все внутренние вершины, кроме вырожденного случая, (начальная/конечная точка лежит внутри выпуклой оболочки фигуры) можно игнорировать.

# Путь проходящий через ребро <tex> BD </tex> будет длиннее, чем через соседей точки <tex> B </tex>, так как по неравенству треугольника <tex> AB + BD < > AD </tex># Если случай не вырожденный, значит заход внутрь фигуры только увеличит суммарный путь, так как по неравенству треугольника расстояние между соседними выпуклыми вершинами всегда меньше суммы расстояний с учётом внутренней.

Однако можно это сделать за <tex> O(n ^ 2 \log n) </tex>. Идея алгоритма проста : для каждой вершины найдем видимые из нее вершины. Если научиться делать это за <tex> O(n \log n) </tex>, задача решена, так как всего точек <tex> n </tex>.

Переформулируем задачу. Дано : точка <tex> v </tex> и множество отрезков {{---}} ребер препятствий. Найти : множество концов отрезков, видимых из <tex> v </tex>.

Пустим луч из рассматриваемой вершины <tex> v </tex> вертикально вверх и добавим в статус все отрезки, которые он пересекает, по увеличению расстояния до них. Теперь будем рассматривать точки <tex> w \in V </tex> в порядке сортировки по углу между <tex> v </tex> и вертикальной полуосью <tex> l </tex>. При таком обходе проверка для проверки видимости вершины будет выполняться за достаточно проверить пересечение с ближайшим к <tex> O(1) v </tex>, так как достаточно проверить пересечение с отрезком, то есть первым в статусе(так как отрезки отсортированы по расстоянию до них). Действительно, если вершина <tex> w </tex> не видна, то отрезок <tex> vw </tex> пересекает несколько отрезков, лежащих перед <tex> w </tex>, а значит и ближайший, то есть первый в статусе. В противном случае все пересекаемые лучом отрезки лежат за вершиной <tex> w </tex> и пересечения отрезка <tex> uw vw </tex> с ближайшим отрезком в статусе не будет. Вне зависимости от видимости вершины, необходимо изменить статус заметающего луча. Для этого необходимо удалить из статуса все отрезки, которые заканчиваются вершине <tex> w </tex> (лежат слева от прямой <tex> vw </tex>) и добавить все отрезки, которые в ней начинаются (лежат справа от прямой <tex> vw </tex>).

<pre> graph buildVisibilityGraph(Set<Segment> segments) Set<Vertex> vertices = getVertices(segments) <tex> \cup\ \{s,\ t\} <//получаем все вершины препятствийtex> graph = visibilityGraph(vertices) //изначально в графе только вершины '''for ''' Vertex <tex>v </tex> '''in ''' vertices //для каждой вершины '''for ''' Vertex <tex>w </tex> '''in ''' getVisibleVertices(<tex>v</tex>, segments) //добавляем в граф все видимые из нее вершины visibilityGraph.addEdge(<tex>v</tex>, <tex>w</tex>) '''return ''' visibilityGraph</pre>Здесь функция getVisibleVertices(<tex> v </tex>) возвращет возвращает все видимые из <tex> v </tex> вершины и выглядит так:<pre>vector Set<Vertex> getVisibleVertices(vertex Vertex <tex>v</tex>, setSet<segmentSegment> segments)// Инициализируем статус Set<Vertex> answer '''for segment ''' Segment <tex>s </tex> '''in ''' segments '''if intersection ''' intersect(<tex> s and ray from v to up exists</tex>, <tex> l </tex>) status.add(<tex>s</tex>)// Инициализируем множество вершин, которые нужно рассматривать '''for point ''' Point <tex>w </tex> '''in ''' segments '''if ''' <tex>v.x \leqslant w.x </tex>= v.x currentVertices.add(<tex>w</tex>) sort(currentVertices) by angle// Для каждой вершины проверяем, видима ли она и обновляем статус '''for ''' Point <tex>w </tex> '''in ''' currentVertices '''if intersection ''' '''not''' intersect(<tex>vw and </tex>, status.first not existsclosest) answer.add(<tex>w</tex>) delete from status all edges '''for''' Segment <tex>s</tex> ending in <tex>w</tex> add in status all edges .delete(<tex>s</tex>) '''for''' Segment <tex>s</tex> beginning in <tex>w</tex> return answer status.add(<tex>s</pretex>) '''return''' answerВ качестве статуса нужно использовать структуру данных, позволяющую добавлять и удалять из нее отрезки за <tex> O(\log n) </tex> и извлекать минимум за <tex> O(1) </tex> или <tex> O(\log n) </tex>. В этом случае достигается асимптотика <tex> O(n^2 \log n) </tex>, так как для каждой из <tex> n </tex> точек выполняется сортировка(за <tex> O(n \log n) </tex>), обновление статуса (суммарно <tex> O(n \log n) </tex>, так как каждый отрезок добавляется и удаляется из статуса только один разне более одного раза) и запросы ближайшего отрезка (<tex> O(\log n) </tex> или <tex> O(1) </tex> на точку, то есть <tex> O(n \log n) </tex> или <tex> O(n) </tex>).

[[Файл:Zamrefr1.png|250px|thumb|right|Обновление статуса заметающего луча: добавляем ребра <tex> w_1 w_5 </tex> и <tex> w_1 w_2 </tex> в статус]][[Файл:Zamrefr2.png|250px|thumb|right|Обновление статуса заметающего лучаДобавляем ребра <tex> w_3 w_2 </tex> и <tex> w_3 w_4 </tex> в статус]][[Файл:Zamrefr3.png|250px|thumb|right|Обновление Удаляем ребра <tex> w_3 w_2 </tex> и <tex> w_1 w_2 </tex> из статуса заметающего луча]]

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

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

Теперь рассмотрим случай, когда мы можем вращать полигон. Для начала Первый шаг решения этой задачи совпадает с предыдущим случаем: выберем точку и построим [[Трапецоидная картаСумма Минковского (определение, вычисление)|трапецоидную картусумму Минковского]], как будто мы не можем вращать полигонпрепятствий с полигоном. Теперь будем вращать полигон на Рассмотрим малый угол, пока он не сделает полный оборот вокруг своей оси, и для каждого угла сделаем трапецоидную карту<tex> \epsilon </tex>. Теперь разместим(мысленно) все карты друг над другом. Таким образом получитсяПредставим, что поворот полигона на малый этот угол {{---}} это движение вверх/-вниз между слоями. Осталось [[Пересечение многоугольников (PSLG overlaying)|попересекать]] соседние слои и добавить между ними ребра (помним что первый и последний слои одинаковы) и уже в этом графе найти путь, на каждом из которых посчитана сумма Минковского с полигоном, повернутым на этот угол.

При такой реализации в некоторых случаях у нас может возникнуть ошибка в поворотеНа каждом слое построим трапецоидную карту и граф, так как описано в одной плоскости мы все можем делать точно: положения на соседних слоях могут допускаться, а повернуть мы не сможем[[Visibility graph и motion planning#Нахождение пути между точками с препятствиями|начале]]. Это лечится в основном двумя способами: измельчением угла поворота Если [[Пересечение многоугольников (PSLG overlaying)|пересечь]] соседние слои и изначальным сглаживанием углов полигона {{---}} повращать полигон на <tex> +\epsilon </tex> и <tex> -\epsilon </tex> и объединить с исходнымдобавить между их графами ребра, получится один большой граф, получив новый полигонв котором ищется кратчайший путь.

Так как эта задача достаточно ресурсоемкаПри таком подходе может возникнуть ошибка при пересечении слоев: на каждом слое состояния будут допустимые, мы рассматриваем а осуществить поворот физически будет невозможно. Обычно, эту проблему решают двумя способами: измельчением угла поворота и изначальным сглаживанием углов полигона. Первый способ повышает не только наличие точность решения, но и вычислительную сложность задачи. Второй подход практически исключает возможность нахождения пути, а не нахождение кратчайшегокогда его нет, но повышает вероятность "ненахождения" пути, когда он есть.

== Источники информации ==* Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (2008), Computational Geometry: Algorithms and Applications (3rd {{---}} Third edition){{---}} Springer, Springer2008. {{---}} Chapter 15. {{---Verlag, }} ISBN 978-3-540-77973-5 Chapter 15 page 324-331* [http://www.academia.edu/2845047/3D_Visibility_Graph статья] про visibility graphs на academiaAcademia.edu] {{---}} 3D Visibility Graph* [http://habrahabr.ru/post/199256/ ХабрХабрахабр]{{---}} Motion planning: граф видимости, дорожные карты* [http://igitur-archive.library.uu.nl/math/2006-1214-201604/overmars_88_new_methods.pdf igitur-archive.library.uu.nl] {{---}} Visibility graph при помощи rotation tree за <tex>O(n^2)</tex>.

* Моя [https://github.com/Igorjan94/cg/blob/master/include/cg/algorithms/visibilityGraph.h реализацияGithub] {{---}} Реализация алгоритма за <tex> O(n^2 \log n) </tex>. Далеко от идеального, но работает