Algoritmul Fortunei

Algoritmul lui Fortune este un algoritm cu linie de măturare pentru generarea unei diagrame Voronoi dintr-un set de puncte dintr-un plan în timp O folosind memoria O( n ) [1] [2] . Algoritmul a fost publicat inițial de Stephen Fortune în 1986 în lucrarea sa „The Sweeping Line Algorithm for Voronoi Diagrams” [3] . $(n\log n)$

Descrierea algoritmului

Algoritmul menține o linie dreaptă și o linie de coastă care se deplasează de-a lungul planului pe măsură ce algoritmul rulează. O linie de măturat este o linie pe care o putem considera în mod tradițional verticală și care se mișcă de la stânga la dreapta. În orice moment al operației algoritmului, punctele din setul din stânga liniei de măturare vor fi incluse în diagrama Voronoi, în timp ce punctele din dreapta liniei de măturare nu au fost încă calculate. Linia de coastă nu este o linie dreaptă, ci este una complexă, constând din bucăți de parabole , o curbă în bucăți la stânga liniei de măturare. Separă o porțiune a planului în care poate fi cunoscută diagrama Voronoi, independent de alte puncte din dreapta liniei de măturare. Pentru fiecare punct din stânga liniei de măturare, puteți defini o parabolă pentru un punct care este echidistant atât de acest punct, cât și de linia de măturare. Linia de coastă este limita asociațiilor acestor parabole. Pe măsură ce vârful drept al liniei de coastă se mișcă, în care două parabole se intersectează, marginile diagramei Voronoi sunt desenate. Linia de coastă avansează păstrând baza fiecărei parabole exact la jumătatea distanței dintre poziția de început a liniei de măturare și noua poziție a liniei de măturare. Din punct de vedere matematic, aceasta înseamnă că fiecare parabolă este formată folosind o linie de măturare ca directriză , iar un punct dat din mulțime servește drept focar.

Algoritmul menține o structură de date în arbore binar care descrie structura combinatorie a liniei de coastă și o coadă de prioritate care listează evenimentele viitoare potențiale care ar putea schimba structura liniei de coastă. Aceste evenimente includ adăugarea unei alte parabole la linia de coastă (când linia de măturare trece printr-un alt punct de intrare) și ștergerea unei curbe de la linia de coastă (când linia de măturare devine tangentă la cerc prin aproximativ trei puncte de intrare ale căror parabole formează segmente succesive de coastă). Fiecare astfel de eveniment poate fi prioritizat de coordonatele x a liniei de măturare în punctul în care a avut loc evenimentul. Algoritmul constă în ștergerea secvențială a unui eveniment din coada de prioritate, găsirea modificărilor la evenimentele de pe coasta și actualizarea structurii datelor.

Deoarece există O( n ) evenimente de procesat (fiecare asociat cu o anumită proprietate a diagramei Voronoi) și O(log n ) timp pentru a procesa un eveniment (care constă dintr-un număr constant de căutări în arbore binar și operații prioritare în coadă), timpul total este . $O(n\log n)$

Pseudocod

Pseudocod al algoritmului [4] .

Să fie o transformare ,

*(z)

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

unde este distanța euclidiană dintre z și cel mai apropiat punct

d(z)

Fie T „linia de coastă” Fie aria care acoperă punctul p .

R_{p}

Fie raza de limita dintre punctele p și q .

C_{pq)

Fie puncte cu coordonata y minimă , ordonate după coordonatele x creează raze de frontieră verticale inițiale până când IsEmpty( Q ) este executat dacă p este un punct în :

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

Q\obține 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)

Găsiți o regiune în T care conține p ,

*(R_{q})

delimitat de o curbă la stânga și o curbă la dreapta

C_{rq)

C_{qs)

creați noi raze de limită și cu baza p înlocuiți cu în T eliminați din Q orice intersecție între și introduceți orice intersecție în Q și introduceți orice intersecție în Q și p este un vârf Voronoi în :

C_{pq}^{-}

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

*(R_{q})

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

C_{rq)

C_{qs)

C_{rq)

C_{pq}^{-}

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

C_{qs)

*(V)

fie p intersecția dintre stânga și dreapta

C_{qr)

C_{rs}

să fie vecinul stâng și

C_{uq)

C_{qr)

fie vecinul drept în T creează o nouă rază de graniță dacă ,

C_{sv)

C_{rs}

C_{qs}^{0}

q_{y}=s_{y}

sau creați dacă p este partea dreaptă a celei mai mari dintre q și s ,

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

în caz contrar, creați înlocuire cu noul creat în T eliminați orice intersecție din Q și eliminați orice intersecție din Q și introduceți orice intersecție în Q și introduceți orice intersecție în Q și scrieți p ca partea de sus și de jos și scoateți segmentele de limită și terminați în caz că la sfârșit , derivă razele de limită rămase din T

C_{qs}^{-}

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

C_{qs)

C_{uq)

C_{qr)

C_{rs}

C_{sv)

C_{uq)

C_{qs)

C_{qs)

C_{sv)

C_{qr)

C_{rs}

C_{qs)

C_{qr)

C_{rs}

Laturi și discuri ponderate

După cum subliniază Fortune [5] , o versiune modificată a algoritmului liniei de măturare poate fi utilizată pentru a construi o diagramă Voronoi ponderată aditiv în care distanța până la fiecare punct este neutralizată de greutatea punctului. Aceasta poate fi privită în mod echivalent ca o diagramă Voronoi a unui set de discuri centrate în puncte și cu o rază egală cu greutatea punctului.

Punctele ponderate pot fi folosite pentru a controla zonele celulelor Voronoi atunci când parcelele Voronoi sunt folosite pentru a construi hărți de arbori . Într-o diagramă Voronoi ponderată aditiv, bisectoarea dintre puncte este în general o hiperbolă, spre deosebire de diagramele Voronoi neponderate și diagramele de energie de disc

Note

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

Literatură