Изменения

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

Пусть мы ищем какой-то путь от Для начала рассмотрим движение материальной точки <tex> S </tex> до <tex> T </tex> с препятствиями (сначала будем двигать точку. Случай, когда размером и формой движимого объекта пренебречь нельзя, а не полигон)будет рассмотрен [[Visibility graph и motion planning#Motion planning|позднее]]. Для нахождения  Эту задачу можно построить решить с помощью [[Трапецоидная карта | трапецоидную картутрапецоидной карты]]. По ней строится граф, соединить ребрами середины ребра которого соединяют центры трапедоидов, а также начальную и конечную вершины с серединами вертикальных сторон с центрами трапецоидов . В таком графе ищется путь между начальной и конечной вершинами. Если точки лежат внутри одного трапецоида {{---}} ответ найден. Иначе идём из стартовой точки в центр её трапецоида, далее по построенным рёбрам ищем трапецоид содержащий финальную точку. Для этого можно использовать поиск в ширину или другой алгоритм нахождения кратчайшего пути в этом графе [[Алгоритм Дейкстры | Дейкстрой]] найти путь от <tex> S </tex> до <tex> T </tex>. Но этот путьВ конечном итоге, очевидно, не будет кратчайшимсоединяем середину последнего трапецоида с конечной вершиной. Однако этот  Данный алгоритм обширно используется из-за быстроты(трапецоидная карта строится работает за <tex> O(n \log n) </tex> и занимает <tex> O(n) </tex> за линейное количество памятии хорошо подходит для нахождения какого-нибудь пути между парой данных вершин. Но если нужно найти кратчайший путь, этот алгоритм не подходит, хоть и работает быстро. Однако, решения нахождения кратчайшего пути в то время как visibility graph строится лучшем случае работают за <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> <i> видна </i>(mutually visible) <tex> v </tex> (ребра полигонов тоже входят .}} В худшем случае в этот граф). Теперь, если мы добавим к множеству вершин таком графе может быть <tex> S O(n^2) </tex> ребер. Однако по некоторым ребрам кратчайший путь точно не пройдет, и <tex> T </tex> (и такие ребра в видимые вершины), у нас получится граф, в котором опять же Дейкстрой находим кратчайший путь. По лемме любое ребро кратчайшего пути {{---}} ребро visibility из графа, так что мы нашли то, что нужноможно удалить.

[[Файл: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> не принадлежит кратчайшему пути и его можно удалить из графа. (См. поясняющую картинку справа)# Все внутренние вершины, кроме вырожденного случая, идущее к текущей точке может быть удалено(начальная/конечная точка лежит внутри выпуклой оболочки фигуры) можно игнорировать.

[[Файл:edgeToDeleteedgeNotToDelete.jpgpng|150px200px|thumb|right|Удаляем Не удаляем <tex> BD 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 </tex>. Найти все концы отрезков, видимые из точки <tex> p </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(n \log n) </tex>. Если вершина видима, необходимо добавить её в список видимых вершин. И, наконец, вне зависимости от видимости вершины, необходимо изменить статус заметающей прямой. Для этогозадача решена, для текущей вершины так как всего точек <tex> w n </tex> необходимо удалить из списка текущих пересечений все рёбра (отрезки), которые заканчиваются в этой вершине (лежат слева от прямой <tex> vw </tex>) и добавить все рёбра (отрезки), которые в ней начинаются (лежат справа от прямой <tex> vw </tex>).

Вершин у нас <tex> O(n) </tex>Для каждой вершины будем рассматривать только правую половину плоскости, сортим за <tex> O(n \log n) </tex> плюс запросы так как ребра, которые должны идти в дереве за <tex> O(n) * O(\log n) </tex>. Итого что хотелилевую половину, будут исходить из вершин, для которых текущая вершина будет справа.

==== Overmars and Welzl’s Algorithm Переформулируем задачу. Дано: точка <tex> O(n ^ 2) v </tex> ====[http://igiturи множество отрезков {{-archive.library.uu.nl/math/2006-1214-201604}} ребер препятствий. Найти: множество концов отрезков, видимых из <tex> v </overmars_88_new_methodstex>.pdf visibility graph при помощи rotation tree]

C помощью [http:Для решения этой задачи будем использовать заметающий луч с началом в точке <tex> v <//bittex>.ly/1eEqTzk rotation tree] можно достичь асимптотики Его статусом будут отрезки, которые его пересекают, упорядоченные по возрастанию расстояния от точки <tex> O(n^2) v </tex>до точки пересечения. Точками событий будут концы отрезков.

Идея таковаПустим луч из рассматриваемой вершины <tex> v </tex> вертикально вверх и добавим в статус все отрезки, что которые он пересекает, по увеличению расстояния до них. Теперь будем рассматривать точки <tex> w \in V </tex> в порядке сортировки по углу между <tex> v </tex> и вертикальной полуосью <tex> l </tex>. При таком обходе для каждой проверки видимости вершины заметающий луч пробегается от достаточно проверить пересечение с ближайшим к <tex> -\pi v </ 2 tex> отрезком, то есть первым в статусе(так как отрезки отсортированы по расстоянию до них). Действительно, если вершина <tex> w </tex> до не видна, то отрезок <tex> \pi vw </ 2 tex> пересекает несколько отрезков, лежащих перед <tex> w </tex>, а значит и ближайший. В основном цикле получаетсяпротивном случае все пересекаемые лучом отрезки лежат за вершиной <tex> w </tex> и пересечения отрезка <tex> vw </tex> с ближайшим отрезком не будет. Вне зависимости от видимости вершины, что мы вращаем необходимо изменить статус заметающего луча. Для этого необходимо удалить из статуса все отрезки, которые заканчиваются вершине <tex> w </tex> (лежат слева от прямой <tex> vw </tex>) и добавить все лучи одновременноотрезки, которые в ней начинаются (лежат справа от прямой <tex> vw </tex>). ===== Псевдокод ===== 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</tex> currentVertices.add(<tex>w</tex>) sort(currentVertices) by angle '''for''' Point <tex>w</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> в rotation tree, что можно сделать по желаниюстатус]][[Файл: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|Раздуваем Изменяем препятствия]][[Файл:mink2.png|400px|thumb|right|Логично жеИщем путь для точки]]Тут мы двигаем не точкуРассмотрим задачу нахождения кратчайшего пути, а произвольный когда движимый объект {{---}} это выпуклый полигон. Например, робот, которого надо доставить из начальной в конечную точку. Если мы его не можем полигон вращатьнельзя, задачу сводится к движению точки так: выбирается точка на полигоне, просто "обводим" которая принимается за начало координат. В такой системе координат для каждого препятствия нашим считается [[Сумма Минковского (определение, вычисление)|сумма Минковского]] с полигоном (делаем . Получаются бОльшие препятствия, но теперь достаточно двигать выбранную точку, что было описано выше. Если полигон можно вращать, задача нахождения ''кратчайшего'' пути становится достаточно ресурсоёмка, поэтому обычно рассматривают задачу нахождения какого-нибудь пути между конечными точками. Первый шаг решения этой задачи совпадает с предыдущим случаем: выберем точку и построим [[Сумма Минковского (определение, вычисление)|сумму Минковского]] препятствий с полигоном. Рассмотрим малый угол <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>.