3. PŘEKRYV Y MAP
Úvod. Cílem této kapitoly je ukázat, jakým způsobem uchováváme v počítači data, která umožňují kreslit mapy, a jak z dat popisujících dvě různé mapy vytvářet nová data popisující překryv těchto dvou map. Co to je překryv map (map overlay), je znázorněno na následujícím obrázku, kde máme dvě mapy, červenou a modrou, a jejich překryv, který je černý.
OBR 3.1 Překryv červené a modré mapy vytvoří černou mapu
Popis map - rovinných podrozdělení. Mapou bude pro nás rovinné podrozdělení (plane subdivision), které se skládá z konečného počtu vyznačených bodů, úseček, které jsou spojnicemi těchto bodů a vzájemně se neprotínají ve vnitřních bodech, a souvislých oblastí, které jsou ohraničeny těmito úsečkami. Rovinná podrozdělení budeme popisovat pomocí tzv. dvojitě souvislých seznamů (doubly connected edge list).
Takovýto seznam se skládá ze tří tabulek, které popisují vrcholy, hrany a oblasti. Vrcholy (verteces) jsou význačné body rovinného podrozdělení. Hrana (edge) je úsečka rovinného podrozdělení společně s orientací. Vrchol, ze kterého hrana vychází, se nazývá počátek (origin). Ke každé hraně existuje hrana určená stejnou úsečkou ale s opačnou orientací. Tu nazýváme dvojčetem (twin) dané hrany. Třetím pojmem v popisu rovinných podrozdělení jsou oblasti (faces). Oblast, která sousedí zleva s danou hranou (co je zleva a co je zprava, je určeno orientací hrany) se nazývá přilehlá k dané hraně. Tento pojem umožňuje pro danou hranu e jednoznačně definovat jejího následníka next(e) a předchůdce prev(e). Následník vychází z koncového bodu hrany e, má stejnou přilehlou oblast a mezi ním a hranou e nejsou žádné jiné hrany s těmito vlastnostmi. Předchůdce je hrana, která končí v počátku hrany e, má rovněž stejnou přilehlou oblast a mezi ním a hranou e nejsou žádné jiné hrany s předchozími dvěma vlastnostmi. Všechny tyto pojmy jsou demonstrovány na následujících obrázcích.
OBR 3.2 Hrana e\ vychází z vrcholu v±, hrana e2 je dvojčetem hrany ei, oblast f\ je přilehlá k hranám ei, e% a eg. Následníkem hrany e\ je e%, nikoliv e§. Předchůdcem hrany e2 je e-j.
Dalším pojmem, který budeme používat, je pojem cyklu. Je to posloupnost hran e1; e2,..., en, en+1 taková, že ei+1 je následníkem e^ a en+1 = e\. Každá omezená oblast je ohraničena vnější hranicí, kterou při vhodné orientaci můžeme popsat jako cyklus hran, které mají danou oblast za přilehlou. Hovoříme o vnějším cyklu. Některé oblasti jsou ohraničeny i zevnitř jedním nebo více cykly. Orientaci jejich hran bereme opět tak, aby hrany byly k dané oblasti přilehlé. Nazýváme je vnitřní cykly.
OBR. 3.3 Posloupnost hran ei, e2, e%, 04, e*,, e$, e-j je vnějším cyklem oblasti /, posloupnosti e§, eg, eio a en, ei2, ei3,     jsou vnitřními cykly oblasti /.
Nyní můžeme popsat tabulky dvojitě souvislého seznamu podrobněji.
1
2
Vrcholy. V tabulce pro vrcholy je pro každý vrchol uvedeno jeho jméno, jeho souřadnice a ukazatel (pointer) na jednu vycházející hranu.
Hrany. Řádek v tabulce hran uvádí pro každou hranu její jméno, ukazatel na její počátek (bod, ze kterého vychází), ukazatel na její dvojče, ukazatel na přilehlou oblast, ukazatel na následníka a ukazatel na předchůdce.
Oblasti. Řádek v tabulce pro oblasti vypadá takto: jméno oblasti, ukazatel na jednu hranu z vnější hranice (existuje-li), ukazatel na jednu hrana z každého cyklu vnitřní hranice (existují-li).
Příklad jednoduchého rovinného podrozdělení a jeho popis pomocí dvojitě souvislého seznamu najdete na obrázku 3.4 a v následující tabulce.
OBR 3.4. Příklad jednoduchého (i když trochu netypického) rovinného podrozdělení.
TAB 3.1
Popis pomocí dvojitě souvislého seznamu lze chápat jako minimální popis rovinného podrozdělení, ze kterého můžeme algoritmicky získat všechna další data v čase 0(n), kde n je množství požadovaných dat. Chceme-li například najít všechny hrany vnějšího cyklu oblasti /, vezmeme jednu hranu z tabulky, k ní najdeme následníka, k následníkovi najdeme opět následníka a to provádíme tak dlouho, až se dostaneme k původní hraně. Díky tomu, že používáme ukazatele, lze hledání následníka považovat za krok časové náročnosti 0(1) a díky tomu je časová náročnost vyhledání všech hran vnější hranice rovna 0(n), kde n je počet hran ve vnějším cyklu. Obdobným způsobem si jako jednoduché cvičení vyřešte tyto úkoly:
- najít všechny hrany vycházející z daného vrcholu v a vypsat je v pořadí proti směru hodinových ručiček.
- najít všechny oblasti, které sousedí s vrcholem v a vypsat je v pořadí proti směru hodinových ručiček. (Pozor, některé oblasti se mohou opakovat.)
Algoritmus pro překryv map. Mějme dána dvě rovinná podrozdělení Si a S2, popsaná dvojitě souvislými seznamy T>(Si) a D(S2). Cílem našeho algoritmu je vytvořit dvojitě souvislý seznam X> pro překryv 0(S±,S2) map S± a 1S2. Navíc, u každé nové oblasti / překryvu chceme uvést jména původních oblastí v S± a S±, ve kterých oblast / leží.
Pro zjednodušení budeme o rovinném podrozdělení S± mluvit jako o červené mapě a o podrozdělení Si jako o modré mapě. Tomu budou odpovídat i naše obrázky. Algoritmus začíná tím, že vytvoříme nový seznam X> spojením dvojitě souvislých seznamů pro obě mapy. Úprava takto vytvořeného seznamu na dvojitě souvislý seznam překry vu má dva kroky. V prvém z nich doplňujeme a upravujeme záznamy v X> týkající se vrcholů a hran tak, aby odpovídaly překryvu map. V druhé části provádíme úpravy týkající se oblastí.
Vrcholy a hrany. Tato část je založena na algoritmu zametači přímky pro nalezení průsečíků úseček, který byl podrobně popsán v předchozí kapitole. Jde však o jeho relativně pracnou modifikaci, proto v této kapitole provedeme popis algoritmu pouze slovně a jeho průběh budeme demonstrovat na příkladech. Popis pomocí pseudokódů
3
by byl příliš dlouhý. Čtenáře odkazujeme na pseudokódy 4 - 10 v diplomové práci Dominika Janků (https://is.muni.cz/auth/th/359588/fi_m/diplomka.pdf).
Začneme tím, že vytvoříme seznam úseček zadaných červenými a modrými hranami a jejich koncových vrcholů. (Pro zjednodušení předpokládejme, že průnikem červené a modré úsečky je buď bod, nebo prázdná množina, nebo jsou obě úsečky totožné. V posledním případě považujeme úsečky za jedinou úsečku, která je ovšem nositelem obou barev.) Ke každému vrcholu p přiřadíme seznamy L(p) a U(p) se stejným významem jako v předchozí kapitole, přitom si budeme pamatovat, kolik úseček v těchto seznamech je červených a kolik modrých. Aktivujeme frontu událostí Q, aby obsahovala všechny vrcholy, a binární vyvážený strom, který bude na začátku prázdný. Stejně jako v předchozí kapitole začněme provádět metodu zametači přímky.
Popíšeme algoritmus při průchodu událostí p. Jestliže množina C(p) úseček, pro které je p vnitřním bodem, je prázdná a sjednocení L(p) U U (p) obsahuje pouze úsečky jedné barvy, neprovádíme v seznamu X> žádné změny. V opačném případě každou úsečku z C(p) rozdělíme na dvě úsečky s koncovým bodem p a ty zařadíme do L(p) a U(p). Novým úsečkám přiřadíme hrany - těm, které končí v p přiřadíme hrany původní, těm, které začínají v p hrany nové, viz následující obrázek.
OBR. 3.5 Původní a nové označení úseček a hran.
Nyní provedeme v seznamu X> tyto změny. Přidáme řádek pro vrchol p, upravíme řádky pro původní hrany odpovídající úsečkám, obsahujícím vrchol p, a přidáme řádky pro nové hrany. Pro určení nových následníků a předchůdců zmíněných hran uspořádáme pomocí binárního stromu nejdříve úsečky z L(p) (to odpovídá poloze zametači přímky před událostí p) a potom uspořádáme úsečky z U (p) (při poloze zametači přímky pod událostí p). Tím dostaneme uspořádání úseček z L(p) a U (p) kolem bodu p ve směru hodinových ručiček. Konkrétní realizaci této myšlenky si ukažme na příkladu z obrázku 3.5
Pořadí úseček z L(p) je su < s'u. Pořadí úseček z U(p) je s[ < si. Tím je určeno pořadí úseček kolem bodu p ve směru hodinových ručiček: su, s'u, si, s[. Z tohoto pořadí určíme například, že následníkem hrany ex je e§ a předchůdcem e5 je e3. Nový řádek pro vrchol p, upravený řádek pro hranu ex a nový řádek pro e5 budou tedy vypadat takto
TAB 3.2
TAB 3.3
Veškeré informace týkající se oblastí ponecháváme beze změn. Tímto postupem dostaneme v seznamu X> všechny informace o vztazích vrcholů a hran obou překryvů.
Oblasti. Každá omezená oblast je určena svou vnější hranicí představovanou vnějším cyklem. Proto k určení oblastí překryvu potřebujeme najít všechny cykly a mezi nimi určit ty, které jsou vnějšími cykly.
4
K určení cyklů nám stačí informace o následnících, které jsou již v seznamu T> zachyceny. Vezmeme nějakou hranu e, najdeme jejího následníka, k němu dalšího následníka a tak dále až se dostaneme opět k hraně e. Potom vezmeme nějakou hranu, která v tomto cyklu nevystupuje. Stejným postupem dostaneme další cyklus. Takto tedy dostaneme všechny cykly.
Nyní si ukážeme, jak rozlišíme vnější a vnitřní cykly. V daném cyklu vezmeme vrchol v, který leží nejvíce vlevo (je nejmenší v lexikografickém uspořádání z předchozí kapitoly). Nechť do vrcholu v přichází hrana ex a vychází hrana e2. Jestliže úhel od ei k e2 měřený přes přilehlou oblast je menší než 180°, jde o cyklus vnější. Je-li tento úhel větší než 180°, je cyklus vnitřní.
OBR 3.6 Vnější cyklus c\ s úhlem a < 180°, vnější cyklus c2 s úhlem (3 > 180°.
Početně o tom rozhodneme podle znaménka determinantu
kde ei a e2 bereme jako vektory o souřadnicích (eix, eiy). Je-li kladné, je cyklus vnější, je-li záporné jde o cyklus vnitřní.
Známe tedy všechny vnější a vnitřní cykly pro překryv. Pro neomezenou oblast zaveďme ještě fiktivní cyklus c^. Nyní každý vnější cyklus definuje právě jednu oblast. Abychom k oblastem přiřadili i vnitřní cykly sestrojíme následující graf Q. Jde o graf ve smyslu teorie grafů, jehož uzly jsou všechny cykly. Hrany tohoto grafu vytvoříme následujícím způsobem:
Vezmeme vnitřní cyklus c\. Nechť p je ten z jeho vrcholů, který leží nejvíce vlevo. Nechť s je úsečka ležící nejblíže vlevo od p (informaci o nejbližší levé úsečce pro každou událost zjišťujeme v prvém kroku algoritmu při použití zametači přímky). Úsečka s určuje hranu e se stejnou přilehlou oblastí jako má vnitřní cyklus c\. Tato hrana pak určuje cyklus c2, který může být vnitřní i vnější. Jestliže vlevo od p neleží žádná úsečka, vezmeme za c2 onen fiktivní vnější cyklus c^. Cykly c\ a c2 spojíme v grafu Q hranou.
OBR 3.7 V grafu Q je vnitřní cyklus c\ spojen hranou s vnitřním cyklem c2 a ten je spojen hranou s vnějším cyklem C3.
V takto sestrojeném grafu určíme komponenty souvislosti. V každé komponentě je právě jeden vnější cyklus, ten určuje jednu oblast překryvu. Tedy mezi komponentami souvislosti grafu a oblastmi je vzájemně jednoznačná korespondence. Vnitřní cykly v dané komponentě souvislosti jsou vnitřními cykly odpovídající oblasti. Se znalostí vnějšího cyklu a všech vnitřních cyklů každé oblasti teď můžeme napsat v seznamu T> tabulku pro oblasti. Dále ke každé hraně najdeme cyklus, ve kterém leží, a k tomuto cyklu jeho oblast. To je přilehlá oblast k dané hraně. Tím doplníme i poslední údaj v tabulce hran.
OBR 3.8 Cykly v rovinném podrozdělení a graf Q, který vytvářejí. Komponentám souvislosti grafu odpovídají postupně oblasti f\, f2, j4, j5, foo-
5
Určení původních oblastí. Ještě zbývá ke každé oblasti / překryvu najít oblasti fi z červené mapy a^z modré mapy, ve kterých / leží. Mohou nastat dvě možnosti. Pokud v hraničních cyklech oblasti / leží hrany obou barev, pak přilehlá oblast k červené hraně je f\ a přilehlá oblast k modré hraně je /2.
OBR 3.9 Určení původních oblastí f\ a /2 pro novou oblast /.
Pokud jsou všechny hraniční cykly oblasti / jednobarevné, řekněme červené, určíme fi stejně jako v předchozím případě. Je-li / neomezená, je /2 neomezená oblast v modré mapě. Pro omezenou oblast / určíme oblast /2 takto: vezmeme vrchol vnějšího cyklu oblasti / ležící nejvíce vlevo. Najdeme k němu nejbližší úsečku vlevo. Ta určuje vnitřní nebo vnější cyklus pro oblast /' sousedící s /. Je-li aspoň jedna hrana cyklů této oblasti modrá, určíme /2 jako oblast k ní přilehlou v modré mapě. Je-li /' neomezená, je oblastí /2 neomezená oblast v modré mapě. Je-li /' omezená a jsou-li všechny hrany jejích cyklů červené, pokračujeme stejným postupem jenom oblast / teď nahradíme oblastí /'. Příslušná modrá oblast pro /', je oblastí /2 pro původní oblast /.
OBR 3.10 Určení původních oblastí f\ a /2 pro novou oblast /.
Průniky a sjednocení mnohoúhelníků. Předchozí algoritmus pro překryv map lze použít k nalezení průniku, sjednocení nebo rozdílu dvou obecně nekonvexních mnohoúhelníků. Jednoduše souvislý mnohoúhelník je takový mnohoúhelník, který je souvislý a ve svém vnitřku nemá "díry", tj. každá uzavřená křivka lze v něm stáhnout spojitě bez přetržení do bodu. jednoduše souvislý mnohoúhelník tedy určuje rovinné podrozdělení se dvěma oblastmi, vnitřní a vnější. Průnikem dvou mnohoúhelníků jsou ty oblasti překryvu jejich rovinných podrozdělení, které leží ve vnitřních oblastech obou podrozdělení. Podobně sjednocení mnohoúhelníků je tvořeno těmi oblastmi překryvu, které leží aspoň v jedné vnitřní oblasti odpovídajících podrozdělení. Viz následující obrázky.
OBR 3.11 Průnikem červeného a modrého mnohoúhelníka je sjednocení oblastí /2 a f'4. Sjednocení mnohoúhelníků je popsáno sjednocením oblastí J'q až f iq.
Pseudokódy pro algoritmu, jeho implementace a složitost. Algoritmus lze stručně shrnout takto:
ALGORITMUS 6 z pseudo.pdf (místo half-edge psát pouze edge)
Podrobné pseudokódy lze nalézt v diplomové práci Překryvy map Dominika Janků https://is.muni.cz/auth/th/359588/fi_m/diplomka.pdf Řádky 1 a 2 se realizují pomocí pseudokódů 4 až 10 z diplomové práce. Hledání cyklů v řádek 4 je popsán pseudokódem 13, vnitřní a vnější cykly najdeme pomocí pseudokódů 11 a 12. Komponenty souvislosti grafu Q v řádku 5 se sestrojí pomocí pseudokódů 14, řádek 6 a 7 je popsán pseudokódem 16 a řádek 8 pseudokódem 15.
6
Součástí diplomové práce je rovněž implementace algoritmu. Její popis jev poslední kapitole práce, potřebné soubory jsou komprimovány v souboru cdrom.zip.
https://is.muni.cz/auth/th/359588/n_m/fakulta=1431 Složitost algoritmu je charakterizována následující větou, kterou uvedeme bez důkazu.
Věta 3.1. Nechť S± je rovinné podrozdélení komplexity n\ a nechť S2 je rovinné podrozdélení komplexity n2. Nechť n = n\ + n2. Potom časová složitost algoritmu, který sestrojí dvojité souvislý seznam pro překryv obou podrozdélení je
0((n + k) logn),
kde k je komplexita překryvu.