222
правки
Изменения
м
'''ВНИМАНИЕ!!!''' Данная статья написана исключительно по-пацански и обладает повышенной чёткостью.
[http://habrahabr.ru/post/199256/ Здесь написано примерно всё по теме и достаточно понятно]
В общем, когда Пусть мы ищем какой-то путь от точки <tex> S </tex> до <tex> T </tex> с препятствиями (надо уточнить, что двигаем мы сначала будем двигать точку, а не какой-то полигон), . Для нахождения можно построить [[Трапецоидная карта | трапецоидную карту]], соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе [[Алгоритм Дейкстры | Дейкстрой]] найти путь от <tex> S </tex> до <tex> T </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 графа, так что мы нашли то, что бы нужно. Чтобы уменьшить объем финального графа, следует удалить из него ребра, по которым точно не пройдет путь.
По этому сосздадим 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 графа, так что мы нашли то, что нужно.
Нет описания правки
== Visibility graph ==
[[Файл:trap.png|200px|thumb|leftright|Путь с препятствиями через трапецоидную карту]]
[[Файл:notShort.png|300px|thumb|right|Такой путь не самый короткий]]
{{Лемма
Любой кратчайший путь от <tex> S </tex> до <tex> T </tex> с полигональными препятствиями представляет собой ломаную, вершины которой {{---}} вершины полигонов.
|proof=
[[Файл:short.png|150px|thumb|right|Ну в общем тут все очевидноВ таком случае мы всегда сможем срезать]]Пусть путь проходит(в смысле вершины) через какую-то другую точку. Рассмотрим окрестность этой точки. По неравенству треугольника мы сможем немножко, да срезать. Значит этот путь не кратчайший. Противоречие, значит лемма доказана и все офигенно.
}}
{{Лемма
|statement=
Если у ребра на предыдущю точку от данной левый поворот, а на следующую, от данной, правый - то ребро, идущее к текущей точке может быть удалено.
|proof=
[[Файл:edgeToDelete.jpg|150px|thumb|right|Удаляем <tex>BD</tex>]]Очевидно, что путь проходящий через ребро <tex>BD</tex> будет длинее, чем через соседей точки <tex>B</tex>. Тк Так как по неравенству треугольника <tex>AB + BD</tex> < <tex>AD</tex>
}}
=== Построение visibility графа ===
== Источники ==
* Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (2008), Computational Geometry: Algorithms and Applications (3rd edition), Springer-Verlag, ISBN 978-3-540-77973-5 Chapter 15 page 324-331
* [http://www.academia.edu/2845047/3D_Visibility_Graph not_bad.jpg статья про visibility graphs]* [http://habrahabr.ru/post/199256/ Хабр]
[[Категория: Вычислительная геометрия]]
