222
правки
Изменения
м
void vector<Vertex> getVisibleVertexes(vertex v) vector<Vertex> ans vertexes.add(for all w in V if Vertexes : w.x >= v.x) status.add(for all e in E if Edges : intersection(e isHigher than v and intersects vertical line from v to infinity, l) != null)
add visiblePair (v, w) if intersection(vw, status.closest) == null ans.push(w)
Нет описания правки
|proof=
[[Файл:short.png|150px|thumb|right|Short cut]]
Пусть кратчайший путь {{---}} не ломаная. В таком случае, на пути существует такая точка <tex> p </tex>, которая не принадлежит ни одному прямому отрезку. Это означает, что существует <tex>\epsilon</tex>-окрестность точки <tex> p </tex>, в которую не попадает ни одно препятствие(случай, когда точка попала на ребро рассматривается аналогично). В таком случае, подпуть, который находится внутри <tex>\epsilon</tex>-окрестности, по неравенству треугольника может быть сокращён по хорде, соединяющий точки пересечения границы <tex>\epsilon</tex>-окрестности с путем. Раз часть пути может быть уменьшена, значит и весь путь может быть уменьшен, а значит исходное предположение некорректно.
}}
{{Определение
==== Lee’s Algorithm. <tex> O(n ^ 2 \log n) </tex> ====
[[Файл:Zam.png|300px|thumb|left|Заметание плоскости вращающимся лучом]]
[[Файл:zamrefr1Zamrefr1.png|300px|thumb|right|Обновление статуса заметающей прямойзаметающего луча]][[Файл:zamrefr2Zamrefr2.png|300px|thumb|right|Обновление статуса заметающей прямойзаметающего луча]][[Файл:zamrefr3Zamrefr3.png|300px|thumb|right|Обновление статуса заметающей прямойзаметающего луча]]
Однако можно это сделать за <tex> O(n ^ 2 \log n) </tex>. Для каждой вершины найдём все видимые из неё вершины при помощи метода плоского заметания. Нам нужно решить следующую задачу: на плоскости дано множество отрезков (рёбер препятствий) и точка <tex> v </tex>. Найти все концы отрезков, видимые из точки <tex> v </tex>. Будем заметать плоскость вращающимся лучом с началом в точке <tex> v </tex>. Статусом заметающего луча будут отрезки, которые его пересекают, упорядоченные по возрастанию расстояния от точки <tex> v </tex> до точки пересечения. Точками событий будут концы отрезков. Итак, первым делом вершины <tex> w \in V </tex> сортируются по углу между лучом <tex> vw </tex> и вертикальной полуосью, проходящей через <tex> v </tex>(достаточно рассматривать только точки, которые лежат правее <tex> v </tex>, так как все точки левее мы уже рассмотрели). Затем происходит инициализация множества видимых вершин (по умолчанию такое множество пустое). Далее начинается заметание плоскости. В порядке сортировки вершин для каждой из них выполняется проверка: видна ли вершина <tex> w </tex> из вершины <tex> v </tex>. Для этого нам достаточно проверить только пересечение заметающего луча с ближайшим отрезком в статусе, т. е. эта проверка выполняется за <tex> O(1) </tex>. Если вершина видима, необходимо добавить её в список видимых вершин. И, наконец, вне зависимости от видимости вершины, необходимо изменить статус заметающего луча. Для этого для текущей вершины <tex> w </tex> необходимо удалить из списка текущих пересечений все рёбра (отрезки), которые заканчиваются в этой вершине (лежат слева от прямой <tex> vw </tex>) и добавить все рёбра (отрезки), которые в ней начинаются (лежат справа от прямой <tex> vw </tex>).
===== Псевдокод =====
<pre>
sort status by distance
sort vertexes by angle
for w in vertexes
delete from status all edges ending in w
add in status all edges beginning in w
