222
правки
Изменения
м
→Lee’s Algorithm. O(n ^ 2 \log n)
<pre>
graph buildVisibilityGraph(Set<Segment> segments)
Set<Vertex> vertices = getVertices(segments) //получаем все вершины препятствий vertices.add(s, t) //добавляем начальную и конечную вершину graph visibilityGraph(vertices) //изначально в графе только вершины for Vertex v in vertices //для каждой вершины for Vertex w in getVisibleVertices(v) // добавляем в граф все видимые из нее вершины
visibilityGraph.addEdge(v, w)
return visibilityGraph
vector<Vertex> getVisibleVertices(vertex v)
vector<Vertex> answer, currentVertices
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) //инициализируем статус
for w in currentVertices
if intersection(vw, status.closest) == null //если отрезок vw не пересекает ближайший // отрезок в статусе answer.add(w) // добавляем в ответ delete from status all edges ending in w //обновляем статус
add in status all edges beginning in w
return answer
