Изменения

== Visibility graph Нахождение любого пути между точками с препятствиями =={|align="right"|-valign="top"|[[Файл:trap.png|200px|thumb|leftright|Путь с препятствиями через трапецоидную карту]]|[[Файл:notShort.png|300px|thumb|right|Такой путь не самый короткий]]|}Для начала рассмотрим движение материальной точки. Случай, когда размером и формой движимого объекта пренебречь нельзя, будет рассмотрен [[Visibility graph и motion planning#Motion planning|позднее]].

Эту задачу можно решить с помощью [[Трапецоидная карта | трапецоидной карты]]. По ней строится граф, ребра которого соединяют центры трапедоидов, а также начальную и конечную вершины с серединами вертикальных сторон трапецоидов. В общемтаком графе ищется путь между начальной и конечной вершинами. Если точки лежат внутри одного трапецоида {{---}} ответ найден. Иначе идём из стартовой точки в центр её трапецоида, когда мы далее по построенным рёбрам ищем трапецоид содержащий финальную точку. Для этого можно использовать поиск в ширину или другой алгоритм нахождения кратчайшего пути в графе. В конечном итоге, соединяем середину последнего трапецоида с конечной вершиной. Данный алгоритм работает за <tex> O(n \log n) </tex> и за линейное количество памяти и хорошо подходит для нахождения какого-нибудь пути между парой данных вершин. Но если нужно найти кратчайший путь от точки , этот алгоритм не подходит, хоть и работает быстро. Однако, решения нахождения кратчайшего пути в лучшем случае работают за <tex> S O(n^2) </tex> до времени и памяти (здесь и далее <tex> T n </tex> {{---}} количество всех вершин). == Нахождение кратчайшего пути между точками с препятствиями ===== Visibility graph ===Рассмотрим точное решение нахождения кратчайшего пути на плоскости между двумя точками с полигональными препятствиями (надо уточнитьс помощью построения графа видимости. После его построения, что двигаем мы точкукак и в случае с трапецоидной картой, а не какой-то полигон)кратчайший путь ищется любым стандартным алгоритмом поиска (например, можно построить алгоритмом [[Алгоритм Дейкстры|Дейкстры]] или [[Трапецоидная карта Алгоритм A*| трапецоидную картуA*]]). Для простоты рассуждений начальную и конечную вершины будем считать вершинами полигонов. {{Лемма|about=О кратчайшем пути|statement=Любой кратчайший путь между двумя вершинами с полигональными препятствиями представляет собой ломаную, соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе вершины которой {{---}} вершины полигонов.|proof=[[Алгоритм Дейкстры Файл:short.png|150px|thumb|right| ДейкстройShort cut]] найти Пусть кратчайший путь от {{---}} не ломаная. В таком случае, на пути существует такая точка <tex> S p </tex> до , которая не принадлежит ни одному прямому отрезку. Это означает, что существует <tex>\epsilon</tex>-окрестность точки <tex> p </tex>, в которую не попадает ни одно препятствие (случай, когда точка попала на ребро рассматривается аналогично). В таком случае, подпуть, который находится внутри <tex>\epsilon</tex>-окрестности, по неравенству треугольника может быть сокращён по хорде, соединяющий точки пересечения границы <tex> T \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> S BD </tex> до ]]# Если существуют вершины <tex> A, B, C </tex> одного препятствия и вершина <tex> D </tex> такая, что поворот <tex> T DBA </tex> не совпадает с полигональными препятствиями представляет собой ломануюповоротом <tex> DBC </tex>, то ребро <tex> DB </tex> не принадлежит кратчайшему пути и его можно удалить из графа. (См. поясняющую картинку справа)# Все внутренние вершины которой {{---}} вершины полигонов, кроме вырожденного случая, (начальная/конечная точка лежит внутри выпуклой оболочки фигуры) можно игнорировать.

[[Файл:shortedgeNotToDelete.png|150px200px|thumb|right|Ну в общем тут все очевидноНе удаляем <tex> BS </tex>]]Пусть путь проходит(в смысле вершины) # Путь проходящий через ребро <tex> BD </tex> будет длиннее, чем через какую-то другую точку. Рассмотрим окрестность этой соседей точки. По <tex> B </tex>, так как по неравенству треугольника мы сможем немножко<tex> AB + BD > AD </tex># Если случай не вырожденный, да срезать. Значит этот значит заход внутрь фигуры только увеличит суммарный путь не кратчайший. Противоречие, значит лемма доказана и все офигеннотак как по неравенству треугольника расстояние между соседними выпуклыми вершинами всегда меньше суммы расстояний с учётом внутренней.

По этой лемме запилим visibility graph. Его вершины {{---}} вершины полигонов. Между вершинами <tex> u </tex> и <tex> v </tex> существует доказанным леммам любое ребро, если из <tex> u </tex> <i> видна </i>(mutually visible) <tex> v </tex> (ребра полигонов тоже входят кратчайшего пути содержится в этот граф)графе. ТеперьТаким образом, если мы добавим к множеству вершин <tex> S </tex> и <tex> T </tex> (и ребра для нахождения кратчайшего пути осталось найти кратчайший путь в видимые этом графе от начальной до конечной вершины), у нас получится граф, в котором опять же Дейкстрой находим кратчайший путь. По лемме любое ребро кратчайшего пути {{---}} ребро visibility графа, так что мы нашли то, что нужно.

Если делать <s> в тупую</s> наивно, т. е. для Для каждой пары вершин проверять проверяем, можно ли добавить ли такое ребро(между ними, то есть нет ли пересечений с полигонами. <tex> O(n^2) </tex> пар вершин и <tex> O(n)</tex> ребер, будет то есть <tex> O(n^3) </tex> (зато просто пилится, даже не надо объяснять как).[[Файл:search.png|400px|thumb|right|Дерево поиска пересекаемых ребер]]

{||[[Файл:Zam.png|300px|thumb|left|Заметание плоскости вращающимся лучом]]Однако можно это сделать за <tex> O(n ^ 2 \log n) </tex>. Пусть мы хотим Идея алгоритма проста: для каждой вершины найдем видимые из нее вершины . Если научиться делать это за <tex> v O(n \log n) </tex> найти все видимые из нее вершины. Теперь мы будем перебирать ребра не в случайном порядке, а задача решена, так чтобы можно было проверять за логарифмкак всего точек <tex> n </tex>.

Для этого посортим все каждой вершины по полярному углу (будем рассматривать только теправую половину плоскости, так как ребра, которые справа нашейдолжны идти в левую половину, ибо очевиднобудут исходить из вершин, что назад можно уже не смотреть) и запилим сбалансированное двоичное дерево поискадля которых текущая вершина будет справа.

Вершин у нас Переформулируем задачу. Дано: точка <tex> O(n) v </tex>и множество отрезков {{---}} ребер препятствий. Найти: множество концов отрезков, сортим за <tex> O(n \log n) видимых из </tex> плюс запросы в дереве за <tex> O(n) * O(\log n) v </tex>. Итого что хотели.

==== Overmars and Welzl’s Algorithm Для решения этой задачи будем использовать заметающий луч с началом в точке <tex> O(n ^ 2) v </tex> ====Каким-то магическим образом. Его статусом будут отрезки, которые его пересекают, можно избавиться и упорядоченные по возрастанию расстояния от логарифма в асимптотике. Это делается с помощью [http:точки <tex> v <//bit.ly/1eEqTzk rotation tree]tex> до точки пересечения. Про него рассказывал Антон Ков., но как-то мутно и не очень понятно. Суть такова, что мы обходим вершины в таком хитром порядке, что почти не просматриваем лишнее и получаем асимптотику {{---}} квадратТочками событий будут концы отрезков.

Короче тут мы делаем Пустим луч из рассматриваемой вершины <tex> v </tex> вертикально вверх и добавим в статус все отрезки, которые он пересекает, по увеличению расстояния до них. Теперь будем рассматривать точки <tex> w \in V </tex> в порядке сортировки по углу между <tex> v </tex> и вертикальной полуосью <tex> l </tex>. При таком обходе для проверки видимости вершины достаточно проверить пересечение с ближайшим к <tex> v </tex> отрезком, то есть первым в статусе(так как отрезки отсортированы по расстоянию до них). Действительно, если вершина <tex> w </tex> не видна, то же самоеотрезок <tex> vw </tex> пересекает несколько отрезков, что лежащих перед <tex> w </tex>, а значит и ближайший. В противном случае все пересекаемые лучом отрезки лежат за вершиной <tex> w </tex> и н2логн, только сортим пересечения отрезка <tex> vw </tex> с ближайшим отрезком не для каждой будет. Вне зависимости от видимости вершины отдельно, а рассматриваем необходимо изменить статус заметающего луча. Для этого необходимо удалить из статуса все отрезки, которые заканчиваются вершине <tex> w </tex> (лежат слева от прямой <tex> vw </tex>) и добавить все одновременноотрезки, которые в ней начинаются (лежат справа от прямой <tex> vw </tex>).

"The idea is simple===== Псевдокод ===== 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 each vertex''' Segment <tex>s</tex> '''in''' segments '''if''' intersect(<tex> s </tex>, a scanline is kept which runs from <tex> -\pi l </tex>) status.add(<tex>s</ 2 tex>) '''for''' Point <tex>w</tex> to '''in''' segments '''if''' <tex> v.x \pi leqslant w.x</ 2 tex> currentVertices.add(<tex>w</tex>) sort(currentVertices) by angle '''for''' Point <tex>w</tex> hopping from vertex to vertex '''in its path. During the main loop''' currentVertices '''if''' '''not''' intersect(<tex>vw</tex>, it appears that all of the scanlines are proceeding simultaneouslystatus. In fact, there are exact rules about determining the next vertex to process, and some vertices may finish their scan before othersclosest) answer. To understand the rules about finding the next vertex, the rotation tree must be understoodadd(<tex>w</tex>) '''for''' Segment <tex>s</tex> ending in <tex>w</tex> status. A rotation tree is a rooted planar tree where each vertex is a node and points to its parentdelete(<tex>s</tex>) '''for''' Segment <tex>s</tex> beginning in <tex>w</tex> status. There are two special nodes: add(<tex>s</tex>) '''return''' answerВ качестве статуса нужно использовать структуру данных, позволяющую добавлять и удалять из нее отрезки за <tex> +O(\infty log n) </tex> and и извлекать минимум за <tex> O(1) </tex> -или <tex> O(\infty log n) </tex>. InitiallyВ этом случае достигается асимптотика <tex> O(n^2 \log n) </tex>, all vertices point to так как для каждой из <tex> n </tex> точек выполняется сортировка за <tex> -O(n \infty log n) </tex> as their parent and , обновление статуса (суммарно <tex> -O(n \infty log n) </tex> points to , так как каждый отрезок добавляется и удаляется из статуса не более одного раза) и запросы ближайшего отрезка (<tex> +O(\infty log n) </tex>. Also stored is the rightmost child или <tex> O(if a node is a parent1)</tex> на точку, and its right and left siblings то есть <tex> O(if they existn \log n). The ordering of children is by slope: the one with the smallest slope is the leftmost. The loop that examines all pairs simply takes the rightmost leftmost leaf as the next segment to process and then reattaches it to the tree </tex> или <tex> O(while maintaining the property of being a rotation treen) </tex>). It can reattach to the left of its parent or to the tangent of the chain above it|[[Файл:Zamrefr1. When a vertex attaches to png|250px|thumb|right|Обновление статуса заметающего луча: добавляем ребра <tex> w_1 w_5 </tex> и <tex> +\infty w_1 w_2 </tex>, it is finishedв статус]][[Файл:Zamrefr2. The loop continues when all points have attached to png|250px|thumb|right|Добавляем ребра <tex> w_3 w_2 </tex> и <tex> +\infty 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 not_badAcademia.jpg статья про visibility graphsedu]{{---}} 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>.