222
правки
Изменения
→Построение visibility графа
|
[[Файл:Zam.png|300px|thumb|left|Заметание плоскости вращающимся лучом]]
Однако можно это сделать за <tex> O(n ^ 2 \log n) </tex>. Нам нужно решить следующую задачуИдея алгоритма проста : на плоскости дано множество отрезков (рёбер препятствий) и точка для каждой вершины найдем видимые из нее вершины независимо. Если научиться делать это за <tex> v O(n \log n) </tex>. Найти все концы отрезков, видимые из точки задача решена, так как всего точек <tex> v n </tex>.
Для решения этой задачи будем использовать заметающий луч с началом в точке <tex> v </tex>. Его статусом будут отрезки, которые его пересекают, упорядоченные по возрастанию расстояния от точки <tex> v </tex> до точки пересечения. Точками событий будут концы отрезков. Будем рассматривать точки слева направо, таким образом потребуется заметать только правую половину плоскости, так как ребра, которые должны идти в левую будут уже добавлены ранее. Итак, первым делом вершины <tex> w \in V </tex> сортируются по углу между лучом <tex> vw </tex> и вертикальной полуосью, проходящей через <tex> v </tex> {{---}} луч <tex> l </tex> (достаточно рассматривать только точки, которые лежат правее <tex> v </tex>, так как все точки левее мы уже рассмотрели). Затем инициализируем статус отрезками, которые пересекают луч <tex> l </tex>. Далее начинается заметание плоскости. В порядке сортировки вершин для каждой из них выполняется проверка: видна ли вершина <tex> w </tex> из вершины <tex> v </tex>. Для этого нам достаточно проверить только пересечение заметающего луча с ближайшим отрезком в статусе. Если вершина видима, необходимо добавить её в список видимых вершин. И, наконец, вне зависимости от видимости вершины, необходимо изменить статус заметающего луча. Для этого для текущей вершины <tex> w </tex> необходимо удалить из статуса все рёбра (отрезки), которые заканчиваются в этой вершине (лежат слева от прямой <tex> vw </tex>) и добавить все рёбра (отрезки), которые в ней начинаются (лежат справа от прямой <tex> vw </tex>).
===== Псевдокод =====
graph visibilityGraph(vertices) //изначально в графе только вершины
for Vertex v in vertices //для каждой вершины
for Vertex w in getVisibleVertices(v) // добавляем в граф все видимые из нее вершины
visibilityGraph.addEdge(v, w)
return visibilityGraph
currentVertices.add(all w in vertices : w.x >= v.x) //рассматриваем только вершины правее v
sort vertexes by angle //в порядке увеличения угла с
// вертикальной прямой, проходящей через v
heap<Segment> status
status.add(all e in Edges : intersection(e, l) != null) //инициализируем статус
