Изменения

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

Рассмотрим задачу нахождения кратчайшего пути от точки <tex> S </tex> до <tex> T </tex> с препятствиями. Для начала рассмотрим движение материальной точки. Случай, когда размером и формой движимого объекта пренебречь нельзя, случай произвольного полигона будет рассмотрен [[Visibility graph и motion planning#Motion planning|позднее]].

Для нахождения пути Эту задачу можно построить решить с помощью [[Трапецоидная карта | трапецоидную картутрапецоидной карты]]. По ней строится граф, ребра которого соединяют центры трапедоидов, соединить ребрами середины а также начальную и конечную вершины с серединами вертикальных сторон трапецоидов с их центрами и в этом . В таком графе любым алгоритмом поиска кратчайших путей (например, алгоритмом [[Алгоритм Дейкстры|Дейкстры]] или [[Алгоритм A*|A*]]) найти ищется путь от <tex> S </tex> до <tex> T </tex>. Однако, этот путь не будет абсолютно кратчайшиммежду начальной и конечной вершинами.

Этот алгоритм поиска пути через трапецоидную карту обширно используется, так как дает хорошее приближение, работает за <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 ===Рассмотрим точное решение нахождения кратчайшего пути на плоскости между двумя точками с полигональными препятствиями с помощью построения графа видимости. После его построения, как и в случае с трапецоидной картой, кратчайший путь ищется любым стандартным алгоритмом поиска (например, алгоритмом [[Алгоритм Дейкстры|Дейкстры]] или [[Алгоритм A*|A*]]). Для этого нам потребуется лемма:простоты рассуждений начальную и конечную вершины будем считать вершинами полигонов.

Любой кратчайший путь от <tex> S </tex> до <tex> T </tex> между двумя вершинами с полигональными препятствиями представляет собой ломаную, вершины которой {{---}} вершины полигонов.

Говорят, что вершина <tex> u </tex> ''видна''visibility graph(англ. mutually visible) из <tex> v </tex>, если отрезок <tex> uv </tex> не пересекает ни одного препятствия.}}{{Определение|definition =''Граф видимости'' (англ. visibility graph) {{---}} граф, вершины которого {{---}} вершины полигонов, а также <tex> S </tex> и <tex> T </tex>. Между вершинами <tex> u </tex> и <tex> v </tex> существует ребро, если из <tex> u </tex> <i> видна </i>(mutually visible) <tex> v </tex>.

# Если существуют вершины <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> S </tex> начальной до <tex> T </tex>конечной вершины.

Если делать наивно, т. е. для Для каждой пары вершин проверять проверяем, можно ли добавить ли такое ребро(между ними, то есть нет ли пересечений с полигонами. <tex> O(n^2) </tex> пар вершин и <tex> O(n)</tex> ребер, будет то есть <tex> O(n^3) </tex>.

[[Файл:Zamrefr1.png|250px|thumb|right|Обновление статуса заметающего луча]][[Файл:Zamrefr2.png|250px|thumb|right|Обновление статуса заметающего луча]][[Файл:Zamrefr3.png|250px|thumb|right|Обновление статуса заметающего луча]]Однако можно это сделать за <tex> O(n ^ 2 \log n) </tex>. Для Идея алгоритма проста: для каждой вершины найдём все найдем видимые из неё нее вершины при помощи метода плоского заметания. Нам нужно решить следующую задачу: на плоскости дано множество отрезков (рёбер препятствий) и точка Если научиться делать это за <tex> v O(n \log n) </tex>. Найти все концы отрезков, видимые из точки задача решена, так как всего точек <tex> v n </tex>. Будем заметать плоскость вращающимся лучом с началом  Для каждой вершины будем рассматривать только правую половину плоскости, так как ребра, которые должны идти в точке <tex> v </tex>. Статусом заметающего луча левую половину, будут отрезкиисходить из вершин, которые его пересекают, упорядоченные по возрастанию расстояния от точки <tex> v </tex> до точки пересечениядля которых текущая вершина будет справа. Точками событий будут концы отрезков Переформулируем задачу. Итак, первым делом вершины Дано: точка <tex> w \in V </tex> сортируются по углу между лучом <tex> vw v </tex> и вертикальной полуосью, проходящей через <tex> v </tex> множество отрезков {{---}} луч <tex> l </tex> (достаточно рассматривать только точки, которые лежат правее <tex> v </tex>, так как все точки левее мы уже рассмотрели)ребер препятствий. Затем происходит инициализация множества видимых вершин (по умолчанию такое Найти: множество пустое). Далее начинается заметание плоскости. В порядке сортировки вершин для каждой из них выполняется проверка: видна ли вершина <tex> w </tex> из вершины <tex> v </tex>. Для этого нам достаточно проверить только пересечение заметающего луча с ближайшим отрезком в статусе, т. е. эта проверка выполняется за <tex> O(1) </tex>. Если вершина видимаконцов отрезков, необходимо добавить её в список видимых вершин. И, наконец, вне зависимости от видимости вершины, необходимо изменить статус заметающего луча. Для этого для текущей вершины <tex> w </tex> необходимо удалить из списка текущих пересечений все рёбра (отрезки), которые заканчиваются в этой вершине (лежат слева от прямой <tex> vw v </tex>) и добавить все рёбра (отрезки), которые в ней начинаются (лежат справа от прямой <tex> vw </tex>).

===== Псевдокод =====Для решения этой задачи будем использовать заметающий луч с началом в точке <pre>vector<Vertextex> getVisibleVertexes(vertex v) vector<Vertex> ans vertexes.add(all w in Vertexes : w.x >= v.x) status.add(all e in Edges : intersection(e, l) != null) sort status by distance sort vertexes by angle for w in vertexes if intersection(vw, status.closest) == null ans.push(w) delete from status all edges ending in w add in status all edges beginning in w</pre>Вершин у нас <tex> O(n) </tex>, сортируем за <tex> O(n \log n) </tex> плюс обновление статуса. Его статусом будут отрезки, которое суммарно выполняется за <tex> O(n \log n) </tex>которые его пересекают, так как у нас упорядоченные по возрастанию расстояния от точки <tex> O(n) </tex> ребер. Итого <tex> O(n^2 \log n) v </tex>до точки пересечения. Что и требовалось доказатьТочками событий будут концы отрезков.

==== Overmars and Welzl’s Algorithm Пустим луч из рассматриваемой вершины <tex> Ov </tex> вертикально вверх и добавим в статус все отрезки, которые он пересекает, по увеличению расстояния до них. Теперь будем рассматривать точки <tex> w \in V </tex> в порядке сортировки по углу между <tex> v </tex> и вертикальной полуосью <tex> l </tex>. При таком обходе для проверки видимости вершины достаточно проверить пересечение с ближайшим к <tex> v </tex> отрезком, то есть первым в статусе(n ^ 2так как отрезки отсортированы по расстоянию до них) . Действительно, если вершина <tex> w </tex> ====[http:не видна, то отрезок <tex> vw </tex> пересекает несколько отрезков, лежащих перед <tex> w </igitur-archivetex>, а значит и ближайший.libraryВ противном случае все пересекаемые лучом отрезки лежат за вершиной <tex> w </tex> и пересечения отрезка <tex> vw </tex> с ближайшим отрезком не будет.uuВне зависимости от видимости вершины, необходимо изменить статус заметающего луча.nlДля этого необходимо удалить из статуса все отрезки, которые заканчиваются вершине <tex> w </mathtex> (лежат слева от прямой <tex> vw </2006-1214-201604tex>) и добавить все отрезки, которые в ней начинаются (лежат справа от прямой <tex> vw </overmars_88_new_methodstex>).pdf visibility graph при помощи rotation tree]

C помощью [http===== Псевдокод ===== graph buildVisibilityGraph(Set<Segment> segments) 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Здесь функция getVisibleVertices(<tex> v </tex>) возвращает все видимые из <tex> v </tex> вершины и выглядит так: Set<Vertex> getVisibleVertices(Vertex <tex>v</tex>, Set<Segment> segments) Set<Vertex> answer '''for''' Segment <tex>s</tex> '''in''' segments '''if''' intersect(<tex> s </tex>, <tex> l </tex>) status.add(<tex>s</tex>) '''for''' Point <tex>w</tex> '''in''' segments '''if''' <tex>v.x \leqslant w.x</bittex> currentVertices.lyadd(<tex>w</tex>) sort(currentVertices) by angle '''for''' Point <tex>w</1eEqTzk rotation tree] можно достичь асимптотики tex> '''in''' currentVertices '''if''' '''not''' intersect(<tex>vw</tex>, status.closest) answer.add(<tex>w</tex>) '''for''' Segment <tex>s</tex> ending in <tex>w</tex> status.delete(<tex>s</tex>) '''for''' Segment <tex>s</tex> beginning in <tex>w</tex> status.add(<tex>s</tex>) '''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> из статуса]]|}

[[Файл:mink.png|200px|thumb|left|Раздуваем Изменяем препятствия]]

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

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

При такой реализации в некоторых случаях у нас может возникнуть ошибка в поворотеЕсли полигон можно вращать, так как в одной плоскости мы все можем делать точно: положения на соседних слоях могут допускатьсязадача нахождения ''кратчайшего'' пути становится достаточно ресурсоёмка, а повернуть мы не сможем. Это лечится в основном двумя способами: измельчением угла поворота и изначальным сглаживанием углов полигона {{--поэтому обычно рассматривают задачу нахождения какого-}} повращать полигон на <tex> +\epsilon </tex> и <tex> -\epsilon </tex> и объединить с исходным, получив новый полигоннибудь пути между конечными точками.

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

На каждом слое построим трапецоидную карту и граф, как описано в [[Visibility graph и motion planning#Нахождение пути между точками с препятствиями|начале]]. Если [[Пересечение многоугольников (PSLG overlaying)|пересечь]] соседние слои и добавить между их графами ребра, получится один большой граф, в котором ищется кратчайший путь. При таком подходе может возникнуть ошибка при пересечении слоев: на каждом слое состояния будут допустимые, а осуществить поворот физически будет невозможно. Обычно, эту проблему решают двумя способами: измельчением угла поворота и изначальным сглаживанием углов полигона. Первый способ повышает не только точность решения, но и вычислительную сложность задачи. Второй подход практически исключает возможность нахождения пути, когда его нет, но повышает вероятность "ненахождения" пути, когда он есть. == Источники информации ==* 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 graphsAcademia.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>.