Fortunov algoritam

Fortune's algorithm animation

Fortunov algoritam je algoritam pokretne linije ѕa generisanje Voronojevih dijagrama iz skupa tačaka u ravni čija je vremenska složenost O(n log n) i prostorna O(n). Objavio ga je Stiven Fortun 1986. u svom radu "Algoritam pokretne linije za Voronojeve dijagrame."

Opis algoritma

Algoritam održava pokretnu liniju i obalsku liniju, koje se obe kreću kroz ravan kako algoritam napreduje. Pokretna linija je prava linija, i možemo po dogovoru pretpostaviti da je vertikalna i da se kreće sleva nadesno. U bilo kom trenutku tokom trajanja algoritma tačke levo od pokretne linije će biti ugrađene u Voronojev dijagram, dok tačke desno od pokretne linije nisu još uvek razmatrane. Obalska linija nije linija, već kompleksna kriva sa leve strane pokretne koja se sastoji od delova parabola; ona razdvaja deo ravni u kojem Voronojev dijagram može biti poznat, bez obzira na tačke desno od pokretne linije, od ostatka ravni. Za svaku tačku levo od pokretne linije, može se definisati parabola tačaka koje su na podjednakom rastojanju od te tačke i od pokretne linije; obalska linija je granica unije ovih parabola. Dok pokretna linija napreduje, temena obalske linije, u kojoj se dve parabole seku, prati ivice Voronojevog dijagrama. Obalska linija napreduje čuvajući svaku parabolu tačno na pola puta između tačaka preko kojih se prethodno prešlo pokretnom linijom i novog položaja pokretne linije.

Algoritam održava kao strukturu podataka binarno stablo pretrage koje opisuje strukturu obalske linije i prioritetni red koji sadrži potencijalne buduće događaje koji mogu da promene strukturu obalske linije. Ovi događaji uključuju dodavanje nove parabole u obalsku liniju (kada pokretna linija naiđe na novu ulaznu tačku) i uklanjanje krive iz obalske linije (kada pokretna linija postane tangenta na krugu kroz neke tri ulazne tačke čije parabole formiraju uzastopne segmente obalske linije). Prioritet svakog takvog događaja se može odrediti na osnovu x-koordinate pokretne linije u tački u kojoj se događaj desio. Sam algoritam se onda sastoji od uklanjanja sledećeg događaja iz prioritetnog reda, pronalaženja promena koje događaj prouzrokuje u obalskoj liniji i ažuriranja struktura podataka.

Pošto ima O(n) događaja koje treba obraditi (svaki je povezan sa nekom karakteristikom Voronojevog dijagrama) i O(log n) vremena za obradu događaja (svaki se sastoji od konstantnog broja operacija na binarnom stablu pretrage i prioritetnom redu) ukupno vreme je O(n log n).

Pseudokod

Pseudokod opis algoritma.

let $*(z)$ be the transformation $*(z)=(z_{x},z_{y}+d(z))$,
  where $d(z)$ is the Euclidean distance between $z$ and the nearest site
let $T$ be the "beach line"
let $R_{p}$ be the region covered by site $p$.
let $C_{pq}$ be the boundary ray between sites $p$ and $q$.
let $p_{1},p_{2},...,p_{m}$ be the sites with minimal $y$-coordinate, ordered by $x$-coordinate
$Q\gets S-{p_{1},p_{2},...,p_{m}}$
create initial vertical boundary rays $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}})$
while not IsEmpty($Q$) do
    $p$ ← DeleteMin($Q$)
    case $p$ of
    $p$ is a site in $*(V)$:
        find the occurrence of a region $*(R_{q})$ in $T$ containing $p$,
          bracketed by $C_{rq}$ on the left and $C_{qs}$ on the right
        create new boundary rays $C_{pq}^{-}$ and $C_{pq}^{+}$ with bases $p$
        replace $*(R_{q})$ with $*(R_{q}),C_{pq}^{-},*(R_{p}),C_{pq}^{+},*(R_{q})$ in $T$
        delete from $Q$ any intersection between $C_{rq}$ and $C_{qs}$
        insert into $Q$ any intersection between $C_{rq}$ and $C_{pq}^{-}$
        insert into $Q$ any intersection between $C_{pq}^{+}$ and $C_{qs}$
    $p$ is a Voronoi vertex in $*(V)$:
        let $p$ be the intersection of $C_{qr}$ on the left and $C_{rs}$ on the right
        let $C_{uq}$ be the left neighbor of $C_{qr}$ and
          let $C_{sv}$ be the right neighbor of $C_{rs}$ in $T$
        create a new boundary ray $C_{qs}^{0}$ if $q_{y}=s_{y}$,
          or create $C_{qs}^{+}$ if $p$ is right of the higher of $q$ and $s$,
          otherwise create $C_{qs}^{-}$
        replace $C_{qr},*(R_{r}),C_{rs}$ with newly created $C_{qs}$ in $T$
        delete from $Q$ any intersection between $C_{uq}$ and $C_{qr}$
        delete from $Q$ any intersection between $C_{rs}$ and $C_{sv}$
        insert into $Q$ any intersection between $C_{uq}$ and $C_{qs}$
        insert into $Q$ any intersection between $C_{qs}$ and $C_{sv}$
        record $p$ as the summit of $C_{qr}$ and $C_{rs}$ and the base of $C_{qs}$
        output the boundary segments $C_{qr}$ and $C_{rs}$
    endcase
endwhile
output the remaining boundary rays in $T$

Težinske lokacije i diskovi

Kao što Fortun opisuje u modifikovana verzija algoritma pokretne linije može biti iskorišćena za konstrukciju aditivnog težinskog Voronojevog dijagrama, u kome udaljenost do svake lokacije (generatora) je pomerena za težinu lokacije; ovo može biti ekvivalentno posmatrano kao Voronojev dijagram skupa diskova čiji je centar u lokacijama sa radijusom jednakim težini lokacije.

Spoljašnje veze

• Fortunov algoritam implementiran u C-u
• Fortunov algoritam implementiran u C++
• Fortunov algoritam implementiran u javascript-u