Изменения

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

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

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

Данный Если точки лежат внутри одного трапецоида {{---}} ответ найден. Иначе идём из стартовой точки в центр её трапецоида, далее по построенным рёбрам ищем трапецоид содержащий финальную точку. Для этого можно использовать поиск в ширину или другой алгоритм работает за <tex> O(n \log 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> будем считать вершинами полигонов.

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

Однако можно это сделать за <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> v </tex> и множество отрезков {{---}} ребер препятствий. Найти: множество концов отрезков, первым делом видимых из <tex> v </tex>. Для решения этой задачи будем использовать заметающий луч с началом в точке <tex> v </tex>. Его статусом будут отрезки, которые его пересекают, упорядоченные по возрастанию расстояния от точки <tex> v </tex> до точки пересечения. Точками событий будут концы отрезков.  Пустим луч из рассматриваемой вершины <tex> v </tex> вертикально вверх и добавим в статус все отрезки, которые он пересекает, по увеличению расстояния до них. Теперь будем рассматривать точки <tex> w \in V </tex> сортируются в порядке сортировки по углу между лучом <tex> vw v </tex> и вертикальной полуосью, проходящей через <tex> v l </tex> {{---}} луч . При таком обходе для проверки видимости вершины достаточно проверить пересечение с ближайшим к <tex> l v </tex> отрезком, то есть первым в статусе(достаточно рассматривать только точкитак как отрезки отсортированы по расстоянию до них). Действительно, которые лежат правее если вершина <tex> v w </tex>не видна, так как все точки левее мы уже рассмотрели). Затем инициализируем статус отрезкамито отрезок <tex> vw </tex> пересекает несколько отрезков, которые пересекают луч лежащих перед <tex> l w </tex>. Далее начинается заметание плоскости, а значит и ближайший. В порядке сортировки вершин для каждой из них выполняется проверка: видна ли вершина противном случае все пересекаемые лучом отрезки лежат за вершиной <tex> w </tex> из вершины и пересечения отрезка <tex> v vw </tex>. Для этого нам достаточно проверить только пересечение заметающего луча с ближайшим отрезком в статусене будет. Если вершина видима, необходимо добавить её в список видимых вершин. И, наконец, вне Вне зависимости от видимости вершины, необходимо изменить статус заметающего луча. Для этого для текущей вершины <tex> w </tex> необходимо удалить из статуса все рёбра (отрезки), которые заканчиваются в этой вершине <tex> w </tex> (лежат слева от прямой <tex> vw </tex>) и добавить все рёбра (отрезки), которые в ней начинаются (лежат справа от прямой <tex> vw </tex>).

<pre> graph buildVisibilityGraph(Set<Segment> segments) Set<Vertex> vertices = getVertices(segments) //получаем все вершины препятствий vertices.add(<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>, Set<Segment> segments) vector Set<Vertex> answer '''for''' Segment <tex>s</tex> '''in''' segments '''if''' intersect(<tex> s </tex>, currentVertices<tex> l </tex>) currentVertices status.add(all <tex>s</tex>) '''for''' Point <tex>w </tex> '''in vertices : w''' segments '''if''' <tex>v.x >= v\leqslant w.x) <//рассматриваем только вершины правее v sort vertexes by angle //в порядке увеличения угла с // вертикальной прямой, проходящей через v heap<Segmenttex> status status currentVertices.add(all e in Edges : intersection<tex>w</tex>) sort(e, lcurrentVertices) != null) //инициализируем статусby angle '''for ''' Point <tex>w </tex> '''in ''' currentVertices '''if intersection''' '''not''' intersect(<tex>vw</tex>, status.closest) == null //если отрезок vw не пересекает ближайший // отрезок в статусе answer.add(<tex>w</tex>) '''for''' Segment <tex>s<// добавляем в ответ delete from status all edges tex> ending in <tex>w </tex> status.delete(<tex>s</tex>) '''for''' Segment <tex>s</обновляем статус add in status all edges tex> beginning in <tex>w</tex> status.add(<tex>s</tex>) '''return ''' answerВ качестве статуса нужно использовать структуру данных, позволяющую добавлять и удалять из нее отрезки за <tex> O(\log n) </pretex>Вершин у нас и извлекать минимум за <tex> n O(1) </tex>, для каждой вершины мы выполяеем следующие шаги: сортировка (или <tex> O(n \log n) </tex>), проверка пересечения (. В этом случае достигается асимптотика <tex> O(1n^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) * O(n \log n) = </tex> или <tex> O(n^2 \log 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> из статуса заметающего луча]]

==== Overmars and Welzl’s Algorithm <tex> O(n ^ 2) </tex> ==Motion planning ==[http[Файл://igitur-archivemink.librarypng|200px|thumb|left|Изменяем препятствия]][[Файл:mink2.uu.nl/math/2006png|400px|thumb|right|Ищем путь для точки]]Рассмотрим задачу нахождения кратчайшего пути, когда движимый объект {{--1214-201604/overmars_88_new_methods}} это выпуклый полигон. Например, робот, которого надо доставить из начальной в конечную точку.pdf visibility graph при помощи rotation tree]

C помощью [httpЕсли полигон вращать нельзя, задачу сводится к движению точки так://bitвыбирается точка на полигоне, которая принимается за начало координат.ly/1eEqTzk rotation tree] можно достичь асимптотики <tex> OВ такой системе координат для каждого препятствия считается [[Сумма Минковского (n^2определение, вычисление) </tex>|сумма Минковского]] с полигоном. Получаются бОльшие препятствия, но теперь достаточно двигать выбранную точку, что было описано выше.

== Motion planning ==[[Файл:mink.png|200px|thumb|left|Раздуваем препятствия]][[Файл:mink2.png|400px|thumb|right|Ищем путь для точки]]Тут мы двигаем не точку, а произвольный выпуклый Если полигон. Если мы его не можем можно вращать, просто считаем configuration space, т. е. "обводим" препятствия нашим полигоном (делаем [[Сумма Минковского (определениезадача нахождения ''кратчайшего'' пути становится достаточно ресурсоёмка, вычисление)|сумму Минковского]] препятствий и полигона, сдвинутого в начало координат какойпоэтому обычно рассматривают задачу нахождения какого-нибудь точкой) и получаем другие препятствия, но зато теперь мы двигаем точку. А это мы уже научились делать вышепути между конечными точками.

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

При такой реализации в некоторых случаях у нас может возникнуть ошибка в поворотеНа каждом слое построим трапецоидную карту и граф, так как описано в одной плоскости мы все можем делать точно: положения на соседних слоях могут допускаться, а повернуть мы не сможем[[Visibility graph и motion planning#Нахождение пути между точками с препятствиями|начале]]. Это лечится в основном двумя способами: измельчением угла поворота Если [[Пересечение многоугольников (PSLG overlaying)|пересечь]] соседние слои и изначальным сглаживанием углов полигона {{---}} повращать полигон на <tex> +\epsilon </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 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>.