Изменения

== 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) </tex> за линейное количество памятии хорошо подходит для нахождения какого-нибудь пути между парой данных вершин. Но если нужно найти кратчайший путь, этот алгоритм не подходит, хоть и работает быстро. Однако, в то время как точные решения нахождения кратчайшего пути в лучшем случае работают за <tex> O(n^2) </tex> времени и памяти (здесь и требуют далее <tex> O(n^2) </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>-окрестности этого участка мы сможем немного срезатьс путем. Значит этот Раз часть пути может быть уменьшена, значит и весь путь может быть уменьшен, а значит исходное предположение некорректно.}}{{Определение|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> BD </tex>]]# Если существуют вершины <tex> A, B, C </tex> одного препятствия и вершина <tex> D </tex> такая, что поворот <tex> 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># Если случай не вырожденный, значит заход внутрь фигуры только увеличит суммарный путь, так как по неравенству треугольника расстояние между соседними выпуклыми вершинами всегда меньше суммы расстояний с учётом внутренней.

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

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

Вершин у нас <tex> O(n) </tex>, сортируем за <tex> O(n \log n) </tex> плюс запросы Для решения этой задачи будем использовать заметающий луч с началом в дереве за точке <tex> O(n) * O(1) v </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>.