9. Diagramy Voronoia
Úvod. Diagramy Voronoia podávají řešení problému známého pod anglickým názvem "post orlice problém". V něm jde o to rozdělit teritorium města na oblasti okolo jednotlivých pošt tak, aby v každé oblasti byla místní pošta ta nejbližší. Jiným příkladem je určení spádových oblastí nemocnic podle vzdálenosti. Matematická formulace problému je následující:
V rovině je dána množina bodů P = {p±,P2, ■ ■ ■ ,Pn}- Diagram Voronoia (zkráceně V-diagram) je rovinné podrozdělení, které má oblasti
V(pi) = {q E IR2; dist(q,pi) < dist(q,pj) pro všechna j E P\ {i}},
kde dist(g,p) označuje klasickou vzdálenost bodů q a p.
OBR 9.1 Příklad diagramu Voronoia.
Množinou bodů v rovině, které mají vzdálenost k bodu Pí menší nebo rovnu vzdálenosti k bodu p j ý Pi Je polorovina
h(pi,Pj) = {q e K2; dist(g,pj) < dist(g,pi)}.
Oblast Voronia V(pi) je tedy rovna průniku všech takových polorovin pro j ^ i
h(Pi,Pj) =   H h(pi,pj).
jeP\{i}
Průnik n — 1 polorovin umíme podle 5. kapitoly najít v čase 0(n\ogn) nebo podle 6. kapitoly v očekávaném čase 0(n). Najít tímto způsobem všechny oblasti by vyžadovalo čas aspoň 0(n2). My si ukážeme algoritmus pro nalezení diagramu Voronoia s časovou náročností 0(n\ogn). O tom, že taková časová náročnost je reálná, svědčí následující tvrzení:
Věta 9.1. Diagram Voronoia pro n > 3 bodů má nejvýše 2n — 5 vrcholů a nejvýše 3n — 6 hran.
Důkaz. Označme m počet vrcholů a h počet hran V-diagramu. Přidáním vrcholu v,^ v "nekonečnu", do kterého vedou všechny hrany V-diagramu, které jsou polopřímky, vytvoříme z V-digramu rovinný graf, který má n oblastí, m + 1 uzlů a h hran. Viz obrázek.
OBR 9.2 Doplnění V-digramu na planární graf. Pro něj platí Eulerova věta
m+1 — h + n = 2. Stupeň každého uzlu je aspoň 3, součet všech stupňů je 2h. Tedy
2h > 3(m + 1).
Dosadíme-li do této nerovnosti h = m + n — 1 z Eulerovy věty, dostaneme
2m + 2n - 2 > 3(m + 1),
tedy po úpravě m <2n — 5. Obdobně po dosazení m = h — n + 1 je
2h > 3(h-n + 2), l
2
což dává h < 3n — 6. □
Pro množinu P a každý bod g G I2 \ P definujeme kruh se středem g a poloměrem, který je roven vzdálenosti bodu q od množiny P
CP(q) = {r G IR2; dist(g,r) < dist(g,P)}.
Na kružnici ohraničující tento kruh leží vždy aspoň jeden bod množiny P. Je zřejmé, že platí následující tvrzení:
Lemma 9.2. Bod q leží na hraně V-diagramu, právě když na hranici Cp(q) leží aspoň dva body z množiny P.
Bod r je vrcholem V-diagramu, právě když na hranici Cp(r) leží aspoň tři body z množiny P.
OBR 9.3 Ilustrace lemmatu 9.2.
9.1. Metoda zametači přímky. Jeden z možných algoritmů pro konstrukci V-diagramu používá metodu zametači přímky, ale v podobě, která je poněkud sofistikovanější než byly ty, se kterými jsme se prozatím setkali. Zametači přímka / postupuje rovinou shora dolů a nad ní se vytváří V-diagram. Tento diagram nemůže vznikat v celé polorovině /+ nad přímkou /, ale pouze v její části, která je sjednocením oblastí nad jistými parabolami. Jak taková oblast vypadá?
Bod q leží v této oblasti, jestliže pro některý bod pi G P H /+ platí
dist(q, pi) < dist(g,/).
Pak totiž pro všechny body p j G P z poloroviny l~ pod přímkou / je
dist(g,pj) < dist(g,/) < dist(g,Pj).
Tedy bod q z této oblasti určitě neleží v oblasti Voronoia V {pj) pro p j G P H l~.
Označme a(p, l) parabolu tvořenou body, které mají stejnou vzdálenost od bodu p i přímky /. Bod p je ohniskem a přímka / řídící přímkou této paraboly. Nechť a+(p, l) je množina bodů ležících nad parabolou a(p, l) nebo na ní. Oblast nad zametači přímkou /, kde bude V-diagram vytvořen, je sjednocení
(J a+(Pi,l)-
PiePni+
Hranici této oblasti, tvořenou oblouky parabol, budeme nazývat plážová linie (beach line).
Strom T bude v tomto případě vyvážený binární strom, který ve svých listech udržuje pořadí oblouků parabol v plážové linii. Zlomové body plážové linie, tj. body kde se setkávají dva po sobě jdoucí oblouky plážové linie příslušné parabolám s ohnisky Pi a p2, mají stejnou vzdálenost od p\ i p2, neboť
dist(g,pi) = dist(g,/) = dist(g,p2),
a leží tedy na hranách diagramu Voronoia. Tyto zlomové body jsou vnitřními uzly stromu T. Jejich popis tvaru (pľ : p2) značí, že se jedná o průsečík parabol s ohnisky Pi a ř>2 (°bě mají řídící přímku /) a to ten (obvykle jsou dva), který má oblouk paraboly s ohniskem p\ zleva a oblouk paraboly s ohniskem p2 zprava. Pomocí takového stromu
3
lze pro bod p na zametači přímce / vyhledat oblouk plážové linie, který leží nad bodem p. Následující obrázek ukazuje příklad plážové linie a příslušného stromu.
OBR 9.4 Plážová linie
OBR 9.5 Vyvážený binární strom příslušný předchozí plážové linii.
9.2. Události. Zásadní význam mají odpovědi na následující dvě otázky:
• Kdy se v plážové linii objeví nový oblouk?
• Kdy z plážové linie nějaký oblouk zmizí?
Na tyto otázky odpovídají následující dvě lemmata. Jejich důkazy jsou technické, proto je nebudeme provádět a raději se omezíme na jejich ilustraci pomocí obrázků.
Lemma 9.3. Nové oblouky v plážové linií vznikají, právě káyž zametači přímka prochází některým boáem množiny P.
Takový bod nazýváme místní událost, anglicky site event. Situaci ilustruje následující obrázek. Zametači přímka / prochází bodem p G P. Nechť a je oblouk plážové linie nad bodem p, který je částí paraboly s ohniskem v bodě p\ G P. Po průchodu zametači přímky bodem p se oblouk a rozdělí na dva oblouky ct\ a a2 a mezi nimi vznikne v plážové linii nový oblouk (3, který je částí paraboly s ohniskem v bodě p.
OBR 9.6 Místní událost p
V průniku dvojice oblouků ct\ a (3 a dvojice (3 a a2 leží body hrany diagramu Voronoia, která odděluje oblast V(pi) od oblasti V(p). Této změně v plážové linii odpovídá následující změna ve stromě 7~:
OBR 9.7 Změna ve stromě T
Vnitřní uzly (pľ : p2), (p± : p) a (p : pi) stromu T popisují zlomové body plážové linie pomocí ohnisek příslušných parabol v pořadí zleva doprava tak, jak jsme to popsali výše. Po změně ve stromu T je potřeba provést jeho vyvážení.
Nyní uvažujme tři po sobě jdoucí oblouky a, (3 a 7 plážové linie. Nechť p±, p2 a P3 jsou postupně ohniska jim příslušejících parabol. Uvažujme kružnici opsanou těmto třem bodům. Nazvěme s její střed a označme q nejspodnější bod této kružnice, tj. bod s minimální souřadnicí y. Jestliže bod q leží pod zametači přímkou /, nazýváme jej kruhovou událostí pro oblouk (3 (anglicky circle event).
Při průchodu přímky / tímto bodem má střed s kružnice opsané bodům p1? p2, p3 a q od těchto bodů stejnou vzdálenost jako od přímky /, leží tedy na všech třech obloucích a, (3 a 7 plážové linie. Při posunu zametači přímky / pod bod q, oblouk (3 mizí z plážové linie. Střed s kružnice opsané je vrcholem diagramu Voronoia, do kterého přicházejí hrany oddělující oblast V(pi) od V(p2), oblast V(p2) od V(ps) a oblast V(pi) od V(ps).
OBR 9.8 Průchod zametači přímky kruhovou událostí q
OBR 9.9 Změna ve stromě T při průchodu kruhovou událostí
Lemma 9.4. Oblouk paraboly mizí z plážové linie, právě když zametači přímka prochází přes jeho kruhovou událost.
4
9.3. Algoritmus. Začátek algoritmu odpovídá poloze zametači přímky / nad všemi body. Strom T je prázdný a fronta událostí Q obsahuje všechny body z množiny P (místní události) uspořádané lexikograficky shora dolů a zleva doprava. Při průchodu zametači přímky událostí provádíme v závislosti na tom, zda se jedná o místní nebo kruhovou událost, následující akce:
• přidáme oblouk do stromu T a hrany do dvojitě souvislého seznamu pro V-diagram,
• vezmeme oblouk ze stromu 7~, přidáme hranu a vrchol do V-diagramu,
• z fronty Q odebereme událost, kterou jsme právě prošli, případně kruhové události, které odpovídaly trojicím po sobě jdoucích oblouků, které po průchodu danou událostí zmizely. Mění se totiž pořadí oblouků a aktuální kruhové události se počítají ze tří aktuálních po sobě jdoucích oblouků. Nově vzniklé kruhové události zařadíme do fronty.
Tento postup provádíme tak dlouho, až je fronta Q prázdná. Strom T však prázdný nebude. Jeho aktuální vnitřní uzly určují hrany V-diagramu, které jsou polopřímkami (případně přímkami). To umožní najít pravoúhelník R, ve kterém leží všechny body množiny P, všechny vrcholy V-diagramu a zlomové body odpovídající těmto zbývajícím vnitřním uzlům stromu T.
Průběh algoritmu v nejjednodušší možné situaci množiny tří bodů je demonstrován následující animací.
ANIMACE
Přesný popis algoritmu je zachycen v následujících pseudokódech. PSEUDOKÓD 30 z pseudo.pdf PSEUDOKÓD 31 z pseudo.pdf PSEUDOKÓD 32 z pseudo.pdf
9.4. Časová náročnost. Nechť množina P, pro kterou provádíme algoritmus, má n bodů. Po průchodu první místní událostí ve frontě bude plážová linie tvořena jedinou parabolou. Při průchodu dalšími místními událostmi přibudou vždy maximálně dva oblouky parabol. Proto celkový počet oblouků, které se někdy vyskytnou v plážové linii nepřevýší 2n — 1. V binárním vyváženém stromě s maximálně 2n — 1 listy trvají operace přidání dvou listů a ubrání jednoho listu a případné vyvážení stromu čas
0(log(2n- 1)) = O(logn).
Protože každý oblouk v plážové linii jednou vznikne a nejvýše jednou zanikne, bude realizovaných událostí 0(2n — 1) = 0(n). V každé události provedeme konečný shora omezený počet kroků, které trvají konečný čas nebo čas maximálně O(logn). Tím jsme dokázali:
Věta 9.5. Časová náročnost algoritmu zametači přímky pro vytvořeni V-áiagramu množiny n boáů je 0(n log n).
5
Implementace algoritmu pomocí Matlabu je provedena v bakalářské práci Jany Tomšů O algoritmech počítačové geometrie dostupné na
https://is.muni.cz/auth/th/175345/prif_b/