222
правки
Изменения
м
→Lee’s Algorithm. O(n ^ 2 \log n)
Для решения этой задачи будем использовать заметающий луч с началом в точке <tex> v </tex>. Его статусом будут отрезки, которые его пересекают, упорядоченные по возрастанию расстояния от точки <tex> v </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>).
===== Псевдокод =====
Здесь функция getVisibleVertices(<tex> v </tex>) возвращает все видимые из <tex> v </tex> вершины и выглядит так:
<pre>
Set<Vertex> getVisibleVertices(vertex Vertex v, setSet<segmentSegment> segments)
Set<Vertex> answer
// Инициализируем статус
for segment Segment s in segments
if intersection s and ray from v to up exists
status.add(s)
// Инициализируем множество вершин, которые нужно рассматривать
for point Point w in segments
if w.x >= v.x
currentVertices.add(w)
sort(currentVertices) by angle
// Для каждой вершины проверяем, видима ли она и обновляем статус
for Point w in currentVertices if intersection vw and status.first closest not exists
answer.add(w)
delete from status all edges segments ending in w add in status all edges segments beginning in w
return answer
</pre>
