Fortunův algoritmus a jeho implementace
Stručně o Voroného diagramu
Mějme N bodů v rovině, kterým budeme říkat místa. Přiřaďme místu $a$ množinu bodů $V(a)$ z dané roviny takovou, že vzdálenost její bodů od $a$ je menší nebo rovná vzdálenosti jakéhokoli jiného místa. Je zřejmé, že množina bodů $V(a)$ bude vytvářet souvislou plochu kolem místa $a$. Tj. ke každému místu $a$ patří oblast, ze které je to k $a$ nejblíž.
Průnikem dvou množin $V(a)$ a $V(b)$ jsou body, mající stejnou vzdálenost od $a$ jako od $b$, přitom žádné místo neleží v kratší vzdálenosti od nich. Mohou ležet na přímce, polopřímce nebo úsečce. Voroného diagramem nazveme právě množinu těchto bodů.
Podobně lze Voroného diagram definovat pro vícerozměrné prostory a různé metriky.
VD jako graf
Na voroného diagram se lze dívat jako na neorientovaný graf. Jeho hrany jsou výše zmíněné úsečky (průniky V(a) a V(b)) a vrcholy jsou průniky těchto úseček, tedy body, mající stejnou vzdálenost ke třem nebo více nejbližším místům. Poznamenejme, že některé hrany mohou vést do nekonečna.
Delaunayho triangulace
Na množině bodů $P$ ležících v rovině lze vytvořit velké množství triangulací. Dleaunayho triangulací $DT(P)$ nazveme tu triangulaci, kde kružnice opsaná libovolnému trojúhelníku neobsahuje uvnitř žádné body z $P$. Tato triangulace má "nejrovnostrannější" trojúhelníky - maximalizuje se jejich minimální úhel. Delaunayho triangulace je duálním grafem k Voroného diagramu pro danou množinu bodů v rovině.
Algoritmy pro výpočet Voroného diagramu
- Rozděl a panuj - algoritmus rozdělí body na pravou a levou část, rekurzivně spočítá Voroného diagramy těchto dvou částí a nakonec dvě části spojí, vytvořením chybějící části diagramu mezi nimi.
- Inkrementální algoritmus - spočítá Voroného diagram pro dvě místa. Při přidávání dalšího místa vypočítá nový diagram pro danou část.
Nevýhody těchto algoritmů - náročná implementace, netriviální spojování diagramů, velké numerické chyby.
Fortunův algoritmus
Tento algoritmus je založen na "zamétání" roviny. Po rovině se pohybuje přímka $L$ (např. zezdola nahoru), která zpracuje každý bod, přes který projde. Pokusme se určit, které body $x$ ležící pod ní patří do Voroného diagramu.
Pokud je bod $x$ stejně daleko od dvou míst $a$ a $b$ (všechny 3 leží pod přímkou), ještě nemusí být v diagramu, jelikož těsně nad přímkou může ležet místo $c$, které je k němu blíž než $a$ či $b$. Voroného diagram můžeme určit pouze pro body, které mají blíž k nějakému místu $a$ než k přímce $L$. Tyto body leží pod parabolou ($a$ je její ohnisko a $L$ řídící přímkou, z definice paraboly).
Hranice, pod kterou už můžeme diagram rozhodnout, je tvořená oblouky parabol (angl. "beachline"). Průsečíky parabol mají stejně daleko ke dvěma sousedním místům (ohniskům sousedních parabol) jako k přímce, a tedy při pohybu přímky $L$ "kreslí" diagram. Hranice je tedy posloupnost oblouků $p$ a jejich průsečíků $x$, kterým říkejme hrany, jelikož při pohledu na VD jako na graf $x$ kreslí jeho hranu.
Hraniční posloupnost $p_0, x_0, p_1, x_1, .... x_{n-1}, p_n$.
Posloupnost se však během kreslení může změnit, a to dvěma způsoby:
- Místní událost - vstoupí do ní nové místo - nová parabola. Rozpůlí parabolu pod ní na dva oblouky a ze středu začnou vycházet do stran dvě nové hrany. Tedy parabolu $p_i$ nahradí posloupnost $p_i, x_i, p_{i+1}, x_{i+1}, p_{i+2}$, kde $p_i$ a $p_{i+2}$ mají ohnisko původní paraboly a $p_{i+1}$ má ohnisko v nově přidaném místě.
- Kružnicová událost - zanikne parabola - sousední paraboly ji zatlačí a vznikne zde nová hrana.. Tedy posloupnost $x_{i-1}, p_i, x_i$ se nahradí novou hranou $x_i$. Místo, kde parabola $p_i$ zanikne, má stejně daleko k ohnisku pi jako k ohniskům obou sousedních oblouků, je tedy středem nimi definované kružnice (proto "kružnicová" událost).
Události budeme uchovávat ve frontě, kde budou seřazeny podle y. Jelikož vidíme, že se hraniční posloupnost mění pouze v několika místech, můžeme s přímkou L hýbat diskrétně, z jedné události na druhou.
Kód algoritmu
Spousta autorů mylně uvádí, že při kontrole kružnicové události stačí najít kružnici a zjistit, zda její vrchol leží nad zametací přímkou. To však nestačí, jelikož dvě okolní hrany mohou jít směrem od středu kružnice a nikdy se nesetkají.¨
Implementace
Fronta událostiJako frontu událostí je zvykem použít prioritní frontu, ve které jsou události uspořádány podle souřadnice "y". Měla by umožňovat mazání prvků.
Hraniční posloupnostHraniční posloupnost lze reprezentovat jako obousměrně spojový seznam. Vkládání a mazání je jednoduché, ovšem vyhledání potřebné položky trvá lineární čas.
Steven Fortune přišel s výbornou myšlenkou reprezentace hraniční posloupnosti jako binárního stromu.
- Každý list představuje jeden oblouk. Vnitřní uzly představují hrany.
- pokud je oblouk jeden, stromem je pouze jeden list
-
Při přidání paraboly do listu se daný list stane vnitřním uzlem, jedna půlka bude levým synem, vpravo bude vnitřní uzel, kde vlevo bude nový oblouk a vpravo druhá půlka.
- Mazání listu je rovněž jednoduché. Otec představuje levou nebo pravou hranu, určitý "vyšší předek" představuje další hranu. Pokud jsme levým synem, nahradíme otce pravým synem a obráceně. "Vyššímu předkovi" přiřadíme novou hranu.
Složitost
Věta: Pro $n \geq 3$ míst v rovině obsahuje Voroného diagram max. $2n - 5$ vrcholů a $3n - 6$ hran.
Důkaz:
- Pro body ležící na přímce to zřejmě platí.
- Předpokládejme, že body neleží na přímce.
Označme si:
- $V$: počet vrcholů voroného diagramu
- $E$: počet hran diagramu
- $N$: počet stěn voroného diagramu = počet míst
Z Eulerova vzorce víme, že pro každý souvislý rovinný graf platí, že:
$V - E + N = 2$
Jelikož Voroného diagram obsahuje nekončící hrany, vytvořme vrchol "nekonečno" a spojme s ním tyto hrany. Nyní máme rovinný graf.
$(V + 1) - E + N = 2$
U Voroného grafu navíc víme, že každý jeho vrchol (včetně "nekonečna") má stupeň aspoň 3. Hrana je mezi dvěma vrcholy, a tedy
$3 * (V + 1) \leq 2 * E$
Jednoduchou algebraickou úpravou dostaneme původní tvrzení.
Primitivní operace, jako vyhledání prvku ve stromu nebo ve frontě, vymazání z fronty, trvají logaritmický čas $O(log(n))$. Při každé události uděláme konstatntí počet těchto primitivních operací.
Počet místních událostí je $N$, kružnicových je až $2N - 5$. Při každé z nich provedeme $k$ primitivních operací. Celková složitost je tedy $O(n*log(n))$.
Implementace v C++
ZDE je moje implementace napsaná v C++ a komentovaná v angličtině. Součástí je i EXE soubor, který spustí animaci bodů a kreslení diagramů (v OpenGL). Rychlost je ohromující - program dokáže spočítat diagram pro 500 bodů 50 krát za vteřinu, výpočet je asi 10 krát rychlejší než stejná implementace v ActionScript 3.
Hezky.
Ivanku diky. Shoodu okolnosti delam taky zapoctak na mff. A po stoprvni co jsem na teto strance jsem si vsiml ze ses taky matfyzak.
Ahoj, pěkný článek. Úplně stejný jsem našel v Angličtině a teď si uvědomuji, že je také tvůj.
Bude se mi to hodit do jedné hry, takže díky. :)
Moc pěkné, učím se na zkoušku z ADS a ty jsi mi perfektně zpracoval jednu celou otázku. Díky.
Hezký článek, dostal jsem se k němu při řešení problému nalezení nejvzdálenějšího bodu ležícího v polygonu ke konečné množině bodů, které taktéž leží v tomto polygonu.
Voroného diagram nabízí moc hezké řešení tohoto problému a implementace autora je k tomu dobře přizpůsobená.
Pokud bych se však měl na výsledné řešení, které zde najdeme, podívat tím nejkritičtějším pohledem, přece jen najdu pár chyb:
1) Kritická chyba: algoritmus (jeho implementace) nefunguje správně v případě, že se dva body nachází na stejné souřadnici y. I když je na tento případ pamatováno (podmínka zkraje funkce InsertParabola), tak očividně není vyřešen správně.
2) Technická chyba: algoritmus způsobuje úniky paměti z důvodu neexistence destruktoru třídy Voronoi.
3) Doporučení: vytváření a mazání objektů v paměti (new, delete) v průběhu činnosti algoritmu snižuje jeho efektivitu, byť je to velmi elegantní. Je k tomu přece jen potřeba management operačního systému, který paměť programu přidělí nebo odebere. Lépe je paměť přiřadit jednou na začátku algoritmu a na konci ji odstranit.