Изменения

== 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> p </tex>, которая не принадлежит ни одному прямому отрезку. Это означает, что существует <tex>\epsilon</tex>-окрестность точки <tex> p </tex>, в которую не попадает ни одно препятствие(случай, когда точка попала на ребро рассматривается аналогично). В таком случае, подпуть, который находится внутри <tex>\epsilon</tex>-окрестности, по неравенству треугольника может быть сокращён по хорде, соединяющий точки пересечения границы <tex>\epsilon</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|300px|thumb|right|Обновление статуса заметающей прямой]][[Файл:zamrefr2.png|300px|thumb|right|Обновление статуса заметающей прямой]][[Файл:zamrefr3.png|300px|thumb|right|Обновление статуса заметающей прямой]]Однако можно это сделать за <tex> O(n ^ 2 \log n) </tex>. Для Идея алгоритма проста: для каждой вершины найдём все найдем видимые из неё нее вершины при помощи метода плоского заметания. Нам нужно решить следующую задачу: на плоскости дано множество отрезков (рёбер препятствий) и точка Если научиться делать это за <tex> v </tex>. Найти все концы отрезков, видимые из точки <tex> v </tex>. Будем заметать плоскость вращающимся лучом с началом в точке <tex> v O(n \log n) </tex>. Статусом заметающего луча будут отрезки, которые его пересекаютзадача решена, упорядоченные по возрастанию расстояния от точки так как всего точек <tex> v n </tex> до точки пересечения. Точками событий будут концы отрезков. Итак, первым делом  Для каждой вершины <tex> w \in V </tex> сортируются по углу между лучом <tex> vw </tex> и вертикальной полуосью, проходящей через <tex> v </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>void getVisibleVertexes(vertex v) vertexes.add(for w in V if w.x tex>= v.x) status.add(for e in E if e isHigher than v and intersects vertical line from v to infinity) sort status by distance sort vertexes by angle for w in vertexes add visiblePair (v, w) if intersection(vw, status.closest) == null 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>.