222
правки
Изменения
м
Будем рассматривать точки слева направо, таким образом потребуется заметать только правую половину плоскости, так как ребра, которые должны идти в левую будут уже добавлены ранее.
vertices.add(s, t) //добавляем начальную и конечную вершину
→Lee’s Algorithm. O(n ^ 2 \log n)
[[Файл:Zam.png|300px|thumb|left|Заметание плоскости вращающимся лучом]]
Однако можно это сделать за <tex> O(n ^ 2 \log n) </tex>. Идея алгоритма проста : для каждой вершины найдем видимые из нее вершины независимо. Если научиться делать это за <tex> O(n \log n) </tex>, задача решена, так как всего точек <tex> n </tex>.
Будем рассматривать точки слева направо, таким образом потребуется рассматривать только правую половину плоскости, так как ребра, которые должны идти в левую будут уже добавлены ранее.
Переформулируем задачу : дана точка <tex> v </tex> и множество отрезков {{---}} ребер препятствий.
Для решения этой задачи будем использовать заметающий луч с началом в точке <tex> v </tex>. Его статусом будут отрезки, которые его пересекают, упорядоченные по возрастанию расстояния от точки <tex> v </tex> до точки пересечения. Точками событий будут концы отрезков.
Изначально, пустим луч из рассматриваемой вершины вертикально вверх и добавим в статус все отрезки, которые он пересекает, по увеличению расстояния до них. Теперь будем рассматривать точки <tex> w \in V </tex> в порядке сортировки по углу между <tex> v </tex> и вертикальной полуосью <tex> l </tex>. При таком обходе проверка видимости вершины будет выполняться за <tex> O(1) </tex>, так как достаточно проверить пересечение с отрезком, первым в статусе. Действительно, если вершина не видна, то отрезок <tex> vw </tex> пересекает несколько отрезков, лежащих перед <tex> w </tex>, а значит и ближайший, то есть первый в статусе. В противном случае все пересекаемые лучом отрезки лежат за вершиной <tex> w </tex> и пересечения отрезка <tex> uw </tex> с ближайшим отрезком в статусе не будет. Вне зависимости от видимости вершины, необходимо изменить статус заметающего луча. Для этого необходимо удалить из статуса все отрезки, которые заканчиваются вершине <tex> w </tex> (лежат слева от прямой <tex> vw </tex>) и добавить все отрезки, которые в ней начинаются (лежат справа от прямой <tex> vw </tex>).
graph buildVisibilityGraph(Set<Segment> segments)
Set<Vertex> vertices = getVertices(segments) //получаем все вершины препятствий
graph visibilityGraph(vertices) //изначально в графе только вершины
for Vertex v in vertices //для каждой вершины
status.add(s)
// Инициализируем множество вершин, которые нужно рассматривать
for point p w in segments if pw.x >= v.x currentVertices.add(pw)
sort(currentVertices) by angle
// Для каждой вершины проверяем, видима ли она и обновляем статус
