Изменения

graph buildVisibilityGraph(Set<Segment> segments) vertices = getVertices(segments) <tex> \cup\ \{S, T\} </tex> //все вершины препятствий, а также начальная и конечная вершины graph = visibilityGraph(vertices) //изначально в графе только вершины '''for''' Vertex v '''in''' vertices //для каждой вершины '''for''' Vertex w '''in''' getVisibleVertices(v, segments) //добавляем в граф все видимые из нее вершины visibilityGraph.addEdge(v, w) '''return''' visibilityGraph

Set<Vertex> getVisibleVertices(Vertex v, Set<Segment> segments) Set<Vertex> answer // Инициализируем статус '''for''' Segment s '''in''' segments '''if''' intersection s and ray from v to up exists status.add(s) // Инициализируем множество вершин, которые нужно рассматривать '''for''' 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.closest not exists answer.add(w) delete from status all segments ending in w