Fortuneův algoritmus

Fortuneův algoritmus je algoritmus pro generování Voronoiova diagramu ze sady bodů v rovině v čase O pomocí paměti O( n ) [1] [2] . Algoritmus původně publikoval Stephen Fortune v roce 1986 ve svém článku "The Sweeping Line Algorithm for Voronoi Diagrams" [3] . $(n\log n)$

Popis algoritmu

Algoritmus udržuje plynulou přímku a pobřeží , které se při běhu algoritmu pohybují podél roviny. Zametací čára je čára, kterou si můžeme tradičně představit jako vertikální a pohybující se zleva doprava. V každém okamžiku činnosti algoritmu budou do Voronoiova diagramu zahrnuty body ze sady nalevo od rozmítací čáry, zatímco body napravo od rozmítací čáry ještě nebyly vypracovány. Pobřežní čára není přímka, ale je složitá, skládající se z kousků parabol , křivky po částech nalevo od křivky. Odděluje část roviny, v níž lze znát Voronoiův diagram, nezávisle na jiných bodech napravo od rozmítané čáry. Pro každý bod nalevo od křivky můžete definovat parabolu pro bod, který je stejně vzdálený jak od tohoto bodu, tak od křivky. Pobřeží je hranicí asociací těchto parabol. Jak se pohybuje rovný vrchol pobřeží, ve kterém se protínají dvě paraboly, kreslí se okraje Voronoiova diagramu. Pobřežní čára se posouvá a udržuje základnu každé paraboly přesně v polovině cesty mezi počáteční polohou čáry závory a novou polohou čáry závory. Matematicky to znamená, že každá parabola je vytvořena pomocí rozmítané přímky jako směrové přímky a daný bod z množiny slouží jako ohnisko.

Algoritmus udržuje binární stromovou datovou strukturu popisující kombinatorickou strukturu pobřeží a prioritní frontu se seznamem potenciálních budoucích událostí, které by mohly změnit strukturu pobřeží. Tyto události zahrnují přidání další paraboly k pobřeží (když křivka prochází jiným vstupním bodem) a vymazání křivky z pobřeží (když se čára tažení stane tečnou ke kruhu přes některé tři vstupní body, jejichž paraboly tvoří po sobě jdoucí segmenty pobřeží). Každá taková událost může být upřednostněna podle souřadnice x rozmítací čáry v bodě, kde k události došlo. Algoritmus sestává z postupného mazání události z prioritní fronty, hledání změn událostí na pobřeží a aktualizace datové struktury.

Protože existuje O( n ) událostí ke zpracování (každá je spojena s nějakou vlastností Voronoiova diagramu) a O(log n ) času na zpracování události (která sestává z konstantního počtu prohledávání binárního stromu a prioritních frontových operací), celkový čas je . $O(n\log n)$

Pseudokód

Pseudokód algoritmu [4] .

Ať je to proměna ,

*(z)

*(z)=(z_{x},z_{y}+d(z))

kde je euklidovská vzdálenost mezi z a nejbližším bodem

d(z)

Nechť T je "pobřeží" Nechť je oblast pokrývající bod p .

R_{p}

Nechť je hraniční paprsek mezi body p a q .

{\displaystyle C_{pq))

Dovolit být body s minimální souřadnicí y , uspořádané podle souřadnice x vytváří počáteční vertikální hraniční paprsky , dokud se neprovede IsEmpty( Q ) , pokud p je bod v :

{\displaystyle p_{1},p_{2},...,p_{m))

Q\gets S-{p_{1},p_{2},...,p_{m))

C_{p_{1},p_{2}}^{0},C_{p_{2},p_{3}}^{0},...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},...,*(R_{p_{m-1}}),C_{p_{m-1},p_{m}}^{0},*( R_{p_{m}})

p\gets \mathrm {DeleteMin} (Q)

*(V)

Najděte oblast v T obsahující p ,

*(R_{q})

ohraničený křivkou zleva a křivkou zprava

{\displaystyle C_{rq))

{\displaystyle C_{qs))

vytvořte nové hraniční paprsky a se základnou p nahraďte za v T odstraňte z Q jakýkoli průsečík mezi a vložte jakýkoli průsečík do Q a vložte libovolný průsečík do Q a p je vrchol Voronoi v :

C_{pq}^{-}

{\displaystyle C_{pq}^{+))

*(R_{q})

*(R_{q}),C_{pq}^{-},*(R_{p}),C_{pq}^{+},*(R_{q})

{\displaystyle C_{rq))

{\displaystyle C_{qs))

{\displaystyle C_{rq))

C_{pq}^{-}

{\displaystyle C_{pq}^{+))

{\displaystyle C_{qs))

*(V)

nechť p je průsečík vlevo a vpravo

{\displaystyle C_{qr))

C_{rs}

nechť být levým sousedem a

{\displaystyle C_{uq))

{\displaystyle C_{qr))

nechť být správným sousedem v T vytvoří nový hraniční paprsek , pokud ,

{\displaystyle C_{sv))

C_{rs}

C_{qs}^{0}

q_{y}=s_{y}

nebo vytvořte , pokud p je pravá strana vyššího z q a s ,

{\displaystyle C_{qs}^{+))

v opačném případě vytvořte nahradit nově vytvořeným v T odstraňte jakýkoli průsečík z Q a odstraňte jakýkoli průsečík z Q a vložte jakýkoli průsečík do Q a vložte jakýkoli průsečík do Q a napište p jako horní a dolní a vydejte hraniční segmenty a konec v případě end bye odvodit zbývající hraniční paprsky z T

C_{qs}^{-}

C_{qr},*(R_{r}),C_{rs}

{\displaystyle C_{qs))

{\displaystyle C_{uq))

{\displaystyle C_{qr))

C_{rs}

{\displaystyle C_{sv))

{\displaystyle C_{uq))

{\displaystyle C_{qs))

{\displaystyle C_{qs))

{\displaystyle C_{sv))

{\displaystyle C_{qr))

C_{rs}

{\displaystyle C_{qs))

{\displaystyle C_{qr))

C_{rs}

Vyvážené strany a disky

Jak zdůrazňuje Fortune [5] , upravenou verzi algoritmu rozmítané čáry lze použít ke konstrukci aditivně váženého Voronoiova diagramu, ve kterém je vzdálenost ke každému bodu neutralizována váhou bodu. To lze ekvivalentně zobrazit jako Voronoiův diagram sady disků se středem v bodech as poloměrem rovným váze bodu.

Vážené body lze použít k ovládání oblastí Voronoiových buněk, když se Voronoiovy grafy používají k vytváření stromových map . V aditivně váženém Voronoiově diagramu je osou mezi body obecně hyperbola, na rozdíl od nevážených Voronoiových diagramů a diagramů energie disku

Poznámky

↑ de Berg, van Kreveld, Overmars, Schwarzkopf, 2000 , str. 151-160.
↑ Austin - Sloupec funkcí .
↑ Fortune, 1986 , str. 313-322.
↑ Wong, Müller .
↑ de Berg, van Kreveld, Overmars, Schwarzkopf, 2000 , str. 151-160.

Literatura