Изменения

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

<pre> graph buildVisibilityGraph(Set<Segment> segments) Set<Vertex> 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</pre>

<pre> Set<Vertex> getVisibleVertices(vertex Vertex <tex>v</tex>, setSet<segmentSegment> segments) Set<Vertex> answer// Инициализируем статус '''for segment ''' Segment <tex>s </tex> '''in ''' segments '''if intersection ''' intersect(<tex> s and ray from v to up exists</tex>, <tex> l </tex>) status.add(<tex>s</tex>)// Инициализируем множество вершин, которые нужно рассматривать '''for point ''' Point <tex>w </tex> '''in ''' segments '''if ''' <tex>v.x \leqslant w.x </tex>= v.x currentVertices.add(<tex>w</tex>) sort(currentVertices) by angle// Для каждой вершины проверяем, видима ли она и обновляем статус '''for ''' Point <tex>w </tex> '''in ''' currentVertices '''if intersection ''' '''not''' intersect(<tex>vw and </tex>, status.first not existsclosest) answer.add(<tex>w</tex>) delete from status all edges '''for''' Segment <tex>s</tex> ending in <tex>w</tex> add in status all edges .delete(<tex>s</tex>) '''for''' Segment <tex>s</tex> beginning in <tex>w</tex> return answer status.add(<tex>s</pretex>) '''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> из статуса заметающего луча]]

== Источники информации ==* 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 graphs на academiaAcademia.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>. Далеко от идеального, но работает