Masarykova univerzita Fakulta informatiky
Překryvy map
Diplomová práce Dominik Janků
Brno, jaro 2014
Prohlášení
Prohlašuji, že tato diplomová práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj.
Vedoucí práce: doc. RNDr. Martin Čadek, CSc.
i
Poděkování
Mé velké poděkování patří doc. RNDr. Martinu Čadkovi, CSc, za ochotu, trpělivost a cenné poznámky během vedení této diplomové práce.
Chtěl bych také poděkovat své přítelkyni za trpělivost, oporu a věcné poznámky k jazykové části textu.
iii
Shrnutí
Diplomová práce představuje dva rovinné geometrické algoritmy, jmenovitě Bentlyův-Ottmanův algoritmus pro výpočet průsečíků úseček a algoritmus pro výpočet překryvu map. Kromě teoretického výkladu nabízí kompletní pseudokódy, které mohou být využity při jejich implementaci. Ta je ostatně součástí práce v podobě ukázkových programů s otevřeným zdrojovým kódem.
v
Klíčová slova
průsečíky úseček, algoritmus zametači přímky, Bentley-Ottman, pře-kryvy map, rovinná podrozdělení, pseudokód, Python
vii
Obsah
Úvod................................ 3
1 Průsečíky úseček......................... 5
1.1 Výpočet průsečíku dvou úseček.............. 5
1.2 Triviální algoritmus..................... 6
1.3 Bentleyův-Ottmanův algoritmus............. 7
1.4 Lexikografické řazení bodů ................ 7
1.5 Použité datové struktury.................. 7
1.5.1 Prioritní fronta Q.................. 8
1.5.2 Vyvážený binární strom T............. 8
1.6 Množiny U (p), C (p) a L (p)................. 10
1.7 Inicializace a běh algoritmu................ 10
1.8 Zpracování události..................... 11
1.9 Hledání nových průsečíků................. 13
1.10 Výstup............................ 14
2 Překry vy map........................... 15
2.1 Základní pojmy....................... 16
2.2 Dvojitě souvislý seznam.................. 17
2.2.1 Struktura dvojitě souvislého seznamu...... 18
2.2.2 Příklad zápisu dat................. 19
2.3 Algoritmus.......................... 19
2.3.1 Spojení seznamů.................. 20
2.3.2 Výpočet průsečíků................. 23
Obsluha události.................. 25
Obsluha události - eliminace úseček C(p)   ... 25
Obsluha události - propojení hran........ 28
2.3.3 Zpracování oblastí................. 31
Hranice oblasti................... 31
Určení vnější a vnitřní hranice.......... 32
Zjištění cyklů.................... 33
Komponenty souvislosti ............. 33
1
Algoritmické vytvoření komponent souvislosti 35
Určení původních názvů oblastí......... 37
Vytvoření záznamů ve faces(D)......... 40
2.4 Úplný algoritmus...................... 41
2.5 Časová složitost překryvu map.............. 41
2.6 Booleovy operace nad polygony ............. 41
3   Ukázkové programy......... .............. 43
3.1 Použité technologie..................... 43
3.1.1 Python........................ 43
3.1.2 Blist.......................... 44
Instalace....................... 44
3.1.3 Tkinter........................ 44
3.1.4 Pomocné třídy ................... 45
3.2 Program Sweepline..................... 45
3.2.1 Ovládání programu ................ 46
3.2.2 Významy barev bodů ............... 46
3.3 Program MapOverlay ................... 46
3.3.1 Ovládání programu ................ 47
3.3.2 Struktura souboru s mapou............ 47
Závěr................................ 49
A Obsah přiloženého CD ..................... 55
2
Úvod
Geometrické algoritmy se vždy řadily k nejpřitažlivějším částem informatiky Snad proto, že se s jejich aplikací setkáváme takřka na každém kroku. Není proto příliš velkým překvapením, že jsem si jednu z jejich částí vybral jako téma této diplomové práce.
Problematika výpočtu průsečíků a překryvu map patří k těm nej-základnějším. Setkáváme se s nimi například v grafických, geografických, nebo konstruktérských aplikacích, které by bez efektivních algoritmů nemohly pracovat. Přestože v dnešní době disponujeme řádově většími výpočetními výkony, než tomu bylo v minulosti, pořád zde existuje poptávka po algoritmech, které řeší daný problém v co nejmenší časové složitosti.
Algoritmy prezentované v této práci patří mezi ně. První z nich, Bentleyův-Ottmanův algoritmus [2] slouží k výpočtu průsečíků úseček, přičemž zohledňuje jejich počet ve své časové složitosti. Totéž činí i algoritmus překryvu map [3], který je popsán následovně.
Konečným cílem této práce je naprogramování aplikací, které by oba výše uvedené algoritmy implementovaly a umožnily uživateli jejich názornou ukázku.
Způsob, jakým algoritmy pracují, je popsán zvlášť v jednotlivých kapitolách. Teoretický výklad je navíc doplněn o pseudokódy, které čtenáři mohou pomoci s pochopením a případnou implementací algoritmů. Členění kapitol je následující.
První kapitola otevírá problematiku průsečíků úseček a to rekapitulací základních poznatků z oboru analytické geometrie. Ihned poté následuje představení Bentley-Ottmanova algoritmu, včetně příslušných pseudokódů.
Druhá kapitola obsahuje stěžejní část této práce - průniky map. Úvodem čtenáře seznamuje se základními pojmy a pokračuje představením dvojitě souvislého seznamu, jakožto vhodné datové struktury pro uchování map. Jednotlivé kroky algoritmu jsou podrobně
3
popsány a stejně jako v kapitole první, ani zde nechybí doprovodné pseudokódy
Třetí kapitola představuje naprogramované aplikace pro demonstraci algoritmů. Uvedeny jsou použité technologie a způsob ovládání aplikací, které zároveň slouží jako uživatelská příručka.
Poslední kapitola přináší rekapitulaci dosažených výsledků.
4
Kapitola 1
Průsečíky úseček
Pro řešení úlohy překryvu map potřebujeme zvládnout vypočet průsečíků úseček. V této kapitole budeme pracovat s množinou úseček {si, s2, ■ ■ ■, sn}, kde jednotlivé úsečky s« jsou určeny koncovými body vť.
1.1   Výpočet průsečíku dvou úseček
Máme dány dvě úsečky: úsečku s, určenou body (px,py), (qx,qy) a úsečku s' určenou body (p'x,p'y), (q'x, q'y)-Našim úkolem je nalézt jejich průsečík.
Pro tento účel využijeme parametrické vyjádření přímky s v rovině:
x = Px + tU1}
u= (qx - px,qy - py), (1.1)
y = py + tu2,
kde t je tzv. parametr. Pokud platí, zet e [0; 1], pak bod (x, y) leží na úsečce s.
K nalezení průsečíku úseček s, s' odvodíme soustavu rovnic, kterou získáme z parametrického vyjádření (1.1):
Px + tiu1=p'x + t2v1, u = [qx — px, qy — py),
Py + t1u2=Py + t2V2, v = (qx-px,qy-py).
Ze soustavy rovnic (1.2) vypočteme parametr íx a t2 následovně:
.    _ VÁPy ~Py) +MPx -Px) ,    _ MPy ~ Py) + MPx ~ Px)
íl — -, í2 — -;-•
UiV2 - U2Vi UiV2 + U2Vi
Pokud nám vyjde nulový jmenovatel, znamená to, že jsou úsečky navzájem rovnoběžné (mají stejný směrový vektor) a průsečík buď neexistuje, nebo jich existuje nekonečně mnoho.
5
1. Průsečíky úseček
Je-li jmenovatel různý od nuly, nejsou úsečky rovnoběžné a průsečík existuje, právě když í1; t2 G [0,1]. V tomto případě má průsečík souřadnice
Obecně si však nevystačíme s počítáním průsečíku pouze dvou úseček. Ve většině případů potřebujeme spočítat průsečíky n úseček, kde n může být libovolně velké (konečné) číslo. Z tohoto důvodu vznikly nejrůznější algoritmy, které tuto úlohu řeší [2, 4].
1.2   Triviální algoritmus
Průsečíky hledáme tak, že vybereme libovolnou úsečku s a testujeme ji na průsečík s ostatními úsečkami. Otestované dvojice úseček si označíme a pokračujeme dále. Celkem tedy potřebujeme (™) testů, což odpovídá časové složitosti 0(n2).
Zde je třeba říct, že lepší algoritmus obecně neexistuje, neboť vždy může existovat až (™) průsečíků a ty musíme označit. V praxi se ale nestává příliš často, že bychom jich měli tak mnoho.
Z tohoto důvodu se hledala řešení, která by počet průsečíků zohlednila při výpočtu. Jedním z nich je Bentleyův-Ottmanův algoritmus, o kterém pojednává následující část textu.
Obrázek 1.1: Průsečíky úseček
6
1. Průsečíky úseček
1.3   Bentleyův-Ottmanův algoritmus
Bentleyův-Ottmanův algoritmus patří do rodiny algoritmů pracujících s ideou tzv. zametači přímky [2] - myšlené horizontální přímky, která se zastavuje v tzv. událostech. Tyto události jsou procházeny odshora dolů, zleva doprava a vše co je nad nimi (a vlevo na přímce od události) je pokládáno za vyřešené.
Algoritmus dosahuje časové složitosti 0((n + k)\ogn), kde k je počet průsečíků a n je počet úseček (viz [3, 9] pro důkaz).
1.4   Lexikografické řazení bodů
Definujeme následující lexikografické uspořádání bodů v rovině:
Jak už je v počítačové grafice zvykem, y-souřadnice roste na zobrazovacím zařízení odshora dolů a my se této konvence budeme držet.
Pokaždé, když budeme hovořit o horním nebo dolním bodu úsečky, máme tím na mysli lexikograficky menší nebo větší bod.
1.5   Použité datové struktury
Algoritmus využívá ke své činnosti dvě datové struktury: prioritní frontu událostí Q a vyvážený binární strom T [3]. Obě si rozebereme podrobněji.
(1.3)
7
1. Průsečíky úseček
1.5.1 Prioritní fronta Q
Do prioritní fronty [8] ukládáme doposud nezpracované události, což jsou význačné body, ve kterých se algoritmus zastavuje. Události jsou ve frontě řazeny lexikograficky (proto prioritní) dle uspořádání 1.3. Na začátku fronty se proto nachází nejmenší událost.
Vložení nové události do fronty musí splňovat časovou složitost O (log n). Ve stejné složitosti probíhá také ověření, zda-li se již daná událost ve frontě nenachází. Logaritmické složitosti můžeme dosáhnout využitím binárního vyhledávání (půlení intervalu).
Výběr nejmenší události ke zpracování musí probíhat v čase 0(1).
1.5.2 Vyvážený binární strom T
Vyvážený binární strom [8] T uchovává ve svých listech aktuální pořadí úseček, které protíná zametači přímka í. Algoritmus tuto informaci využívá při testování průsečíků, což bude podrobněji rozebráno v sekci 1.9.
Ve vnitřních uzlech stromu se pak nachází hodnota nejpravějšího listu levého podstromu. Ukázku stromu můžeme pozorovat na obrázku 1.3.
Obrázek 1.3: Úsečky protnuté í a odpovídající strom T
Může být trochu nezvyklé uchovávat ve stromě úsečky namísto čísel. Pokud ale dokážeme určit, která z úseček je „menší" (myšleno více vlevo) a která „větší" (myšleno více vpravo) je možné použít i takové uspořádání.
Abychom toho byli schopni, předpokládejme, že bod p je právě zpracovávaná událost. Zametači přímka l splňuje rovnici y = py (prochází bodem p). Dále předpokládejme existenci libovolné úsečky
8
1. Průsečíky úseček
s, která je určena body {xi,yi) a (x2, y2), přičemž platí, že
< P < (x2,y2)
dle lexikografického uspořádání 1.3. Definujeme funkci
(px jinak,
která vrací rr-souřadnici průsečíku úsečky s se zametači přímkou í. Pokud je úsečka horizontálně orientovaná, použije se rr-souřadnice události p.
Dále definujeme funkci
(1.4)
V?(s)
X2 — X\
(1.5)
^2 - xx)2 + (y2 - í/i)2
která je rovna kosinu úhlu úsečky s svíraného s osou x. Ten budeme potřebovat v situacích, kdy prochází bodem p více úseček zároveň (viz obrázek č. 1.4). Obdržíme totiž více stejných hodnot což ke korektnímu rozhodnutí o pořadí nebude stačit. Porovnání úhlů nám tuto možnost nabízí.
P
Sl
		\s2
/s4	S3	
		
Obrázek 1.4: Více úseček prochází událostí p
Nyní již známe vše potřebné k tomu, abychom mohli definovat ostré uspořádání nad libovolnými úsečkami s, t ve stromě T:
s<t^ t(s) < m v   = m a <p(S) < <p(t)). (i.6)
Nemožnost rozhodnout, která úsečka je více nalevo, nebo více napravo znamená chybu na vstupu (úsečky se překrývají). Pro jednoduchost tedy předpokládejme, že se úsečky na vstupu překrývat nebudou.
9
1. Průsečíky úseček
Obrázek 1.5: Přidání úsečky s4 do stromu T dle £(sj) 1.6   Množiny £/(p), C(p) a L(p)
V následujícím textu se setkáme s třemi typy množin. Každá z nich je podmnožinou úseček S, které algoritmus získá na svém vstupu. Jejich význam je následující:
• U(p) - množina úseček, jejichž horním bodem je p,
• C(p) - množina úseček, jejichž vnitřním bodem je p,
• L(p) - množina úseček, jejichž dolním bodem je p.
HP) = M
cíp) = M
U (p) = {s3,s4}
Obrázek 1.6: Rozdělení úseček do množin L(p), C(p) a U (p)
Množiny U (p) a L (p) konstruujeme právě jednou při inicializaci algoritmu (viz sekce 1.7). Množiny C(p) konstruujeme v jeho průběhu a to při detekci průsečíků (viz sekce 1.9).
1.7   Inicializace a běh algoritmu
Algoritmus 1 (doplněný z [3]) nejprve inicializuje prázdnou frontu událostí Q a vyvážený binární strom T (ř. 1-2).
10
1. Průsečíky úseček
Algoritmus 1: SWEEPLlNE (S)
Input: Množina úseček S. Output: Průsečíky úseček.
Inicializujeme prázdnou prioritní frontu událostí Q. Inicializujeme prázdný vyvážený binární strom T. f or Si E S do
pu «— lexikograficky horní bod úsečky s« Pi «— lexikograficky dolní bod úsečky Sj Přidáme úsečku s« do množin U(pu) a L(pi). Přidáme body pu a pi do fronty Q. end
while \Q\ > 0 do
Vybereme z fronty Q událost p. HandleEventPoint(p) end
Poté následuje průchod jednotlivých úseček ze vstupní množiny (ř. 3-8), při kterém provádíme následující úkony:
1. konstruujeme množiny úseček U (p), L (p) pro pozdější použití,
2. přidáváme koncové body úseček do fronty událostí Q.
Posledním krokem je výběr nezpracované události ze začátku fronty Q (i. 9-12) a její zpracování algoritmem č. 2. Tak činíme do doby, než bude fronta událostí prázdná.
1.8   Zpracování události
Stěžejní částí Bentley-Ottmanova algoritmu je zpracování události p algoritmem č. 2 (vychází z [3]). Na jeho počátku zpřístupníme množiny U(p), C(p) a L(p). V případě, že sjednocení množin obsahuje více než jednu úsečku, označíme bod p jako jejich průsečík (ř. 4-6).
11
1. Průsečíky úseček
Algoritmus 2: HandleEventPoint(p)
Input: Událost p.
U(p) «— úsečky jejichž horní bod je p L(p) «— úsečky jejichž dolní bod je p C(p)    úsečky jejichž vnitřním bodem je p if | U(p) U C(p) U L(p) | > 2 then
| Označíme bod p jako průsečík úseček U(p) U C(p) U L(p). end
Odebereme úsečky L(p) U C(p) ze stromu T. Vložíme úsečky U(p) U C (p) do stromu T. if U(p) U C{p) = 0 then
si ^— úsečka nalevo od bodu p ve stromě T sr ^— úsečka napravo od bodu p ve stromě T FlNDNEWEVENT(sř, sr/p) else
s' ^— nejlevější úsečka zU(p)VJ C(p) si ^— levý soused úsečky s' ve stromě T FINDNEWEVENT(s', Syp) s" ^— nejpravější úsečka zU(p)VJ C(p) sr ^— pravý soused úsečky s" ve stromě T FindNewEvent(s", sr/p) end
Práce se stromem T
Je velice důležité, abychom při manipulaci se stromem T (ř. 7-8) dodržovali následující pravidla:
1. při odebírání úseček se řídíme uspořádáním 1.6, které je platné pro předchozí událost,
2. naopak při vkládání je platné uspořádání podle zpracovávané události p.
Činíme tak proto, že úsečky C (p) mění v bodě p své pořadí. Strom ale o této změně nemůže „vědět" a tak v něm zůstává pořadí úseček platné z předchozí události. Abychom zajistili jejich správné prohození, odstraníme je a znovu vložíme (podle zmíněných pravidel).
12
1. Průsečíky úseček
Tímto způsobem udržujeme platné pořadí úseček, které je nezbytné pro nalezení nových průsečíků.
1.9   Hledání nových průsečíků
Posledním krokem algoritmu je hledání nových průsečíků. To probíhá v závislosti na tom, jestli je sjednocení U(p) U C (p) prázdné či nikoliv (alg. č. 2, ř. 9-20) [3]. Na obrázku 1.7 vidíme ilustraci obou situací. Je zřejmé, že pokud některá z úseček si, sr, s', s" neexistuje, nemá smysl hledat její průsečíky.
(a) U(p) U C (p) = 0 (b) U (p) U C (p) ^ 0
Obrázek 1.7: Hledání nových průsečíků
Algoritmus 3: FindNewEvent(s;, sr, p) Input: si, sr - testované úsečky, p - bod události
if 3 průsečík q úseček sř a sr A q > p then if q je vnitřním bodem si then
|   Přidáme úsečku si do množiny C (q). if q je vnitřním bodem sr then
|   Přidáme úsečku sr do množiny C (q). if q    Q then
|   Přidáme bod q do fronty Q.
end
Algoritmus č. 3 řeší testování na průsečík dvou úseček podle soustavy rovnic 1.2. Pokud je průsečík nalezen a leží pod bodem událostí p, pak se přistoupí k dalšímu zpracováni. Průsečíky nad událostí nás
13
1. Průsečíky úseček
již nezajímají (byly vypočítány a zpracovány v předchozím průběhu algoritmu).
1.10 Výstup
Výstupem algoritmu je seznam všech průsečíků včetně úseček, které jimi prochází.
Jak uvidíme v následující kapitole, může být výstup obohacen o další informace, které potřebujeme pro vyřešení specifického typu úlohy.
14
Kapitola 2
Překryvy map
Stěžejní částí této práce jsou překryvy map. Problém překryvu si můžeme jednoduše představit jako nalezení průsečíků a překrývajících se oblastí dvou zadaných map [3]. Příklad jednoduchého překryvu můžeme vidět na obrázku 2.1, oblasti jsou značeny písmenem /.
Obrázek 2.1: Překryv dvou jednoduchých map
Překryvy map se uplatňují v široké škále aplikací. Nejčastěji pak v geografických výpočtech, územním projektování atp.
Když se například rozhodne o stavbě nové pozemní komunikace, je potřeba učinit řadu nezbytných kroků. Jedním z nich je zjistit, přes které pozemky projektovaná stavba povede. Na základě těchto informací pak dojde k rozdělení pozemků v katastru nemovitostí a jsou zahájeny jejich výkupy. Jedná se o ukázkový příklad, u kterého je vhodné použít překryvy map - jedna mapa bude projektované území silnice a druhá mapa bude oblast, do které je silnice zasazena.
15
2. PŘEKRYVY map
2.1   Základní pojmy
V této části si osvětlíme některé základní pojmy, které budou nezbytné pro správné pochopení algoritmu.
Začněme ústředním pojmem celé kapitoly - mapou. Mapa není nic jiného, než rovinné podrozdělení. Tedy rovina, kterou rozdělují uzavřené lomené čáry složené z úseček na oblasti.
Na obrázku 2.2 můžeme vidět jednoduché rovinné podrozdělení, skládající se ze 4 oblastí, 10 vrcholů a 22 hran (hranu chápeme jako orientovanou úsečku). Rovinné podrozdělení značíme písmenem S.
V textu se dále setkáme s následujícími pojmy:
Vrchol je koncový bod hrany, budeme jej označovat jako v{ (vertex).
Hrana je orientovaná úsečka vycházející z vrcholu v i a končící ve vrcholu Vj. Značíme jako e^- (edge). Výchozí vrchol hrany v;t označujeme jako origin(eij).
Oblast je plocha vymezená právě jednou vnější hranicí a libovolným počtem hranic vnitřních. Označujeme f í (face).
Přilehlá oblast je oblast umístěna nalevo od hrany.
Obrázek 2.2: Příklad rovinného podrozdělení
16
2. PŘEKRYVY MAP
Dvojče hrany e, j je hrana s opačnou orientací od hrany e^. Dvojče hrany označujeme twin(ei:j).
Následník hrany ei:j je hrana e^k vycházející z koncového vrcholu hrany ei:j, která má stejnou přilehlou oblast jako ei:j. Označujeme next(e,ij).
Předchůdce hrany e,^ je hrana e,hj, která má svůj koncový vrchol totožný s počátečním vrcholem hrany e^k a navíc mají obě hrany stejnou přilehlou oblast. Označujeme prev{e^k).
2.2   Dvojitě souvislý seznam
Vhodnou datovou strukturou pro reprezentaci mapy je dvojitě souvislý seznam1. Tvoří jej tři tabulky záznamů (relace), z nichž každá zvlášť uchovává informace o vrcholech, hranách a oblastech [3].
K základním atributům jednotlivých tabulek (viz podsekce 2.2.1) můžeme libovolně přidávat další - doplňující informace. Když například sestavujeme mapu znečištění ovzduší, bude u každé oblasti uvedena také hodnota naměřené veličiny, atp.
Dvojitě souvislým je seznam nazýván proto, jelikož propojuje vrcholy s hranami a hrany s oblastmi.
Vrcholy Hrany Oblasti
V dalším textu budeme dvojitě souvislý seznam označovat písmenem D.
1.  V anglické literatuře se setkáme s názvem doubly-connected edge list (DCEL).
17
2. překryvy MAP
2.2.1 Struktura dvojitě souvislého seznamu
1. vrcholy (vertices)
• název vrcholu2
• souřadnice (IR x IR)
• ukazatel3 na libovolnou hranu vycházející z vrcholu
2. hrany (edges)
• název hrany
• ukazatel na vrchol, ze kterého hrana vychází
• ukazatel na dvojče hrany
• ukazatel na následníka hrany se stejnou přilehlou oblastí
• ukazatel na předchůdce hrany
• ukazatel na přilehlou oblast (oblast vlevo dle směru orientace)
3. oblasti (faces)
• název oblasti
• ukazatel na jednu hranu přilehlou z vnější hranice
• ukazatel na jednu hranu přilehlou pro každou komponentu vnitřní hranice
Názvy vrcholů, hran a oblastí mohou být libovolné4 - jsou určeny čistě pro naše potřeby a nemají vliv na strukturu dat. Tím rozhodujícím jsou totiž ukazatelé.
Ukazatel si můžeme představit jako adresu (nebo index), na které se poukazovaný záznam nachází. Nejedná se tedy o data samotná, ale jen o informaci, kde je nalezneme. Přístup k poukazovanému záznamu probíhá v konstantním čase 0(1).
2. Pro naše účely budeme vrcholy pojmenovávat podle jejich oznčení, tedy ví.
3. Ukazatel chápeme jako adresu konkrétní poukazované položky v seznamu, která je dostupná v čase 0(1). V programovacích jazycích jako je C, C++ se často implementuje pomocí operátoru *.
4. Názvy se dokonce mohou i shodovat, nejedná se tedy o tzv. primární klíče
18
2. PŘEKRYVY MAP
Pokud budeme chtít získat ostatní informace (jako například všechny hrany vedoucí z/do vrcholu), můžeme tak zpravidla učinit v lineárním čase 0(n) ku celkovému množství požadovaných dat.
2.2.2 Příklad zápisu dat
Na obrázku 2.3 máme uvedeno jednoduché rovinné podrozdělení. Pro názornost si jej převedeme do dvojitě souvislého seznamu. Pokud je v názvu sloupce tabulky uveden znak * znamená to, že se jedná o ukazatel na data, nikoliv data samotná.
Výsledek převodu vidíme v tabulkách 2.1, 2.2 a 2.3.
v5 e5i4 v4
v1 e2,i v2
Obrázek 2.3: Triviální rovinné podrozdělení
Název	Souřadnice	* Vycházející hrana
Vl	(0; 10)	ei,2
V2	(10; 10)	e2,3
v3	(15; 5)	e3,4
v4	(9;0)	e3,4
v5	(i;0)	e4,i
Tabulka 2.1: Vrcholy z obrázku 2.3
2.3 Algoritmus
Nyní již známe všechny potřebné informace k tomu, abychom si mohli rozebrat princip algoritmu překryvu map. Ten bude na svém
19
2. překryvy MAP
Název	*Vrchol	*Dvojče	*Násled.	*Předchůd.	*Oblast
ei,2	^i	e2,i	e2,4	e5,i	fi
e2,i	^2	ei,2	ei,5	e3,2	foo
e2,3	^2	e3,2	e3,4	e4,2	Í2
e3,2	^3	e2,3	e2,i	e4,3	foo
e3,4	^3	e4,3	e4,2	e2,3	Í2
e4,3	V4	e3,4	e3,2	e5,4	foo
e4,2	V4	e2,4	e2,3	e3,4	h
e2,4	V2	e4,2	e4,5	ei,2	fl
e4,5	V4	e5,4	e5,i	e2,4	fl
e5,4	v5	e4,5	e4,3	ei,5	foo
e5,i		ei,5	ei,2	e4,5	fl
ei,5	Vl	e5,i	e5,4	e2,i	foo
Tabulka 2.2: Hrany z obrázku 2.3
Název	*Hrana vnější hranice	* Hrany vnitřních hranic
foo	—	{el,5>
fl	ei,2	0
h	e2,3	0
Tabulka 2.3: Oblasti z obrázku 2.3
vstupu přijímat dvojitě souvislé seznamy Dlr D2, reprezentující rovinná podrozdělení S\ a S2. Jejich překryv budeme chtít vypočítat.
Výsledkem výpočtu je nové rovinné podrozdělení S, reprezentované dvojitě souvislým seznamem D.
2.3.1 Spojení seznamů
Prvním krokem algoritmu je spojení seznamů Di a D2 do jednoho seznamu D. Tuto operaci provádí algoritmus 4, DCELMerge(Di , D2).
Princip spočívá v postupném slučování hran a vrcholů do jediného seznamu D. Oblasti slučovat nebudeme, neboť je ještě nemáme vypočteny.
Označením všech vrcholů jako doposud nepřidaných (ř. 2) se vy-
20
2. PŘEKRYVY map
hneme situaci, kdy bychom přidávali do vertices(D) víc shodných vrcholů najednou.
Poté procházíme jednotlivé hrany prvního podrozdělení a postupně je přidáváme do edges(D). Na tomto místě je potřeba zmínit, že vzájemná propojenost ukazatelů v záznamu musí být zachována. Toho docílíme například tak, že nebudeme přidávat jednotlivé záznamy hran a vrcholů, ale jen ukazatele na ně. Nové vrcholy a hrany budeme přidávat až ve chvíli, kdy budeme počítat nové průsečíky (viz další části).
Spolu s hranami přidáváme i jejich výchozí vrcholy za podmínky, že se již v D nenachází (ř. 7-10, 18-20). Navíc si u hran poznamenáme číslo mapy, ze které pochází (ř. 4,13). Tuto informaci použijeme v dalších krocích algoritmu.
Obdobně postupujeme se záznamy původem z D2. Jediný rozdíl bude spočívat v tom, že ošetříme sitauce, kdy se již vrchol se shodnými souřadnicemi ve vertices(D) nachází. V takovém případě nastavíme u zpracovávané hrany ukazatel origin(e) na existující vrchol ve vertices(D) (ř 16-17).
Obrázek 2.4: Řešení shodných souřadnic u dvou vrcholů
Zmíněnou situaci ilustruje obrázek 2.4. Vrchol vi z vertices(Di) je souřadnicově shodný s vrcholem v2 z vertices(D2). Situaci rozhodneme ve prospěch vrcholu z prvního podrozdělení.
Abychom při kontrole existence vrcholu, prováděné na řádku 16, zachovali časovou složitost 0(n logn), můžeme si vytvořit pomocný binární vyhledávací strom. Uzly stromu uspořádáme dle souřadnic vrcholů. Vytvoření stromu má časovou složitost 0(n\ogn), vyhledání vrcholu v něm pak O(logn). Tímto způsobem můžeme zjistit, zda-li se již nějaký vrchol ve vertices(D) nenachází.
21
2. překryvy MAP
Algoritmus 4: DCELMerge (Dlř D2)
Input: Dvojitě souvislé seznamy Dlf D2
Output: Datově spojený dvojitě souvislý seznam D.
D    prázdný dvojitě souvislý seznam. Označíme všechny vrcholy v D\ a D2 jako nepřidané, for e G edges(Di) do source_map{e) 1 edges(D)     edges(D) U {e} f ace_label{e)     {label(/ace(e))} ■u origin(e) if ->is_added(v) then
vertices(D)     vertices(D) U {-u} is_added(v) Trae end end
for e G edges(D2) do source_map{e) 2 edges(D)     edges(D) U {e} f ace_label{e) {/a6e/(/ace(e))} ■u origin(e)
ií3 w E vertices (D) .coords (w) = coords{v) then |   origin(e) -u; else if ~^is_added{v) then
vertices(D)     vertices(D) U {-u} is_added{v) Trae end end
22
2. překryvy map
2.3.2 Výpočet průsečíků
Výpočet průsečíků z dvou různých podrozdělení je dalším krokem algoritmu. Za tímto účelem využijeme nám známý algoritmus zametači přímky, který pro naše účely upravíme. Výsledek je uveden v algoritmu 5 - OverlaySweepLine (D).
Algoritmus začíná převodem hran na úsečky, se kterými se nám bude lépe pracovat. Postup převodu je uveden na řádcích 1-10.
Začneme tím, že označíme všechny hrany z edges(D) jako nezpracované. Poté převádíme jednu (nezpracovanou) hranu po druhé a vytváříme z nich úsečky. Pamatujeme si přitom, ze které hrany úsečka vznikla a to díky ukazateli na ní. Abychom se však vyhnuli vytváření identických úseček, označíme rovněž její dvojče za zpracované. Nakonec získáváme množinu úseček S, se kterou můžeme dále pracovat5.
Následuje procházení jednotlivých úseček s e S, které se od původní verze příliš neliší. Jediným krokem navíc je uchovávání počtu úseček patřící k té, či oné mapě. Tuto informaci si budeme pamatovat u jednotlivých množin U (p) a L (p). Za tímto účelem definujme funkci (Tí(S), kde i je označení mapy a S je množina úseček. Pak a,i(S) vrací počet úseček v S s původem v mapě i. Tak například ai(U(p)) vrací počet úseček v U(p) s původem v mapě 1.
Tuto informaci bude užitečné znát při zpracování události algoritmem 6, jak ostatně uvidíme dále.
5. Při implementaci převodní procedury bychom mohli navíc uspořit výpočetní čas tím, že bychom konverzi prováděli přímo v cyklu na řádcích 13-19, nicméně asymptotická složitost by zůstala nezměněna - 0(n).
I
[
23
2. překryvy map
Algoritmus 5: OverlaySweepLine (D)
Input: Dvojitě souvislý seznam D. Output: D s vypočtenými průsečíky
Označíme všechny hrany edges(D) jako nezpracované.
for e G edges(D) do
if hrana e nebyla dosud zpracována then
s segment(e) edgejpointer(s) <r- e S ^SU{s}
Označíme twin(e) jako zpracovanou hranu, end end
li: Inicializujeme prázdnou prioritní frontu událostí Q. 12: Inicializujeme prázdný vyvážený binární strom T.
for Si E S do
pu «— lexikograficky horní bod úsečky s i Pi «— lexikograficky dolní bod úsečky Sj Přidáme úsečku s« do množin U(pu) a L(pi). Upravíme čítače původu úseček tak, aby funkce o-j vracela korektní hodnotu. Přidáme body pu a př do fronty Q. end
while \Q\ > Odo
Vybereme z fronty Q událost p. OverlayHandleEventPoint(p) end
24
2. překryvy map
Obsluha události
Obsluha události p doznala výraznějších změn oproti své původní verzi uvedené v algoritmu 2. Její podobu můžeme vidět v algoritmu 6 - OverlayHandleEventPoin(p).
Při obsluze události vycházíme z faktu, že nehledáme průsečíky úseček, které mají původ v téže mapě - ty již známe (jinak by mapa nebyla korektní). Hledáme pouze takové průsečíky, které mají původ v obou mapách současně. Když je takový průsečík nalezen, provedeme potřebné úpravy v D tak, aby oblast nad p byla zpracovaná.
Pro přehlednost si postup rozčleníme do tří částí:
1. eliminace úseček C (p) rozdělením na horní a dolní část,
2. propojení (nastavení předchůdců a následníků) hran směřujících z/do p,
3. hledání nových průsečíků pod p. Obsluha události - eliminace úseček C (p)
Při obsluze události p je nezbytné provést rozdělení všech úseček v množině C (p). Tento krok činíme proto, abychom vytvořili korektní dvojitě souvislý seznam. Každý vrchol v něm může být pouze začátkem nebo koncem hrany, nemůže ležet uvnitř ní.
s s
s'
Obrázek 2.5: Princip algoritmu SplitCpSegment(s, p)
25
2. překryvy map
Algoritmus 6: OverlayHandleEventPoint(p) Input: Událost p.
U (p) «— úsečky jejichž horní bod je p L (p) «— úsečky jejichž dolní bod je p C (p)    úsečky jejichž vnitřním bodem je p
for s e C (p) do
s' <- SplitCpSegment(s, p) L(p) <r- L(p) U {s} C (p) <- C (p) \ {s}
U (p) <r- U [p) U {s'}
end
si, sr <- ClockwiseConnectUpper(p)
left_segment(p) úsečka nejblíže vlevo od bodu p ve stromě T. th tr <- ClockwiseConnectLower(p)
if 3 si A3 ti then
DoCLOCKWISECONNECT(íř/ sup) DoCLOCKWISECONNECT(sr, tr/p) if 3 si A -i3 ti then
I   DoCLOCKWISECONNECT(sr, Sy p) if -i3 si A 3 ti then
j  DoClockwiseConnect(í;, tr/p)
if U (p) = 0 then
si «— úsečka nalevo od bodu p ve stromě T sr «— úsečka napravo od bodu p ve stromě T FindNewEvent(sč, sr/p) else
s' «— nej levější úsečka z U (p) si «— levý soused úsečky s' ve stromě T FindNewEvent(s', si, p) s" «— nejpravější úsečka z U (p) sr «— pravý soused úsečky s" ve stromě T FindNewEvent(s", sr/p) end
26
2. překryvy map
Rozdělení úseček provádí algoritmus 7, SplitCpSegment (s, p). Zároveň dochází k úpravě záznamů v D, přičemž na výstupu obdržíme nově vzniklou úsečku s'. Princip rozdělení úsečeky je ilustrován na obrázku 2.5.
Samotné rozdělení úsečky ale nestačí. Ještě je potřeba ji odebrat z množiny C(p) a zároveň přidat její rozdělenou horní část do množiny L(p). Spodní část úsečky (úsečka s') přidáme do množiny U (p). Pro postup viz algoritmus 6, ř. 6-8.
Výše popsané rozdělení aplikujeme postupně na všechny úsečky v C(p) a tím, že úsečky zároveň i odebíráme, nemusíme C (p) v dalších krocích algoritmu uvažovat - bude to vždy prázdná množina.
Algoritmus 7: SplitCpSegment (s, p)
Input: Událost p a úsečka s e C (p) Output: Nová úsečka s' a nové hrany v D
i: ei     hrana úsečky s, taková že origin^) < p.
2: e2 <r- twin(ei)
3: e[     nový záznam v edges(D)
4: origin(e[) p
5: twin(e[) ei
6: twin(ei) e[
7: next(e[)     next(02)
8: source_map{e'1) source_map(e\)
9: face_label(e[) face_label(e2)
10: e'2    nový záznam v edges(D)
íl: origin(e2) <r- p
12: twin(e2) e2
13: twin(e2) <r- e'2
14: nexí(e2) nerrt(ei)
15: source_map(e2) <r- source_map(e2)
16: face_label(e2) face_label(ei)
17: return úsečka s' tvořená z hran e2, e'2
27
2. překryvy map
Obsluha události - propojení hran
Nyní přichází na řadu správné nastavení předchůdců a následníků hran úseček U (p) U L(p) směřujících do/z p.
Hrany propojujeme podle následujících pravidel:
• následník hrany směřující do p je hrana nejblíže po směru hodinových ručiček směřující od p,
• předchůdce hrany směřující od p je hrana nejblíže proti směru hodinových ručiček, směřující do p.
Jelikož nemáme k dispozici všechny úsečky seřazené po/proti směru hodinových ručiček, využijeme strom T. Z něj tuto informaci lze vyčíst, ale bude nezbytné rozdělit si problém na dvě části: horní a dolní, jak můžeme vidět na obrázcích 2.6 a 2.7.
Obrázek 2.6: Zpracování horní části - úsečky L{p)
Obrázek 2.7: Zpracování dolní části - úsečky U(p)
Princip algoritmu 8, ClockwiseConnectUpper(p), popřípadě algoritmu 9, ClockwiseConnectLower(p), spočívá v propojení
28
2. překryvy map
vnitřních hran úseček. Ty postupně procházíme zprava doleva (potažmo zleva doprava) a propojujeme je pomocí jednoduchého algoritmu 10, DoClockwiseConnect(s, t, p).
Algoritmus 8: ClockwiseConnectUpper(p)
Input: Událost p a úsečky L(p),U(p).
Result: Propojení hran úseček z množiny L(p).
-. if | L(p) | > 0 A o-i(L(p) U U(p)) > 0 A a2(L(p) U U(p)) > 0 then :      si «— nejlevější úsečka z L(p) -.      sr «— nejpravější úsečka z L(p)
while s\ ý sr do
: s'r «— pravý soused úsečky s\ ve stromě T
■. DoClockwiseConnect(s;, s'r, p)
s\ <r- s'r
end : end
: Odebereme úsečky L(p) ze stromu T. -. return slr sr
Oba výše uvedené algoritmy 8 a 9 vrací na svém výstupu nejlevější a nejpravější úsečku zpracovávané části (pokud existují). Výstupní úsečky mohou být samozřejmě totožné: v případě, kdy existuje jen jedna úsečka v U (p) nebo v L(p).
Pokud je dolní část úseček prázdná (U(p) = 0), propojíme spolu pouze hrany nejlevější a nejpravější úsečky z L(p). Pokud je prázdná část horní (L(p) = 0), propojíme spolu pouze hrany nejlevější a nejpravější úsečky zU(p).
Propojování provádíme za předpokladu, že platí následující podmínka:
<ri(L(p) U U (p)) > 0 A a2(L(p) U U (p)) > 0.
Tedy, že existuje alespoň jedna úsečka z každé mapy. Tato podmínka je obsažena jak v algoritmu 8, tak v algoritmu 9. Oba navíc přidávají podmínku na neprázdnost zpracovávaných úseček.
Tímto způsobem se můžeme vyhnout zbytečnému propojování hran původem z téže mapy - je již hotové.
29
2. překryvy map
Algoritmus 9: ClockwiseConnectLower(p)
Input: Událost p a úsečky L(p),U(p).
Result: Propojení hran úseček z množiny U (p).
i: Vložíme úsečky U (p) do stromu T.
2: if I U (p) I > 0 A oi(L(p) U U (p)) > 0 A (T2{L[p) U f/(p)) > 0 then 3:      ti «— nejlevější úsečeka z f/(p) 4:      tr «— nejpravější úsečeka z U (p)
5: íj. tr
6:      while íj. 7^ ti do
7: ŕ{ «— levý soused úsečky ťr ve stromě T
8: DoClockwiseConnect(4, í;, p)
9: t; <- t;
ío: end
íi:      return í;, ír
12: end
Algoritmus 10: DoClockwiseConnect(s, t, p) Input: Událost p, která je společným koncovým bodem úseček s, t. Result: Nastaví předchůdce a následníka hran úseček s, t při události p.
i: ei     hrana úsečky s taková, že origin(ei) ^ p 2: e2    hrana úsečky t taková, že origin(e2) = p 3: next(ei) e2 4: prev(e2) <r- ei
30
2. PŘEKRYVY map
2.3.3 Zpracování oblastí
Nyní, když známe všechny průsečíky a máme správně propojeny hrany, můžeme přistoupit k určování oblastí nového podrozdělení. To budeme provádět ve třech krocích:
1. zjištění hranic oblastí,
2. sestavení speciálního grafu a nalezení jeho komponent souvislosti,
3. vytvoření odpovídajících záznamů ve faces(D). Hranice oblasti
Každá oblast podrozdělení je určena svou vnější hranicí a libovolným počtem hranic vnitřních. Hranici oblasti tvoří posloupnost hran ei, e2,en, en+1 = e\, přičemž platí, že hrana ei+1 je následníkem hrany e^. Takovou posloupnost hran budeme nazývat cyklem a označovat jako q. Platí, že počet vnějších hranic odpovídá počtu omezených oblastí. Jedna oblast je neomezená (bez vnější hranice). Pro ni můžeme vytvořit fiktivní vnější cyklus, který budeme označovat c^,.
Obrázek 2.8: Cykly podrozdělení
Na obrázku 2.8 můžeme vidět jednotlivé hranice oblastí v rovin-ném podrozdělení. Černě jsou znázorněny vnitřní hranice a modře jsou znázorněny vnější hranice oblastí. Tak například oblast j\ je vymezena vnější hranicí c2 a vnitřními hranicemi c3 a c5.
31
2. překryvy map
Určení vnější a vnitřní hranice
Typ hranice určíme podle úhlu, který svírají hrany procházející nej-levějším bodem cyklu (v případě, že jich existuje více, vezmeme nej-nižší bod). Pokud je tento úhel menší než 180°, jedná se o vnější hranici oblasti. V opačném případě se jedná o vnitřní hranici oblasti.
Algoritmy 11 a 12 nám umožňují zjitit typ hranice podle svíraného úhlu (zjišťujeme výpočtem znaménka determinantu vhodné matice 2 x 2).
Algoritmus 11: inner (c)
Input: Cyklus c s určeným nejlevějším bodem a hranou z něj
vycházející leftmost_edge(c). Output: Pravda, pokud cyklus tvoří vnitřní hranici oblasti.
: e leftmost_edge(c)
: p origin(prev(e))
: q origin(e)
: r ^— origin(next(e))
: return (qx - px) * (py - ry) - (rx - px) * (py - qy) < 0
Algoritmus 12: outer (c) Input: Cyklus c
Output: Pravda, pokud je cyklus na vstupu vnější hranicí oblasti, jinak nepravda. : return -Jnner(c)
32
2. překryvy map
Zjištění cyklů
Seznam všech cyklů v rovinném podrozdělení vrací na svém výstupu algoritmus 13, OverlayCycles(-D). Ten navíc ke každému cyklu ukládá informaci o jeho nejlevějším bodě - leftmost_vertex(c) a hraně z něj vycházející - leftmost_edge(c).
Princip algoritmu spočívá v postupném procházení nezpracovaných hran z edges(D). Z jedné nezpracované hrany postupně procházíme její následníky až narazíme na hranu, u které jsme začali. Tím algoritmus projde celý cyklus. Navštívené hrany přitom označíme jako zpracované a poznamenáme si u nich také cyklus, do kterého patří (například ukazatelem).
Navíc je vhodné (uvidíme později) poznamenat si názvy přilehlých oblastí hran, které cyklus tvoří (ř. 5, 24-25).
Každý cyklus je jednoznačně určen svým indexem - index(c).
Komponenty souvislosti
Jak už bylo řečeno, každá oblast podrozdělení má svou vnější hranici a libovolný počet hranic vnitřních. Abychom mohli vložit záznamy o oblastech do faces(D) je nezbytné určit, které hranice vymezují plochu jedné oblasti.
Řešení problému spočívá v nalezení komponent souvislosti v následujícím grafu. Uzly grafu tvoří jednotlivé cykly, hrany pak vytváříme následovně:
0 0
Obrázek 2.9: Komponenty souvislosti z obrázku 2.8
33
2. překryvy map
Algoritmus 13: OverlayCycles (D)
Input: Dvojitě souvislý seznam D
Output: Seznam cyklů vnitřních a vnějších hranic C s nejlevějším bodem a hranou.
Označíme všechny hrany v edges(D) jako nezpracované. C    prázdný seznam cyklů indexovaných od nuly.
«— uměle vytvořený cyklus vnější hranice (oblast /oo) index (c^) 0
face_labels(Coo) <- {(1, "/«,"), (2, "/«,")} Přidáme cyklus Coo do seznamu C.
Í <r- 1
for e G nezpracovaná hrana z edges(D) do c «— nový cyklus
index(c) i face_labels(c) 0 ■u origin(e) leftmost _vertex{c) <r- -u leftmost _edge{c) <r- e e' «— e repeat
cycle{e') c v' origin{e')
if ?4 < ^ V     = ^ A v'y < vy) then
leftmost_vertex{c) v' leftmost_edge{c) e'
end
/     {(source_map(e), face_label(e))} face_labels(c)     face_labels(c) U / e' next{e')
Označíme hranu e' jako zpracovanou, until e^e'
Přidáme cyklus c do seznamu C pod indexem i.
i = i + \
end
return C
34
2. PŘEKRYVY MAP
Procházíme jeden vnitřní cyklus za druhým a hledáme k němu jeho levého souseda. To děláme tak, že vezmeme nejlevější bod cyklu (pokud je jich více, rozhoduje ten nejníže položený) a vedeme z něj myšlenou horizontální čáru vlevo. Tam, kde se čára jako první protne s jinou úsečkou dostáváme opačně orientované hrany dvou cyklů. Vybereme z něj ten, který má shodnou přilehlou oblast s právě zpracovávaným cyklem. Tyto cykly v grafu spojíme hranou [3].
Nalézt sousední cyklus vlevo není obtížné, pokud si u zpracovávané události pamatujeme úsečku nejblíže nalevo od ní (tak činíme v algoritmu 6 na ř. 11).
Po vytvoření všech takových hran daného grafu dostáváme komponenty souvislosti, které představují jednotlivé oblasti. Uzly komponenty tvoří vnitřní a vnější hranice dané oblasti.
Když bychom se vrátili k podrozdělení z obrázku 2.8, pak by sestavené komponenty souvislosti byly shodné s těmi, které jsou uvedeny na obrázku 2.9. Navíc si můžeme u podrozdělení povšimnout přerušovaných horizontálních čar, které symbolizují propojování sousedních cyklů. Vidíme tak, že levým sousedem cyklu c6 je cyklus c3. Cykly vnější hranice jsou u komponent znázorněny zvýrazněným kruhem.
Algoritmické vytvoření komponent souvislosti
Algoritmus 14 představuje jeden z možných způsobů jak komponenty souvislosti vytvářet.
Prvním krokem je vytvoření prázdného seznamu komponent. Do něj budeme postupně ukládat jednotlivé komponenty. Dále definujeme funkci component (c) na cyklu c, která vrací komponentu cyklu. Tedy komponentu, ve které se cyklus nachází.
Následuje postupné zpracovávání cyklů. Pokud má cyklus přiřazenou komponentu souvislosti, neděláme nic. V opačném případě provedeme následující kroky.
Pokud cyklus tvoří vnější hranici oblasti, pak k němu vytvoříme zcela novou komponentu souvislosti (ř. 5) a uložíme k ní potřebné informace (ř. 6-8).
35
2. překryvy map
Algoritmus 14: OverlayComponents (C)
Input: Seznam cyklů C
Output: Seznam komponent souvislosti G
Q    prázdný seznam komponent souvislosti
foreach c e C do
if -i3 component(c) then if Outer (c) then
p    nová komponenta v £/
outer(g) c inners(g) 0 component(c) g else
C' = {c} repeat
c'    cyklus nalevo od cyklu c if -i3 c' then
|   d ^— Cqo (index 0 v seznamu cyklů) if outer(c') A -i3 component (d) then I  Totéž, co na řádcích 6-9, ale s cyklem d. end
if inner(c') A -i3 component(d) then I CVC'UM until -i3 component (d) g     component (d) foreach d £ C' do component(d) <r- g inners(g)     inners(g) U {c'} end end
end
36
2. PŘEKRYVY map
Pokud cyklus představuje vnitřní hranici oblasti, je situace složitější. Musíme k němu totiž nalézt související cyklus (cyklus nalevo od nejlevějšího bodu), který má buďto nastavenou komponentu souvislosti nebo se jedná o vnější hranici oblasti, ke které komponentu souvislosti vytvoříme (ř. 15-17).
Jak můžeme vidět, algoritmus nepostupuje přesně tak, jak bylo uvedeno v myšlence sestavování komponent souvislosti, nicméně jeho výstup je korektní. Navíc, a to je důležitější, pracuje v časové složitosti 0(n) vzhledem k n-cyklům na vstupu. Nezvyšuje tedy celkovou časovou složitost překryvu map (viz sekce 2.5).
Určení původních názvů oblastí
Ještě předtím, než provedeme převod komponent souvislosti do tabulky oblastí faces(D), určíme jejich původní názvy.
Platí, že každá nová oblast (reprezentovaná komponentou souvislosti) pochází právě z jedné oblasti první mapy a právě z jedné oblasti druhé mapy. Touto oblastí může být samozřejmě i neomezená oblast foo.
V zásadě existují dva možné způsoby, jak původní názvy zjistit.
První způsob spočívá v tom, že projdeme všechny cykly, ze kterých je komponenta souvislosti tvořena. Každý z cyklů totiž obsahuje informaci o původních přilehlých oblastech hran, které jsme získali v algoritmu 13.
Obrázek 2.10: Získání názvu oblastí z cyklů komponenty
V levé části obrázku 2.10 vidíme cyklus, který je tvořen ze tří hran původem z první mapy (vyznačeny černě) a jedna hrana původem z mapy druhé (vyznačena červeně). V pravé části pak vidíme vnější
37
2. překryvy map
cyklus původem z první mapy a vnitřní cyklus původem z druhé mapy
Názvy oblastí poznamenané u cyklů jsou uloženy jako množina uspořádaných dvojic (i, label), kde i je číslo původní mapy a label je název původní oblasti. Je přitom zřejmé, že množina názvů oblastí může mít maximálně dva prvky. Pokud jich je méně (jeden), musíme zjistit původní oblast z chybějící mapy. To provedeme druhým způsobem.
Ten spočívá v tom, že budeme postupně procházet vnější hranice nadřazených komponent, dokud název oblasti chybějící mapy nezískáme. Nadřazenou komponentou myslíme takovou komponentu, ve které se nachází cyklus opačný od cyklu vnější hranice aktuální komponenty.
• -• 9i 92
Obrázek 2.11: Překryv a komponenty souvislosti
Uveďme si to na příkladu z obrázku 2.11. Máme zde komponentu g2l která je jednobarevná (neobsahuje hrany původem z různých map). Přesto leží v oblasti z druhé mapy a sice oblasti fa. Vezmeme proto cyklus opačný (c2) k cyklu vnější hranice (c3) a zjistíme, ve které komponentě se nachází - component(c2) = g±. Z vnějšího cyklu komponenty gi získáváme chybějící původní oblast fa.
Algoritmus 15, FindFaceLabels (G), vykonává výše uvedený postup.
38
2. překryvy map
Algoritmus 15: FindFaceLabels (G)
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15:
16: 17: 18: 19:
Input: Seznam komponent souvislosti G
Result: Nastavené popisky oblastí u komponent souvislosti G
for g G G do
L <r- 0
for c G {outer(g)} U inner s{g) do L     IU face_labels(c) if | L | = 2 then |  Ukonči procházení cyklů.
end
if I L I < 2 then
g' <- g
repeat
c     outer (g')
e twin(leftmost_edge(c)) g' <r- component (cycle(e)) c'     outer(g')
Přidáme do L jen takovou uspořádanou dvojici z f ace_labels(d), která pochází z chybějící mapy. until | L | < 2 end
face_labels(g) L
end
39
2. překryvy map
Vytvoření záznamů ve faces(D)
Nyní zbývá jediné: vytvořit odpovídající záznamy oblastí v tabulce faces(D). Ty vytvoříme podle obdržených komponent souvislosti následovně:
Nejprve vytvoříme nový záznam oblasti ve faces(D). Nastavíme vnější a vnitřní hranice podle komponenty souvislosti a stejně tak nastavíme nový název oblasti.
Poté projdeme všechny hrany hraničních cyklů a nastavíme ukazatel na novou přilehlou oblast.
Pseudokód je uveden v algoritmu 16, OverlayFaces(G).
Algoritmus 16: OverlayFaces (G)
Input: Seznam komponent souvislosti G Result: Spočítaná mapa překryvu D
for g E G do
f    nový záznam v tabulce f aces (D)
for c G inners(g) do J   E <r- E U {leftmost_edge(c)} end
inner _edges{f) E
outer_edge(f) leftmost_edge(outer(g)) label(f) face_labels(g)
foreach c G {outer(g)} U inners(g) do e leftmost_edge(c) e1 <r- e repeat
face(e') <- f e'     next (e') until e^e' end end
40
2. překryvy map
2.4   Úplný algoritmus
Spojením jednotlivých algoritmů do jednoho celku dostáváme úplnou verzi překryvu map.
Pseudokód je uveden v algoritmu 17, MapOverlay {Dlr D2).
Algoritmus 17: MapOverlay (Dlř D2)
Input: Dvojitě souvislé seznamy D\, D2. Output: Spočítaný překryv map D
D <r- DCELMerge (Dlf D2)
OverlaySweepLine (D)
C <r- OverlayCycles (D)
G <- OverlayComponents (c)
OverlayFaces (G)
return D
2.5 Časová složitost překryvu map
Časová složitost překryvu dvou map je odvozena od jejich komplexity (počtu záznamů v dvojitě souvislém seznamu).
Věta 2.5.1. Nechť S± je rovinné podrozdšlení s komplexitou ri\, S2 je rovinné podrozdělení s komplexitou n2 a nechť n = rii +n2. Pak překryv dvou podrozdšlení Si a S2 může být proveden v časové složitosti 0(n\ogn + k log n), kde k je komplexita překryvu.
Důkaz věty 2.5.1 je uveden v [3].
2.6 Booleovy operace nad polygony
Jednou z aplikací překryvu map jsou Booleovy operace nad dvěma polygony. Výsledkem operace je nové rovinné podrozdělení, které není nutně polygonem [3].
Předpokládejme existenci polygonu V\, který je zadán rovinným podrozdělením S\ jako oblast nesoucí označení V\. Obdobně předpokládejme existenci polygonu V2. Každému polygonu přiřadíme
41
2. překryvy MAP
rovinné podrozdělení se dvěma oblastmi, kde jedna oblast je polygon a druhá její doplněk.
Sjednocení polygonů V\ U V 2 provedeme tak, že v překryvu zahrneme pouze ty oblasti, které nesou označení buďto jen V\, nebo jen V2, popřípadě obojí.
Průnik dvou polygonů V\ n V2 provedeme tak, že v překryvu zahrneme pouze takové oblasti, které nesou označení jak V\, tak V2 zároveň.
Rozdíl dvou polygonů V\ \ V2 provedeme tak, že ve výsledném překryvu zahrneme pouze takové oblasti, které nesou označení V\, ale ne V2-
42
Kapitola 3
Ukázkové programy
Ukázkové programy tvoří nedílnou součást této diplomové práce. Jsou celkem dva:
1. Sweepline
2. MapOverlay
Oba programy implementují stejnojmenné algoritmy a umožňují jejich praktickou ukázku.
3.1   Použité technologie
Cílem bylo použít takové technologie, které by umožňovaly co nej-větší přenositelnost programů napříč operačními systémy. Neméně důležitým cílem byla také dobrá čitelnost zdrojového kódu.
Programovací jazyk Python nabízí obojí [7] a z tohoto důvodu byl vybrán pro implementaci programů. Využita byla jeho verze 2.7.
3.1.1 Python
Python patří mezi nejrozšířenější a nejoblíbenější skriptovací jazyky současnoti. Kombinuje imperativní, objektové a funkcionální prvky programování, přičemž zachovává výbornou čitelnost zdrojového kódu. Ta je mimo jiné dána i specifickou formou syntaxe, při které se jednotlivé bloky kódu tvoří jejich odsazením [7].
Další nespornou výhodou je rozsáhlá standardní knihovna, díky níž můžeme výrazným způsobem omezit využití knihoven třetích stran [1].
43
3. Ukázkové programy
Python je zpravidla standardní součástí všech linuxových distribucí. Nachází se rovněž na systémech Mac OS X. Výjimku tvoří operační systémy Windows, u kterých je nezbytné provést ruční instalaci.
3.1.2 Blist
Jedinou výjimku tvoří modul Blist, který není součástí standardní knihovny. Obsahuje datové struktury sortedlist a sortedset [6], které v programech využíváme.
V prvním případě se jedná o řazené pole dle zvoleného klíče (může být i funkce), přičemž operace na něm prováděné (vložení, smazání, vyhledání prvku) se realizují se shodnou časovou složitostí jako v binárním vyhledávacím stromě [6]. Ten je ostatně použit v implementaci pole.
Druhá zmiňovaná struktura je rovněž seřazeným polem, má však chování množin: nemůžeme mít v poli více než jeden unikátní objekt, nehledě na to, kolik jich do pole přidáme (tato operace neskončí chybou). Strukturu využíváme při práci s množinami U(p), C(p), L(p), které jsou uvedeny v předchozích kapitolách.
Instalace
Instalaci knihovny můžeme provést pomocí standardního nástroje Easy Install:
easy_install blist
nebo pomocí sofistikovanějšího správce balíčků PIP:
pip install blist
3.1.3 Tkinter
Grafické uživatelské rozhranní obou programů využívá standardní knihovny Tkinter1, která je součástí jazyka Python [1].
Tkinter umožňuje používání standardních ovladačích prvků jako jsou tlačítka, textová pole, popisky atp. (souhrne widgety) a jednak použití tzv. plátna (Canvas), na které můžeme vykreslovat geometrické útvary [5].
1. Jedná se o zkratku z anglického Tk interface. 44
3. Ukázkové programy
3.1.4 Pomocné třídy
Vzhledem k tomu, že v obou programech pracujeme s geometrickými objekty, je k dispozici pomocný modul geotools .py, který definuje třídu Point reprezentující rovinný bod a třídu Segment reprezentující úsečku.
Bod má navíc definové uspořádání dle lexikografického uspořádání 1.3. Úsečka pak obsahuje metodu na výpočet průsečíku s jinou úsečkou atp.
3.2   Program Sweepline
Algoritmus zametači přímky demonstruje program Sweepline. Jeho zdrojové kódy se nachází v souboru sweepline .py. Po spuštění souboru interpretem jazyka Python uvidíme obrazovku rozdělenou na dvě části: levou a pravou (viz obrázek 3.1).
Kroky algoritmu:
Zadání úseček Inicializace Obsluha události p
- zpracování U(p), C(p), L(p)
- aktualizace stromu
- hledání nových průsečíků Konec algoritmu
Dále     "| '    Vše )
Událost p=[422.0;120.0] L(P)=Í)
C(p)=B U(p)=(sO)
Pořadí úseček ve stromě T:
Ukončit program
Obrázek 3.1: Obrazovka programu Sweepline.
Levá část programu představuje plochu, na které se zobrazují úsečky a grafické operace s nimi. Vlevo dole můžeme vidět aktuální
45
3. Ukázkové programy
pozici kurzoru, vzhledem k hornímu pravému rohu okna. Vpravo od souřadnic se nachází informativní popis objektu, který je nejblíže ke kurzoru myši. Uživatel tak může pohodlně zjistit význam objektu, který jej zajímá.
V pravé části aplikace se nachází přehled jednotlivých kroků algoritmu a jednotlivé ovládací prvky.
3.2.1 Ovládání programu
Uživatel začíná tím, že zadává jednotlivé úsečky myší, na kterých chce algoritmus simulovat. Poté klikne na tlačítko Dále, které jej přesune na další krok algoritmu. Aktuální fáze algoritmu je zvýrazněna tučným řezem písma. Již prošlé kroky se zobrazují zelenou barvou.
Má-li jeden krok algoritmu více dílčích kroků, lze je všechny provést kliknutím na tlačítko Vše. Toho lze například využít u kroku Inicializace, při kterém se přidávají do fronty událostí krajní body úseček. Uživatel se tak nemusí proklikávat každou úsečkou zvlášť.
Program lze v kteroukoliv dobu ukončit kliknutím na tlačítko Ukončit program situované v pravém dolním rohu.
3.2.2 Významy barev bodů
V průběhu algoritmu se objevuje hned několik možných obarvení bodů. Zde je jejich význam:
• červený - nezpracovaný bod události, pocházející z koncového bodu úsečky,
• zelený - aktuálně zpracovávná událost,
• žlutý - objevený průsečík, doposud nezpracovaný,
• bílý - zpracovaný průsečík úseček.
3.3   Program MapOverlay
Algoritmus průniků map implementuje program MapOverlay. Jeho zdrojový kód se nachází v souboru mapoverlay . py.
46
3. Ukázkové programy
3.3.1 Ovládání programu
Ovládání programu se nikterak neliší od ovládáni toho předchozího. Výjimkou je zadávání vstupních dat, které se neděje ručně (z důvodu složitosti), ale načtením mapy již hotové ze souboru. Jeho formát je popsán v následující části.
3.3.2 Struktura souboru s mapou
Pro uchovávání mapy v souboru je využit značkovací jazyk XML. Struktura značek a jejich atributů je následující:
<map>
<vertices>
<vertex id="vl" x="10" y="15" edge="el" />
</vertices> <edges>
<edge id="el" origin="vl" twin="e5" next="e2" face="f0"/>
</edges> <faces>
<face id="fO">
<border type="inner" edge="el" />
</face>
<face id="fl">
<border type="outer" edge="e5" /> </face>
</faces> </map>
Všechna data se nachází uvnitř párové značky <map>. Nalezneme zde tři seznamy, které kopírují strukturu dvojitě souvislého seznamu: data o vrcholech <vertices>, hranách <edges> a oblastech <f aces>.
Atribut id je unikátním identifikačním pojmenováním objektu a nesmí se tedy stát, že by existovaly dva objekty se stejným iden-
47
3. Ukázkové programy
tifikátorem. Taková situace bude programem považována za chybu na vstupu.
Ostatní atributy vrcholů, hran nebo oblastí se řídí konvenčním pojmenováním, které v této práci běžně užíváme.
U záznamů oblastí rozlišujeme vnější a vnitřní hranici atributem type u značky <border>. Více než jedna vnější hranice u oblasti znamená chybu na vstupu.
Předdefinované mapy jsou k nalezení v adresáři map s na přiloženém CD a lze je použít jako vstup programu.
48
Zaver
Závěrem lze konstatovat, že cíle stanovené v úvodu této práce byly splněny
Přínosem v problematice výpočtu průsečíků úseček je definování způsobu práce s binárním stromem T. V literatuře [2, 3, 9] totiž není explicitně uvedeno, jakým způsobem se rozhodovat při procházení stromu vůči zadanému bodu. Jeden z možných způsobů je popsán v podsekci 1.5.2.
Největší objem původní práce však představuje kapitola druhá: prakticky všechny uvedené pseudokódy musely být nově vymyšleny. Mnohé postupy byly navíc oproti těm z [3] vylepšeny a zjednodušeny.
Naprogramování dvou ukázkových aplikací je neméně významným přínosem. Vzhledem k tomu, že programy prakticky nejsou závislé na zvoleném prostředí, může se s touto problematikou seznámit velké množství zájemců.
Možnosti k dalšímu rozvoji vidím v ošetření některých speciálních situací na vstupu, jako jsou dvě navzájem se překrývající úsečky. Dále bude možné rozšiřovat funkcionalitu ukázkových programů dle přání uživatelů.
49
Seznam algoritmů
1 SweepLine (S)........................ 11
2 HandleEventPoint(p).................. 12
3 FindNewEvent(s;/ sr/p).................. 13
4 DCELMERGE (Dlr D2).................... 22
5 OverlaySweepLine (D).................. 24
6 OverlayHandleEventPoint(p)............. 26
7 SplitCpSegment (s,p)................... 27
8 ClockwiseConnectUpper(p) .............. 29
9 ClockwiseConnectLower(p).............. 30
10 DoClockwiseConnect(s, t, p).............. 30
11 inner (c) ........................... 32
12 outer (c)........................... 32
13 OverlayCycles (D) .................... 34
14 OverlayComponents (C)................. 36
15 FindFaceLabels (G).................... 39
16 OverlayFaces (G) ..................... 40
17 MapOverlay (Dlr D2) ................... 41
51
Literatúra
[1] Python 2.7.7 documentation. 18.5.2014, [online].
URL [https://docs.python.0rg/2/]
[2] Bentley, J. L.; Ottmann, T. A.: Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput, 1979.
[3] Berk, M.; Kreveld, M.; Cheong, O.; ay. Computational Geometry. Springer, 2008, ISBN 978-3-540-77973-5.
[4] Chazelle, B.; Edelsbrunner, H.: An optimal algorithm for intersecting line segments in the plane. Journal of the ACM 39, 1992: s. 1-54.
[5] Lundh, E: An Introduction to Tkinter. 2005, [online].
URL [http://elfbot.org/tkinterbook/]
[6] Stutzbach, D.: Blist Documentation. 2010, [online].
URL [http://stutzbachenterprises.com/blist/]
[7] Summerfield, M.: Python 3. Computer press, 2010, ISBN 978-8-025-12737-7.
[8] Wróblewski, P.: Algoritmy. Computer press, 2004, ISBN 80-251-0343-9.
[9] Čadek, M.: Geometrické algoritmy, kap. 2. 2013, [online].
URL [http://tinyurl.com/qzzk5xb]
53
Příloha A
Obsah přiloženého CD
Přiložený kompaktní disk je nedílnou součástí této práce. Obsah kořenového adresáře je následující:
maps Adresář s předdefinovanými mapami.
geotools.py Modul usnaďňující práci s geometrickými objekty.
dcel.py Modul pro práci s dvojitě souvislým seznamem.
sweepline.py Program Sweepline.
mapoverlay.py Program MapOverlay.
55