Algorytm fortuny

Animacja algorytmu Fortune

Algorytm Fortune to algorytm linii przemiatania służący do generowania diagramu Woronoja ze zbioru punktów na płaszczyźnie przy użyciu czasu O ( n log n ) i przestrzeni O ( n ). Został pierwotnie opublikowany przez Stevena Fortune'a w 1986 roku w jego artykule „Algorytm linii zamiatanej dla diagramów Woronoja”.

Opis algorytmu

Algorytm utrzymuje zarówno linię przeciągnięcia , jak i linię plaży , które poruszają się po płaszczyźnie w miarę postępu algorytmu. Linia przeciągnięcia jest linią prostą, którą możemy umownie przyjąć jako pionową i poruszającą się od lewej do prawej w poprzek płaszczyzny. W dowolnym momencie algorytmu punkty wejściowe na lewo od linii przemiatania zostaną włączone do diagramu Woronoja, podczas gdy punkty na prawo od linii przemiatania nie będą jeszcze brane pod uwagę. Linia plaży nie jest linią prostą, ale skomplikowaną, fragmentaryczną krzywą na lewo od linii przeciągnięcia, złożoną z kawałków paraboli ; dzieli część płaszczyzny, w której można poznać diagram Woronoja, niezależnie od tego, jakie inne punkty mogą znajdować się na prawo od linii przeciągnięcia, od reszty płaszczyzny. Dla każdego punktu na lewo od linii przeciągnięcia można zdefiniować parabolę punktów równoodległych od tego punktu i od linii przeciągnięcia; linia plaży jest granicą połączenia tych paraboli. W miarę postępu linii przemiatania wierzchołki linii plaży, w których przecinają się dwie parabole, wyznaczają krawędzie diagramu Woronoja. Linia plaży rozwija się, utrzymując każdą podstawę paraboli dokładnie w połowie drogi między punktami początkowo przemiatanymi linią wobulacji a nową pozycją linii wobulacji. Matematycznie oznacza to, że każda parabola jest tworzona przy użyciu linii przemiatania jako kierownicy i punktu wejściowego jako ogniska.

Algorytm utrzymuje jako struktury danych binarne drzewo wyszukiwania opisujące kombinatoryczną strukturę linii plaży oraz kolejkę priorytetową zawierającą potencjalne przyszłe zdarzenia, które mogą zmienić strukturę linii plaży. Zdarzenia te obejmują dodanie kolejnej paraboli do linii plaży (kiedy linia przeciągnięcia przecina inny punkt wejściowy) i usunięcie krzywej z linii plaży (kiedy linia przeciągnięcia staje się styczna do okręgu przechodzącego przez jakieś trzy punkty wejściowe, których parabole tworzą kolejne odcinki linii brzegowej). Każdemu takiemu zdarzeniu można nadać priorytet na podstawie x linii przemiatania w punkcie wystąpienia zdarzenia. Sam algorytm polega następnie na wielokrotnym usuwaniu następnego zdarzenia z kolejki priorytetów, wyszukiwaniu zmian, które zdarzenie powoduje w linii brzegowej i aktualizowaniu struktur danych.

Ponieważ istnieje O( n ) zdarzeń do przetworzenia (każde jest powiązane z jakąś cechą diagramu Woronoja) i O(log n ) czasu na przetworzenie zdarzenia (każde składa się ze stałej liczby binarnych drzew wyszukiwania i operacji kolejki priorytetowej), całkowity czas to O( n log n ).

Pseudo kod

Pseudokodowy opis algorytmu.




     
    
    
 niech  ${\ Displaystyle * (z)}$  będzie transformacją  $))}$  ${\ Displaystyle * (z) = (z_ {x}, z_ {y } +$  $z$  , gdzie  jest odległością euklidesową między  $a$  najbliższym miejscem, niech  $będzie$  „linią plaży” niech  ${\ Displaystyle R_ {p} }$  będzie regionem objętym przez witrynę  $p$  . niech do   ${\ displaystyle C_ {pq}}$  będzie promieniem granicznym między  $p$  i  $q$  . niech   $witryn,$  na których ma być zastosowany ten algorytm. niech   $uporządkowanej$  ${1}, p_ {2}, ..., p_ {m}} być witrynami wyodrębnionymi z minimalnej współrzędnej y$  według  współrzędnej  $,$  niech  $DeleteMin$  (  $X$  ) być aktem usunięcia najniższego i najbardziej wysuniętego na lewo miejsca  $będzie$  $} \displaystyle S}$  według y, chyba że są identyczne, w takim przypadku posortuj według x) niech  mapą Woronoja  ${\ displaystyle V$  , które ma być skonstruowane przez ten algorytm  ${\ Displaystyle Q \ pobiera {p_ {1}, p_ {2}, ..., p_ {m}, S}}$  początkowe pionowe promienie graniczne  ${\ Displaystyle C_ {p_ {1}, p_ {2}} ^ {0}, C_ {p_ {2}, p_ {3}} ^ {0}, ... C_ { p_{m-1},p_{m}}^{0}}$  ${\ Displaystyle T \ dostaje * (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}})} podczas gdy nie IsEmpty($  Q  )  $do$  p  ←  $DeleteMin$  (  $Q$  )  przypadek  $p$  z  $p$  $Displaystyle * ($  miejscem w  $)}$  : znajdź występowanie regionu  T  $zawierającego$  p  $,$  przez  ${\ Displaystyle C_ {rq}}$  po lewej i do  ${\ Displaystyle C_ {qs}}$  po prawej tworzą nowe promienie graniczne  ${pq} ^ {-}}$  i  ${\ Displaystyle C_ {pq} ^ {+}}$  z podstawami  $p$  zastąpić  ${\ Displaystyle * (R_ {q})}$  z  ${\ Displaystyle * (R_ {q}), C_ {pq} ^ {-}, * (R_ {p}), C_ {pq} ^ {+}, *$  w  $T$  usuń z  $Q$  dowolne przecięcie między  ${\ displaystyle C_ {rq}}$  i  $\ displaystyle C_ {qs}}$  wstaw do  $Q$  dowolne przecięcie między do  $\ displaystyle C_ {rq}}$  i do  ${\ Displaystyle C_ {pq} ^ {-}}$  wstaw do  $Q$  dowolne przecięcie między  ${\ displaystyle C_ {pq} ^ {+}}$  do  $qs}}$  $\ displaystyle C_$  ${\ displaystyle C_ {rs}}$  $p$  jest wierzchołkiem Woronoja w  ${\ Displaystyle * (V)}$  : niech  $p$  będzie przecięciem do  ${\ displaystyle C_ {qr}}$  po lewej stronie i  po prawej niech  $}$  lewym sąsiadem do  $C_ {qr$  i niech do  $}$  $Displaystyle q_ {y } = s_ {y}}$  prawym sąsiadem  $Displaystyle$  T  utworzyć nowy promień graniczny  $C_ {qs} ^ {0}}$  y  $\$  lub stwórz do  ${\ displaystyle C_ {qs } ^ {-}}$  $\ displaystyle C_ {qs} ^ {+}}$  jeśli  $p jest na prawo$  wyższej z  $q$  i  $s$  , w przeciwnym razie utwórz  zastąpić  ${\ displaystyle C_ {qs}}$  $Displaystyle C_ {qr}, * (R_ {r}), C_ {rs}}$  utworzonym do  w  $T$  usuń z  $Q$  dowolne przecięcie między  $\ displaystyle C_ { rs}}$  do  $\ displaystyle C_$  $qr}}$  z  $Q$  dowolne przecięcie między  i do  $\ Displaystyle C_ {sv}}$  wstaw do  $wstaw$  $s$  {  ${$  qs  do  $Q$  dowolne przecięcie między  $\ Displaystyle C_ {qs}}$  i  $C_ {sv}}$  $i$  zapisz  $p$  jako szczyt do  ${\ displaystyle C_ {qr}}$  i do  $\ displaystyle C_ {rs}$  do  ${\ Displaystyle C_ {qs}}$  segmenty graniczne  ${\ displaystyle C_ {qr}}$  do  $displaystyle C_ {rs}}$  endcase  endwhile  wyprowadź pozostałą granicę promienie w  $t$

Ważone witryny i dyski

Jak opisuje Fortune w odnośniku, zmodyfikowaną wersję algorytmu linii przemiatania można wykorzystać do skonstruowania addytywnie ważonego diagramu Woronoja, w którym odległość do każdego miejsca jest kompensowana przez wagę miejsca; można to równoważnie postrzegać jako diagram Woronoja zestawu dysków, wyśrodkowanych w miejscach o promieniu równym wadze miejsca.

Miejsca ważone mogą być używane do kontrolowania obszarów komórek Woronoja podczas używania diagramów Woronoja do konstruowania map drzew . Na diagramie Woronoja ważonym addytywnie dwusieczna między miejscami jest na ogół hiperbolą, w przeciwieństwie do nieważonych diagramów Woronoja i diagramów mocy dysków, dla których jest to linia prosta.

Linki zewnętrzne