222
правки
Изменения
м
<pre> graph buildVisibilityGraph(Set<Segment> segments) Set<Vertex> vertices = getVertices(segments) //получаем все вершины препятствий graph visibilityGraph(vertices) //изначально в графе только вершины '''for ''' Vertex v '''in ''' vertices //для каждой вершины '''for ''' Vertex w '''in ''' getVisibleVertices(v, segments) //добавляем в граф все видимые из нее вершины visibilityGraph.addEdge(v, w) '''return ''' visibilityGraph</pre>
<pre> 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 add in status all segments beginning in w '''return ''' answer</pre>
→Псевдокод
===== Псевдокод =====
Здесь функция getVisibleVertices(<tex> v </tex>) возвращает все видимые из <tex> v </tex> вершины и выглядит так:
В качестве статуса нужно использовать структуру данных, позволяющую добавлять и удалять из нее отрезки за <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>).
|
