Изменения

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

Эту задачу можно решить с помощью [http://habrahabr[Трапецоидная карта | трапецоидной карты]].ru/post/199256/ Здесь написано примерно всё по теме По ней строится граф, ребра которого соединяют центры трапедоидов, а также начальную и достаточно понятно]конечную вершины с серединами вертикальных сторон трапецоидов. В таком графе ищется путь между начальной и конечной вершинами.

== Visibility graph ==[[Файл:trapЕсли точки лежат внутри одного трапецоида {{---}} ответ найден.png|200px|thumb|left|Путь Иначе идём из стартовой точки в центр её трапецоида, далее по построенным рёбрам ищем трапецоид содержащий финальную точку. Для этого можно использовать поиск в ширину или другой алгоритм нахождения кратчайшего пути в графе. В конечном итоге, соединяем середину последнего трапецоида с препятствиями через трапецоидную карту]][[Файл:notShortконечной вершиной.png|300px|thumb|right|Такой путь не самый короткий]]

В общемДанный алгоритм работает за <tex> O(n \log n) </tex> и за линейное количество памяти и хорошо подходит для нахождения какого-нибудь пути между парой данных вершин. Но если нужно найти кратчайший путь, этот алгоритм не подходит, хоть и работает быстро. Однако, когда мы ищем путь от точки решения нахождения кратчайшего пути в лучшем случае работают за <tex> S O(n^2) </tex> до времени и памяти (здесь и далее <tex> T n </tex> {{---}} количество всех вершин). == Нахождение кратчайшего пути между точками с препятствиями ===== Visibility graph ===Рассмотрим точное решение нахождения кратчайшего пути на плоскости между двумя точками с полигональными препятствиями (надо уточнитьс помощью построения графа видимости. После его построения, что двигаем мы точкукак и в случае с трапецоидной картой, а не какой-то полигон)кратчайший путь ищется любым стандартным алгоритмом поиска (например, можно построить алгоритмом [[Трапецоидная карта Алгоритм Дейкстры| трапецоидную картуДейкстры]], соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе или [[Алгоритм Дейкстры A*| ДейкстройA*]] найти путь от <tex> S </tex> до <tex> T </tex>). Но этот путь не будет кратчайшим(кэп) Для простоты рассуждений начальную и конечную вершины будем считать вершинами полигонов.

Любой кратчайший путь от <tex> S </tex> до <tex> T </tex> между двумя вершинами с полигональными препятствиями представляет собой ломаную, вершины которой {{---}} вершины полигонов.

[[Файл:short.png|150px|thumb|right|Ну в общем тут все очевидноShort cut]]Пусть кратчайший путь проходит(в смысле вершины) через какую{{---то другую точку}} не ломаная. В таком случае, на пути существует такая точка <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> не принадлежит кратчайшему пути и его можно удалить из графа. (См. поясняющую картинку справа)# Все внутренние вершины, кроме вырожденного случая, идущее к текущей точке может быть удалено(начальная/конечная точка лежит внутри выпуклой оболочки фигуры) можно игнорировать.

[[Файл:edgeToDeleteedgeNotToDelete.jpgpng|150px200px|thumb|right|Удаляем Не удаляем <tex>BDBS </tex>]]Очевидно, что путь # Путь проходящий через ребро <tex>BD</tex> будет длинеедлиннее, чем через соседей точки <tex>B</tex>. Тк , так как по неравенству треугольника <tex>AB + BD</tex> < <tex>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 графа, так что мы нашли то, что нужно.

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

{||[[Файл:zamZam.png|400px300px|thumb|left|Заметание плоскости вращающимся лучом]][[Файл:zamrefr1.png|400px|thumb|right|Обновление статуса заметающей прямой]][[Файл:zamrefr2.png|400px|thumb|right|Обновление статуса заметающей прямой]][[Файл:zamrefr3.png|400px|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(\log n) </tex>. Если вершина видимаНайти: множество концов отрезков, необходимо добавить её в список видимых вершин. И, наконец, вне зависимости от видимости вершины, необходимо изменить статус заметающей прямой. Для этого, для текущей вершины <tex> w </tex> необходимо удалить из списка текущих пересечений все рёбра (отрезки), которые заканчиваются в этой вершине (лежат слева от прямой <tex> vw v </tex>) и добавить все рёбра (отрезки), которые в ней начинаются (лежат справа от прямой <tex> vw </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> 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]

Ковалев сказал что это можно рассказывать по желанию===== Псевдокод ===== 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> в статус]][[Файл: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> из статуса]]|}

Каким-то магическим образом, можно избавиться и от логарифма в асимптотике== Motion planning ==[[Файл:mink. Это делается с помощью png|200px|thumb|left|Изменяем препятствия]][http[Файл://bitmink2.ly/1eEqTzk rotation treepng|400px|thumb|right|Ищем путь для точки]. Про него рассказывал Антон Ков., но как-то мутно и не очень понятно. Суть такова, что мы обходим вершины в таком хитром порядке]Рассмотрим задачу нахождения кратчайшего пути, что почти не просматриваем лишнее и получаем асимптотику когда движимый объект {{---}} квадратэто выпуклый полигон. Например, робот, которого надо доставить из начальной в конечную точку.

Короче тут мы делаем то же самоеЕсли полигон вращать нельзя, что и н2логнзадачу сводится к движению точки так: выбирается точка на полигоне, только сортим не которая принимается за начало координат. В такой системе координат для каждой вершины отдельнокаждого препятствия считается [[Сумма Минковского (определение, вычисление)|сумма Минковского]] с полигоном. Получаются бОльшие препятствия, но теперь достаточно двигать выбранную точку, а рассматриваем все одновременночто было описано выше.

"The idea is simple: for each vertexЕсли полигон можно вращать, a scanline is kept which runs from <tex> -\pi / 2 </tex> to <tex> \pi / 2 </tex> hopping from vertex to vertex in its path. During the main loopзадача нахождения ''кратчайшего'' пути становится достаточно ресурсоёмка, it appears that all of the scanlines are proceeding simultaneously. In fact, there are exact rules about determining the next vertex to process, and some vertices may finish their scan before others. To understand the rules about finding the next vertex, the rotation tree must be understood. A rotation tree is a rooted planar tree where each vertex is a node and points to its parent. There are two special nodes: <tex> +\infty </tex> and <tex> поэтому обычно рассматривают задачу нахождения какого-\infty </tex>. Initially, all vertices point to <tex> -\infty </tex> as their parent and <tex> -\infty </tex> points to <tex> +\infty </tex>. Also stored is the rightmost child (if a node is a parent), and its right and left siblings (if they exist). 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 (while maintaining the property of being a rotation tree). It can reattach to the left of its parent or to the tangent of the chain above it. When a vertex attaches to <tex> +\infty </tex>, it is finished. The loop continues when all points have attached to <tex> +\infty </tex>"нибудь пути между конечными точками.

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

== Motion planning ==На каждом слое построим трапецоидную карту и граф, как описано в [[Файл:mink.pngVisibility graph и motion planning#Нахождение пути между точками с препятствиями|200px|thumb|left|Раздуваем препятствияначале]][[Файл:mink2.png|400px|thumb|right|Логично же]]В общем тут все очевидно. Тут мы просто двигаем не точку, а произвольный выпуклый полигон. Если мы его не можем вращать, просто "обводим" препятствия нашим полигоном (запиливаем [[Сумма Минковского Пересечение многоугольников (определение, вычисление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>.