Fortunes algoritme

Fortunes algoritme er en sweeping-linjealgoritme til at generere et Voronoi-diagram fra et sæt punkter i et plan i O- tid ved hjælp af O( n ) -hukommelse [1] [2] . Algoritmen blev oprindeligt udgivet af Stephen Fortune i 1986 i hans papir "The Sweeping Line Algorithm for Voronoi Diagrams" [3] . $(n\log n)$

Beskrivelse af algoritmen

Algoritmen opretholder en fejende lige linje og kystlinje , der bevæger sig langs flyet, mens algoritmen kører. En fejende linje er en linje, som vi traditionelt kan tænke på som lodret og bevæger sig fra venstre mod højre. På et hvilket som helst tidspunkt af algoritmens drift vil punkterne fra sættet til venstre for sweepinglinjen blive inkluderet i Voronoi-diagrammet, mens punkterne til højre for sweepinglinjen endnu ikke er udarbejdet. Kystlinjen er ikke en lige linje, men er en kompleks, bestående af stykker af parabler , en stykkevis kurve til venstre for den fejende linje. Den adskiller en del af planet, inden for hvilken Voronoi-diagrammet kan kendes, uafhængigt af andre punkter til højre for den fejende linje. For hvert punkt til venstre for den fejende linje kan du definere en parabel for et punkt, der er lige langt fra både dette punkt og den fejende linje. Kystlinjen er grænsen for foreningerne af disse parabler. Når den lige top af kystlinjen bevæger sig, hvor to parabler krydser hinanden, tegnes kanterne af Voronoi-diagrammet. Kystlinjen rykker frem og holder bunden af hver parabel nøjagtigt halvvejs mellem sweep-linjens startposition og sweep-linjens nye position. Matematisk betyder det, at hver parabel er dannet ved hjælp af en fejende linje som et retningslinje , og et givet punkt fra sættet fungerer som fokus.

Algoritmen opretholder en binær trædatastruktur , der beskriver den kombinatoriske struktur af kystlinjen, og en prioritetskø , der viser potentielle fremtidige begivenheder, der kan ændre kystlinjens struktur. Disse hændelser omfatter tilføjelse af endnu en parabel til kystlinjen (når sweep-linjen passerer gennem et andet inputpunkt) og sletning af en kurve fra kystlinjen (når sweep-linjen bliver tangent til cirklen gennem nogle tre inputpunkter, hvis parabler danner successive kystlinjesegmenter). Hver sådan hændelse kan prioriteres efter x - koordinaten for fejelinjen på det punkt, hvor hændelsen fandt sted. Algoritmen består af sekventielt at slette en hændelse fra prioritetskøen, finde ændringer til hændelser i kystlinjen og opdatere datastrukturen.

Da der er O( n ) hændelser at behandle (hver tilknyttet en eller anden egenskab i Voronoi-diagrammet) og O(log n ) tid til at behandle en hændelse (som består af et konstant antal binære træsøgninger og prioriterede køoperationer), den samlede tid er . $O(n\log n)$

Pseudokode

Pseudokode for algoritmen [4] .

Lad det være en forvandling ,

*(z)

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

hvor er den euklidiske afstand mellem z og det nærmeste punkt

d(z)

Lad T være "kystlinjen" Lad være området, der dækker punktet p .

R_{p}

Lade være grænsestrålen mellem punkterne p og q .

{\displaystyle C_{pq))

Lad være punkter med minimum y -koordinat, ordnet efter x - koordinat skaber indledende lodrette grænsestråler, indtil IsEmpty( Q ) udføres, hvis p er et punkt i :

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

Q\får 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)

Find et område i T , der indeholder p ,

*(R_{q})

afgrænset af en kurve til venstre og en kurve til højre

{\displaystyle C_{rq))

{\displaystyle C_{qs))

skabe nye grænsestråler og med base p erstat med i T fjern fra Q ethvert skæringspunkt mellem og indsæt ethvert skæringspunkt i Q og indsæt ethvert skæringspunkt i Q og p er et Voronoi-toppunkt i :

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)

lad p være skæringspunktet mellem venstre og højre

{\displaystyle C_{qr))

{\displaystyle C_{rs))

lad være venstre nabo og

{\displaystyle C_{uq))

{\displaystyle C_{qr))

lad være den rigtige nabo i T opret en ny grænsestråle , hvis ,

{\displaystyle C_{sv))

{\displaystyle C_{rs))

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

q_{y}=s_{y}

eller opret hvis p er højre side af den højeste af q og s ,

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

ellers skal du oprette udskiftning med den nyoprettede i T fjern ethvert skæringspunkt fra Q og fjern ethvert skæringspunkt fra Q og indsæt ethvert skæringspunkt i Q og indsæt ethvert skæringspunkt i Q og skriv p som toppen og bunden og udskriv grænsesegmenterne og slut i tilfælde end bye udled de resterende grænsestråler fra T

C_{qs}^{-}

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

{\displaystyle C_{qs))

{\displaystyle C_{uq))

{\displaystyle C_{qr))

{\displaystyle C_{rs))

{\displaystyle C_{sv))

{\displaystyle C_{uq))

{\displaystyle C_{qs))

{\displaystyle C_{qs))

{\displaystyle C_{sv))

{\displaystyle C_{qr))

{\displaystyle C_{rs))

{\displaystyle C_{qs))

{\displaystyle C_{qr))

{\displaystyle C_{rs))

Vægtede sider og skiver

Som Fortune [5] påpeger, kan en modificeret version af sweeping line-algoritmen bruges til at konstruere et additivt vægtet Voronoi-diagram, hvor afstanden til hvert punkt neutraliseres af punktets vægt. Dette kan ses tilsvarende som et Voronoi-diagram af et sæt skiver centreret i punkterne og med en radius svarende til punktets vægt.

Vægtede punkter kan bruges til at kontrollere områderne af Voronoi-celler, når Voronoi-plot bruges til at bygge trækort . I et additivt vægtet Voronoi-diagram er halveringslinjen mellem punkter generelt en hyperbel, i modsætning til uvægtede Voronoi-diagrammer og diskenergidiagrammer ,

Noter

↑ de Berg, van Kreveld, Overmars, Schwarzkopf, 2000 , s. 151-160.
↑ Austin - Feature Column .
↑ Fortune, 1986 , s. 313-322.
↑ Wong, Müller .
↑ de Berg, van Kreveld, Overmars, Schwarzkopf, 2000 , s. 151-160.

Litteratur