Изменения

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

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

Данный алгоритм работает за <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>. Представим, что поворот полигона на этот угол {{---}} это движение вверх-вниз между слоями, на каждом из которых посчитана сумма Минковского с полигоном, повернутым на этот угол.

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

== Источники информации ==* 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>. Далеко от идеального, но работает