Алгоритм Фортуны

Алгоритм Фортуны представляет собой алгоритм прогонки линий для создания диаграммы Вороного из набора точек на плоскости с использованием времени O ( n log n ) и пространства O ( n ). ^{[ 1 ]}^{[ 2 ]} Первоначально он был опубликован Стивеном Фортьюном в 1986 году в его статье «Алгоритм развертки для диаграмм Вороного». ^{[ 3 ]}

Описание алгоритма

Алгоритм поддерживает как линию развертки , так и линию пляжа , которые движутся через плоскость по мере выполнения алгоритма. Линия развертки — это прямая линия, которую мы условно можем считать вертикальной и движущейся слева направо по плоскости. В любой момент работы алгоритма входные точки слева от линии развертки будут включены в диаграмму Вороного, тогда как точки справа от линии развертки еще не будут учитываться. Линия пляжа представляет собой не прямую линию, а сложную кусочную кривую слева от линии развертки, составленную из кусков парабол ; он отделяет часть плоскости, в пределах которой может быть известна диаграмма Вороного, независимо от того, какие другие точки могут находиться справа от линии развертки, от остальной части плоскости. Для каждой точки слева от линии развертки можно определить параболу из точек, равноудаленных от этой точки и от линии развертки; линия пляжа является границей объединения этих парабол. По мере продвижения линии развертки вершины береговой линии, в которых пересекаются две параболы, очерчивают края диаграммы Вороного. Линия пляжа продвигается вперед, сохраняя каждое основание параболы точно на полпути между точками, первоначально пройденными линией развертки, и новым положением линии развертки. Математически это означает, что каждая парабола формируется с использованием линии развертки в качестве директриса и точка входа в качестве фокуса.

Алгоритм поддерживает в качестве структур данных двоичное дерево поиска, описывающее комбинаторную структуру пляжной линии, и очередь приоритетов, в которой перечислены потенциальные будущие события, которые могут изменить структуру пляжной линии. Эти события включают добавление еще одной параболы к линии пляжа (когда линия развертки пересекает другую входную точку) и удаление кривой из линии пляжа (когда линия развертки становится касательной к окружности через какие-то три входные точки, параболы которых образуют последовательные сегменты пляжной линии). Каждому такому событию может быть присвоен приоритет по координате x линии развертки в точке возникновения события. Сам алгоритм тогда состоит из многократного удаления следующего события из приоритетной очереди, поиска изменений, которые событие вызывает в пляжной линии, и обновления структур данных.

Поскольку необходимо обработать O( n ) событий (каждое из которых связано с некоторой особенностью диаграммы Вороного) и время O(log n ) для обработки события (каждое из которых состоит из постоянного числа операций двоичного дерева поиска и приоритетных операций очереди), общее время равно O( n log n ).

Псевдокод

Псевдокодовое описание алгоритма. ^{[ 4 ]}

let  $\scriptstyle *(z)$  be the transformation  $\scriptstyle *(z)=(z_{x},z_{y}+d(z))$ ,
  where  $\scriptstyle d(z)$  is the Euclidean distance between  $z$  and the nearest site
let  $T$  be the "beach line"
let  $\scriptstyle R_{p}$  be the region covered by site  $p$ .
let  $\scriptstyle C_{pq}$  be the boundary ray between sites  $p$  and  $q$ .
let  $\scriptstyle S$  be a set of sites on which this algorithm is to be applied.
let  $\scriptstyle p_{1},p_{2},...,p_{m}$  be the sites extracted from  $S$  with minimal  $y$ -coordinate, ordered by  $x$ -coordinate
let DeleteMin( $X$ ) be the act of removing the lowest and leftmost site of  $X$  (sort by y unless they're identical, in which case sort by x) 
let  $V$  be the Voronoi map of  $S$  which is to be constructed by this algorithm
 $Q\gets {p_{1},p_{2},\dots ,p_{m},S}$ 
create initial vertical boundary rays  $\scriptstyle C_{p_{1},p_{2}}^{0},C_{p_{2},p_{3}}^{0},\dots ,C_{p_{m-1},p_{m}}^{0}$ 
 $T\gets *(R_{p_{1}}),C_{p_{1},p_{2}}^{0},*(R_{p_{2}}),C_{p_{2},p_{3}}^{0},\dots ,*(R_{p_{m-1}}),C_{p_{m-1},p_{m}}^{0},*(R_{p_{m}})$ 

while not IsEmpty( $Q$ ) do
     $p$  ← DeleteMin( $Q$ )
    case  $p$  of
     $p$  is a site in  $\scriptstyle *(V)$ :
        find the occurrence of a region  $\scriptstyle *(R_{q})$  in  $T$  containing  $p$ ,
          bracketed by  $\scriptstyle C_{rq}$  on the left and  $\scriptstyle C_{qs}$  on the right
        create new boundary rays  $\scriptstyle C_{pq}^{-}$  and  $\scriptstyle C_{pq}^{+}$  with bases  $p$ 
        replace  $\scriptstyle *(R_{q})$  with  $\scriptstyle *(R_{q}),C_{pq}^{-},*(R_{p}),C_{pq}^{+},*(R_{q})$  in  $T$ 
        delete from  $Q$  any intersection between  $\scriptstyle C_{rq}$  and  $\scriptstyle C_{qs}$ 
        insert into  $Q$  any intersection between  $\scriptstyle C_{rq}$  and  $\scriptstyle C_{pq}^{-}$ 
        insert into  $Q$  any intersection between  $\scriptstyle C_{pq}^{+}$  and  $\scriptstyle C_{qs}$ 
     $p$  is a Voronoi vertex in  $\scriptstyle *(V)$ :
        let  $p$  be the intersection of  $\scriptstyle C_{qr}$  on the left and  $\scriptstyle C_{rs}$  on the right
        let  $\scriptstyle C_{uq}$  be the left neighbor of  $\scriptstyle C_{qr}$  and
        let  $\scriptstyle C_{sv}$  be the right neighbor of  $\scriptstyle C_{rs}$  in  $T$ 
        if  $\scriptstyle q_{y}=s_{y}$ ,
            create a new boundary ray  $\scriptstyle C_{qs}^{0}$  
        else if  $p$  is right of the higher of  $q$  and  $s$ ,
            create  $\scriptstyle C_{qs}^{+}$  
        else
            create  $\scriptstyle C_{qs}^{-}$ 
        endif
        replace  $\scriptstyle C_{qr},*(R_{r}),C_{rs}$  with newly created  $\scriptstyle C_{qs}$  in  $T$ 
        delete from  $Q$  any intersection between  $\scriptstyle C_{uq}$  and  $\scriptstyle C_{qr}$ 
        delete from  $Q$  any intersection between  $\scriptstyle C_{rs}$  and  $\scriptstyle C_{sv}$ 
        insert into  $Q$  any intersection between  $\scriptstyle C_{uq}$  and  $\scriptstyle C_{qs}$ 
        insert into  $Q$  any intersection between  $\scriptstyle C_{qs}$  and  $\scriptstyle C_{sv}$ 
        record  $p$  as the summit of  $\scriptstyle C_{qr}$  and  $\scriptstyle C_{rs}$  and the base of  $\scriptstyle C_{qs}$ 
        output the boundary segments  $\scriptstyle C_{qr}$  and  $\scriptstyle C_{rs}$ 
    endcase
endwhile

output the remaining boundary rays in  $T$

Взвешенные сайты и диски

Аддитивно взвешенные сайты

Как описывает Fortune в ссылке, ^{[ 1 ]} модифицированную версию алгоритма линии развертки можно использовать для построения аддитивно взвешенной диаграммы Вороного, в которой расстояние до каждого узла компенсируется весом узла; эквивалентно это можно рассматривать как диаграмму Вороного набора дисков с центрами в узлах с радиусом, равным весу узла. обнаружено, что алгоритм имеет $O(n\log(n))$ временная сложность, где n — количество сайтов согласно ссылке. ^{[ 1 ]}

Взвешенные сайты могут использоваться для управления областями ячеек Вороного при использовании диаграмм Вороного для построения древовидных карт . В аддитивно взвешенной диаграмме Вороного биссектриса между узлами обычно представляет собой гиперболу, в отличие от невзвешенных диаграмм Вороного и степенных диаграмм дисков, для которых она представляет собой прямую линию.

Ссылки

^ Перейти обратно: ^а ^б ^с де Берг, Марк ; ван Кревелд, Марк ; Овермарс, Марк ; Шварцкопф, Отфрид (2000), Вычислительная геометрия (2-е исправленное издание), Springer-Verlag , ISBN 3-540-65620-0 Раздел 7.2: Вычисление диаграммы Вороного: стр. 151–160.
^ Остин, Дэвид, Диаграммы Вороного и день на пляже , Тематическая колонка, Американское математическое общество .
^ Стивен Форчун. Алгоритм развертки для диаграмм Вороного. Материалы второго ежегодного симпозиума по вычислительной геометрии . Йорктаун-Хайтс, Нью-Йорк, США, стр. 313–322. 1986. ISBN 0-89791-194-6 . библиотека ACM Цифровая
^ Кенни Вонг, Хауси А. Мюллер , Эффективная реализация алгоритма прогонки плоскости Фортуны для диаграмм Вороного , CiteSeerX 10.1.1.83.5571 .

Внешние ссылки

[Mark2000-1] Перейти обратно: ^а ^б ^с де Берг, Марк ; ван Кревелд, Марк ; Овермарс, Марк ; Шварцкопф, Отфрид (2000), Вычислительная геометрия (2-е исправленное издание), Springer-Verlag , ISBN 3-540-65620-0 Раздел 7.2: Вычисление диаграммы Вороного: стр. 151–160.

[2] Остин, Дэвид, Диаграммы Вороного и день на пляже , Тематическая колонка, Американское математическое общество .

[3] Стивен Форчун. Алгоритм развертки для диаграмм Вороного. Материалы второго ежегодного симпозиума по вычислительной геометрии . Йорктаун-Хайтс, Нью-Йорк, США, стр. 313–322. 1986. ISBN 0-89791-194-6 . библиотека ACM Цифровая

[4] Кенни Вонг, Хауси А. Мюллер , Эффективная реализация алгоритма прогонки плоскости Фортуны для диаграмм Вороного , CiteSeerX 10.1.1.83.5571 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]