Fortunen algoritmi

Fortunen algoritmi on pyyhkäisyviivaalgoritmi Voronoi - kaavion muodostamiseksi pistejoukosta tasossa O- ajassa käyttämällä O( n ) -muistia [1] [2] . Stephen Fortune julkaisi algoritmin alun perin vuonna 1986 artikkelissaan "The Sweeping Line Algorithm for Voronoi Diagrams" [3] . $(n\log n)$

Algoritmin kuvaus

Algoritmi ylläpitää pyyhkäisevää suoraa ja rantaviivaa , jotka liikkuvat tasoa pitkin algoritmin suoritettaessa. Pyyhkäisevä viiva on viiva, jota voimme perinteisesti pitää pystysuorana ja liikkuvana vasemmalta oikealle. Milloin tahansa algoritmin toimintahetkellä joukosta pyyhkäisyviivan vasemmalla puolella olevat pisteet sisällytetään Voronoi-kaavioon, kun taas pyyhkäisyviivan oikealla puolella olevia pisteitä ei ole vielä työstetty. Rantaviiva ei ole suora, vaan monimutkainen viiva, joka koostuu paraabelipaloista , paloittain kaarevasta viivasta vasemmalla. Se erottaa osan tasosta, jonka sisällä Voronoi-kaavio voidaan tuntea, riippumatta muista pisteistä, jotka ovat pyyhkäisyviivan oikealla puolella. Jokaiselle pyyhkäisyviivan vasemmalla puolella olevalle pisteelle voit määrittää paraabelin pisteelle, joka on yhtä kaukana sekä tästä pisteestä että pyyhkäisyviivasta. Rantaviiva on näiden paraabelien yhdistysten raja. Kun rantaviivan suora yläosa liikkuu, jossa kaksi paraabelia leikkaavat, piirretään Voronoi-kaavion reunat. Rantaviiva etenee pitäen jokaisen paraabelin kannan tarkalleen pyyhkäisyviivan aloituskohdan ja pyyhkäisyviivan uuden sijainnin puolivälissä. Matemaattisesti tämä tarkoittaa, että jokainen paraabeli muodostetaan käyttämällä pyyhkäisyviivaa suuntaviivana ja tietty piste joukosta toimii fokuksena.

Algoritmi ylläpitää binaaripuutietorakennetta , joka kuvaa rantaviivan kombinatorista rakennetta, ja prioriteettijonoa , jossa luetellaan mahdolliset tulevaisuuden tapahtumat, jotka voivat muuttaa rantaviivan rakennetta. Näihin tapahtumiin kuuluu toisen paraabelin lisääminen rantaviivaan (kun pyyhkäisyviiva kulkee toisen syöttöpisteen kautta) ja käyrän poistaminen rannikolta (kun pyyhkäisyviiva tulee tangentiksi ympyrään noin kolmen syöttöpisteen kautta, joiden paraabelit muodostavat peräkkäisiä rantaviivaosia). Jokainen tällainen tapahtuma voidaan priorisoida pyyhkäisyviivan x - koordinaatilla pisteessä, jossa tapahtuma tapahtui. Algoritmi koostuu tapahtuman peräkkäisestä poistamisesta prioriteettijonosta, rannikon tapahtumien muutosten etsimisestä ja tietorakenteen päivityksestä.

Koska käsiteltävänä on O( n ) tapahtumaa (jokainen liittyy johonkin Voronoi-kaavion ominaisuuteen) ja O(log n ) aikaa tapahtuman käsittelyyn (joka koostuu vakiomäärästä binääripuuhakuja ja prioriteettijonotoimintoja), kokonaisaika on . $O(n\log n)$

Pseudokoodi

Algoritmin pseudokoodi [ 4] .

Olkoon se muutos ,

*(z)

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

missä on euklidinen etäisyys z :n ja lähimmän pisteen välillä

{\näyttötyyli d(z)}

Olkoon T "rantaviiva" Antaa olla alue, joka kattaa pisteen p .

R_{p}

Olkoon rajasäde pisteiden p ja q välillä .

{\displaystyle C_{pq))

Olkoon pisteet, joilla on pienin y -koordinaatit, järjestetyt x - koordinaatilla - luo alustavat pystysuuntaiset rajasäteet, kunnes IsEmpty( Q ) suoritetaan , jos p on piste :

{\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)

Etsi alueesta T , joka sisältää p ,

*(R_{q})

jota rajoittaa vasemmalla oleva kaari ja oikealla oleva käyrä

{\displaystyle C_{rq))

{\displaystyle C_{qs))

luo uudet rajasäteet ja korvaa kantalla p arvolla T poista Q : sta kaikki leikkauspisteet ja lisää mikä tahansa leikkauspiste Q :hen ja lisää mikä tahansa leikkauspiste Q :iin ja p on Voronoin kärkipiste :

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)

olkoon p vasemman ja oikean leikkauspiste

{\displaystyle C_{qr))

{\displaystyle C_{rs))

olkoon vasen naapuri ja

{\displaystyle C_{uq))

{\displaystyle C_{qr))

Olkoon T : n oikea naapuri luo uusi rajasäde , jos ,

{\displaystyle C_{sv))

{\displaystyle C_{rs))

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

q_{y}=s_{y}

tai luo jos p on q :n ja s :n suuremman oikea puoli ,

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

muussa tapauksessa luo korvaa uusilla T : ssä luodulla poista kaikki leikkauspisteet Q:sta ja poista kaikki leikkauspisteet Q :sta ja lisää mikä tahansa leikkaus Q :iin ja lisää mikä tahansa leikkaus Q : iin ja kirjoita p ylä- ja alaosaan ja tulosta rajasegmentit ja lopeta siinä tapauksessa loppuun , johda loput rajasäteet T :stä

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))

Painotetut sivut ja levyt

Kuten Fortune [5] huomauttaa , pyyhkäisyviivaalgoritmin muunneltua versiota voidaan käyttää muodostamaan additiivisesti painotettu Voronoi-kaavio, jossa etäisyys kuhunkin pisteeseen neutraloidaan pisteen painolla. Tätä voidaan katsoa vastaavasti Voronoi-kaaviona joukosta kiekkoja, jotka on keskitetty pisteisiin ja joiden säde on yhtä suuri kuin pisteen paino.

Painotettujen pisteiden avulla voidaan ohjata Voronoi-solujen alueita, kun Voronoin tontteja käytetään puukarttojen rakentamiseen [ . Additiivisesti painotetussa Voronoi-kaaviossa pisteiden välinen puolittaja on yleensä hyperbola, toisin kuin painottamattomissa Voronoi-kaavioissa ja levyenergiakaavioissa , joille

Muistiinpanot

↑ 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.

Kirjallisuus