Изменения

[[Файл:zam.png|200px400px|thumb|left|Заметание плоскости вращающимся лучом]][[Файл:zamrefr1.png|400px|thumb|right|Обновление статуса заметающей прямой]][[Файл:zamrefr2.png|400px|thumb|right|Обновление статуса заметающей прямой]][[Файл:zamrefr3.png|400px|thumb|right|Обновление статуса заметающей прямой]]Однако можно это сделать за <tex> O(n ^ 2 \log n) </tex>. Для каждой вершины найдём все видимые из неё вершины при помощи метода плоского заметания. Нам нужно решить следующую задачу: на плоскости дано множество отрезков (рёбер препятствий) и точка <tex> p</tex>. Найти все концы отрезков, видимые из точки <tex> p</tex>. Будем заметать плоскость вращающимся лучом с началом в точке <tex> p</tex>. Статусом заметающей прямой будет отрезки, которые её пересекают, упорядоченные по возрастанию расстояния от точки <tex> p </tex> до точки пересечения. Точками событий будут концы отрезков. Итак, первым делом вершины <tex> w ∈ \in W </tex> сортируются по углу между лучом <tex> vw </tex> и вертикальной полуосью, проходящей через <tex> v</tex>. Затем происходит инициализация множества видимых вершин (по умолчанию, такое множество пустое). Далее начинается заметание плоскости. В порядке сортировки вершин для каждой из них выполняется проверка: видна ли вершина <tex> w </tex> из вершины <tex> v</tex>. Поскольку такая проверка означает наличие пересечений, которые хранятся в сбалансированном дереве, она может быть выполнена за <tex> O(\log(n))</tex>. Если вершина видима, необходимо добавить её в список видимых вершин. И, наконец, вне зависимости от видимости вершины, необходимо изменить статус заметающей прямой. Для этого, для текущей вершины <tex> w </tex> необходимо удалить из списка текущих пересечений все рёбра (отрезки), которые заканчиваются в этой вершине (лежат слева от прямой <tex> vw</tex>) и добавить все рёбра (отрезки), которые в ней начинаются (лежат справа от прямой <tex> vw</tex>).