1632
правки
Изменения
м
Пусть мы ищем какой-то путь от Для начала рассмотрим движение материальной точки <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*]]). Для простоты рассуждений начальную и конечную вершины будем считать вершинами полигонов.
По этому создадим {{Определение|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 из графа, так что мы нашли то, что нужноможно удалить.
Чтобы уменьшить объем графа, следует удалить из него ребра, по которым точно не пройдет путь.
Если делать наивно, т. е. для Для каждой пары вершин проверять проверяем, можно ли добавить ли такое ребро(между ними, то есть нет ли пересечений с полигонами. <tex> O(n^2) </tex> пар вершин и <tex> O(n)</tex> ребер, будет то есть <tex> O(n^3) </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> из статуса]]|}
rollbackEdits.php mass rollback
== Visibility graph Нахождение любого пути между точками с препятствиями ==
{|align="right"
|-valign="top"
|[[Файл:notShort.png|300px|thumb|right|Такой путь не самый короткий]]
|}
{{Лемма
|about=О кратчайшем пути
|statement=
Любой кратчайший путь от <tex> S </tex> до <tex> T </tex> между двумя вершинами с полигональными препятствиями представляет собой ломаную, вершины которой {{---}} вершины полигонов.
|proof=
[[Файл:short.png|150px|thumb|right|Short cut]]
Пусть кратчайший путь проходит(в смысле вершины) через какую{{---то другую точку}} не ломаная. В таком случае, на пути существует такая точка <tex> p </tex>, которая не принадлежит ни одному прямому отрезку. Рассмотрим Это означает, что существует <tex>\epsilon</tex>-окрестность этой точки<tex> p </tex>, в которую не попадает ни одно препятствие (случай, когда точка попала на ребро рассматривается аналогично). По В таком случае, подпуть, который находится внутри <tex>\epsilon</tex>-окрестности, по неравенству треугольника мы сможем немножко срезатьможет быть сокращён по хорде, соединяющий точки пересечения границы <tex>\epsilon</tex>-окрестности с путем. Значит этот Раз часть пути может быть уменьшена, значит и весь путь не кратчайший. Противоречиеможет быть уменьшен, а значит лемма доказанаисходное предположение некорректно.
}}
{{Лемма
|about=О неиспользуемых вершинах
|statement=
[[Файл: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> не принадлежит кратчайшему пути и его можно удалить из графа. (См. поясняющую картинку справа)# Все внутренние вершины, кроме вырожденного случая, идущее к текущей точке может быть удалено(начальная/конечная точка лежит внутри выпуклой оболочки фигуры) можно игнорировать.
|proof=
[[Файл:edgeToDeleteedgeNotToDelete.jpgpng|150px200px|thumb|right|Удаляем Не удаляем <tex> BD BS </tex>]]Очевидно, что путь # Путь проходящий через ребро <tex> BD </tex> будет длинеедлиннее, чем через соседей точки <tex> B </tex>. Так , так как по неравенству треугольника <tex> AB + BD < > AD </tex># Если случай не вырожденный, значит заход внутрь фигуры только увеличит суммарный путь, так как по неравенству треугольника расстояние между соседними выпуклыми вершинами всегда меньше суммы расстояний с учётом внутренней.
}}
По доказанным леммам любое ребро кратчайшего пути содержится в графе. Таким образом, для нахождения кратчайшего пути осталось найти кратчайший путь в этом графе от начальной до конечной вершины.
=== Построение visibility графа ===
==== Наивный алгоритм. <tex> O(n ^ 3) </tex> ====
==== Lee’s Algorithm. <tex> O(n ^ 2 \log n) </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>).
== Motion planning ==
[[Файл: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>.
[[Категория: Вычислительная геометрия]]
== Ссылки ==
* [https://github.com/Igorjan94/cg/blob/master/include/cg/algorithms/visibilityGraph.h Github] {{---}} Реализация алгоритма за <tex> O(n^2 \log n) </tex>