222
правки
Изменения
м
//все вершины препятствий, а также начальная и конечная вершины vertices = getVertices(segments) <tex> \cup\ \{Ss, T\ t\} </tex> //изначально в графе только вершины
//добавляем в граф все видимые из нее вершины
// Инициализируем статус
// Инициализируем множество вершин, которые нужно рассматривать
// Для каждой вершины проверяем, видима ли она и обновляем статус
→Псевдокод
===== Псевдокод =====
graph buildVisibilityGraph(Set<Segment> segments)
graph = visibilityGraph(vertices)
'''for''' Vertex <tex>v</tex> '''in''' vertices
'''for''' Vertex <tex>w</tex> '''in''' getVisibleVertices(<tex>v</tex>, segments)
visibilityGraph.addEdge(<tex>v</tex>, <tex>w</tex>)
Set<Vertex> getVisibleVertices(Vertex <tex>v</tex>, Set<Segment> segments)
Set<Vertex> answer
'''for''' Segment <tex>s</tex> '''in''' segments
'''if''' intersection intersect(<tex>s</tex> and ray from , <tex>vl </tex> to up exists)
status.add(<tex>s</tex>)
'''for''' Point <tex>w</tex> '''in''' segments
'''if''' <tex>v</tex>.x <tex>\le</tex> <tex>w</tex>.x
currentVertices.add(<tex>w</tex>)
sort(currentVertices) by angle
'''for''' Point <tex>w</tex> '''in''' currentVertices
'''if''' intersection '''not''' intersect(<tex>vw</tex> and , status.closest not exists)
answer.add(<tex>w</tex>)
'''for''' Segment <tex>s</tex> ending in <tex>w</tex>
