222
правки
Изменения
м
→tex
vertices = getVertices(segments) <tex> \cup\ \{S, T\} </tex> //все вершины препятствий, а также начальная и конечная вершины
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>)
'''return''' visibilityGraph
Здесь функция getVisibleVertices(<tex> v </tex>) возвращает все видимые из <tex> v </tex> вершины и выглядит так:
Set<Vertex> getVisibleVertices(Vertex <tex>v</tex>, Set<Segment> segments)
Set<Vertex> answer
// Инициализируем статус
'''for''' Segment <tex>s </tex> '''in''' segments '''if''' intersection <tex>s </tex> and ray from <tex>v </tex> to up exists status.add(<tex>s</tex>)
// Инициализируем множество вершин, которые нужно рассматривать
'''for''' Point <tex>w </tex> '''in''' segments '''if''' <tex>w</tex>.x >= <tex>v</tex>.x currentVertices.add(<tex>w</tex>)
sort(currentVertices) by angle
// Для каждой вершины проверяем, видима ли она и обновляем статус
'''for''' Point <tex>w </tex> '''in''' currentVertices '''if''' intersection <tex>vw </tex> and status.closest not exists answer.add(<tex>w</tex>) delete from status all segments ending in <tex>w</tex> add in status all segments beginning in <tex>w</tex>
'''return''' answer
В качестве статуса нужно использовать структуру данных, позволяющую добавлять и удалять из нее отрезки за <tex> O(\log n) </tex> и извлекать минимум за <tex> O(1) </tex> или <tex> O(\log n) </tex>. В этом случае достигается асимптотика <tex> O(n^2 \log n) </tex>, так как для каждой из <tex> n </tex> точек выполняется сортировка за <tex> O(n \log n) </tex>, обновление статуса (суммарно <tex> O(n \log n) </tex>, так как каждый отрезок добавляется и удаляется из статуса не более одного раза) и запросы ближайшего отрезка (<tex> O(\log n) </tex> или <tex> O(1) </tex> на точку, то есть <tex> O(n \log n) </tex> или <tex> O(n) </tex>).
