PV251 Vizualizace Jaro 2017 Výukový materiál 5. přednáška: Vizualizace geoprostorových dat Geoprostorová data se liší od ostatních typů dat především tím, že popisují objekty nebo jevy, které se vyskytují v reálném světě. Geoprostorová data se objevují v množství aplikací, jako například kreditní platební systém, telefonní sítě, sčítání lidu atd. V této přednášce se zaměříme na přehled speciálních vlastností a metod, které se využívají pro vizualizaci geoprostorových dat. Tato oblast se často označuje jako geovizualizace. Ukážeme si nejdůležitější základy geoprostorové vizualizace, jako jsou mapy a uvedeme si vizualizační techniky pro bodová, čárová, plošná a povrchová data. Tato oblast je široce pokryta oblastí GIS (geografických informačních systémů) a oblastí kartografie, proto se zde budeme touto oblastí zabývat čistě z vizualizačního hlediska. Po této přednášce bychom měli mít obecný přehled o state-of-the-art vizualizačních technikách pro geoprostorová data a měli bychom být schopni je implementovat a používat. Rozsáhlé množiny prostorových dat často vznikají akumulací diskrétních vzorků spojitého jevu v reálném světě. V současné době existuje řada aplikací, pro které je velmi důležité analyzovat a zobrazit vztahy mezi daty, které zahrnují geografické umístění. Příkladem je modelování globálního vývoje klimatu (např. měření teploty, srážek, rychlosti větru), sledování ekonomických a sociálních indikátorů (míra nezaměstnanosti, úroveň vzdělání atd.), analýza chování zákazníka, statistiky telefonních hovorů, plateb kreditní kartou či statistika kriminality. Díky speciálním vlastnostem takovýchto prostorových dat je jejich základní vizualizace přímočará – prostorové atributy jsou mapovány přímo na dvě dimenze výstupního zařízení (obrazovky), čímž dosáhneme zobrazení mapy. Body, čáry, plochy Mapy můžeme zjednodušeně považovat za zobrazení světa, který je redukován na body, čáry a plochy. Vizualizační parametry, jako například velikost, tvar, hodnota, textura, barva, orientace, doplňují zobrazovaná data o další informace. Podle organizace U.S. Geological Survey jsou mapové vizualizace definovány jako sada bodů, čar a ploch, které jsou definovány pomocí jejich pozice v souřadném systému (prostorové vlastnosti) a dále pomocí dalších „neprostorových“ atributů. Z definice je zřejmé, že můžeme prostorové jevy rozlišit podle jejich prostorové dimenze či rozměru na: - Bodové jevy – nemají prostorovou složku. Mohou být označeny jako 0-dimenzionální a mohou být specifikovány pomocí dvojice (zeměpisná délka, zeměpisná šířka) a sady dalších atributů. Jako příklad můžeme uvést budovy, ropné vrty, města, … - Čárové jevy – mají určitou délku, jejich šířka je dána implicitně. Mohou být označeny jako 1-dimenzionální a mohou být udány pomocí sady dvojic (zeměpisná délka, zeměpisná šířka). Příkladem mohou být rozsáhlé telekomunikační sítě, cesty, hranice mezi státy, … Atributy spojené s čárovými jevy mohou obsahovat kapacitu, stupeň dopravní vytíženosti, jména, … - Plošné (area) jevy – obsahují délku i šířku. Mohou být označeny jako 2-dimenzionální a mohou být specifikovány pomocí sady dvojic (zeměpisná délka, zeměpisná šířka), které jsou uzavřeny v daném regionu. Každá dvojice může opět mít asociovánu sadu dalších atributů. Příkladem jsou jezera, politická mapa – státy, … - Povrchové (surface) jevy – kromě délky a šířky obsahují navíc výšku. Jsou tedy označovány jako 2,5-dimenzionální a mohou být specifikovány sadou vektorů složených ze zeměpisné délky, zeměpisné šířky a výšky a každá dvojice (zeměpisná délka, zeměpisná šířka) může mít asociovány další atributy. Typy map Mapy mohou být rozděleny podle jejich typů na základě vlastností zobrazovaných dat (kvalitativní vs. kvantitativní, diskrétní vs. spojité) a na základě vlastností tzv. grafických proměnných (body, čáry, povrchy, objemy). Příklady výsledných map pak mohou být: - Mapy symbolů (nominální bodová data) - Bodové mapy (ordinální bodová data) - Mapy využití půdy - land use maps (nominální plošná data) - Choropletové mapy – choropleth maps (ordinální plošná data) – využívá se k zobrazení jevů pomocí barevných ploch a odstínů. Zobrazuje se tak například hustota obyvatelstva. - Čárové diagramy (nominální nebo ordinální čárová data) - Izočárové mapy – isoline maps (ordinální povrchová data) - Povrchové mapy – surface maps (ordinální objemová data). - Obrázek navíc ukazuje stejná data zobrazena pomocí kontury a poté pomocí povrchové mapy. Různé typy zobrazení Z ukázek je zřejmé, že stejná data mohou být zobrazena pomocí různých typů map. Pomocí agregace bodových dat uvnitř oblastí můžeme z bodové mapy vytvořit choropletovou mapu. Podobně z mapy symbolů lze vytvořit mapu využití půdy. Můžeme rovněž generovat povrch se zobrazením hustoty bodové mapy a zobrazit ji jako izočárovou mapu nebo povrchovou mapu. Pokud seskupíme bodová data uvnitř ploch a namapujeme počet bodů uvnitř dané plochy na jejich velikost, dostaneme tzv. kartogram – tematickou mapu. Na obrázku je zobrazen kartogram světové populace. Průzkumná geovizualizace V průzkumné geovizualizaci je klíčovou schopnost interakce s mapami. V porovnání s tradiční kartografií je klasifikace a mapování dat pomocí této techniky interaktivně přizpůsobeno potřebám uživatele. Zároveň jsou umožněny interaktivní dotazy. Tyto interakční schopnosti jsou podporovány celou sadou současných technik a systémů. Ty umožňují například spojení několika map či kombinaci map se standardní statistickou vizualizací, jako jsou sloupcové a čárové grafy. Mapy se dají kombinovat i s mnohem složitějšími technikami pro multidimenzionální vizualizace, jako například s paralelními souřadnicemi. Mapová projekce Při vizualizaci geoprostorových dat hraje klíčovou roli mapová projekce. Mapová projekce se zabývá mapováním pozic na zeměkouli (koule) na pozice na obrazovce (rovinný povrch). Mapová projekce je definována jako Π: (λ, φ) → (x, y). Datový formát pro stupně zeměpisné délky (λ) je omezen na interval [-180, 180], kde záporné hodnoty značí západní délku a kladné hodnoty představují východní délku. Stupně zeměpisné šířky (φ) jsou definovány podobně pro interval [-90, 90], kde záporné hodnoty představují jižní šířku a kladné hodnoty reprezentují severní šířku. Mapové projekce mohou mít různé vlastnosti: - Konformní projekce – zachovává korektně lokální úhly každého bodu mapy. To znamená, že rovněž lokálně zachovává tvary. Avšak plocha zachována není. - Ekvivalentní projekce – specifická plocha části mapy pokrývá přesně stejný povrch na kouli. Výsledná mapa deformuje tvar a úhly. Například čtverec na povrchu zeměkoule je mapován na obdélník na mapě o stejné velikosti plochy. - Ekvidistantní projekce – zachovává vzdálenost od nějakého bodu nebo čáry. - Gnomická projekce (gnomonic) – umožňuje zobrazení „hlavních kružnic“ (great circle) pomocí čar. Hlavní kružnice rozděluje kouli na dvě stejně velké polokoule (u zeměkoule je to rovník). Gnomické projekce zachovávají nejkratší cestu mezi dvěma body. Celou polokouli není možné zobrazit, protože okraje „utíkají“ do nekonečna. - Azimutální projekce – zachovávají směr od středového bodu. Obvykle má tento typ projekce radiální symetrii, například vzdálenosti od středového bodu jsou nezávislé na úhlu a zároveň soustředné kružnice se středem ve středovém bodu projekce se promítají na kružnice se středem ve středovém bodu mapy. - Retroazimutální projekce – směr z bodu S do fixního místa L odpovídá směru z S do L na mapě. Mapové projekce – klasifikace podle typu povrchu Mapové projekce mohou být klasifikovány rovněž podle typu povrchu, na který je koule promítnuta. Nejdůležitější typy takovýchto povrchů jsou: - Válcová (cylindrická) projekce - Rovinná projekce - Kuželová (kónická) projekce Válcová projekce Válcová projekce promítá povrch koule na válec umístěný kolem této koule. Každý bod koule je pak promítnut na vnější válec. Válcové projekce mají výhodu v tom, že dokáží zobrazit celý sférický povrch. Většina válcových projekcí zachovává lokální úhly a tudíž je konformní. Stupně zeměpisné délky a šířky jsou obvykle vzájemně ortogonální. Pseudo-válcová projekce Pseudo-válcové projekce reprezentují hlavní poledník a každou rovnoběžku jako jednu rovnou čáru, ostatní poledníky jsou deformovány. Rovinná projekce Rovinné projekce jsou azimutální projekce mapující povrch koule na rovinu, která je tečná k dané kouli. Přitom tečný bod odpovídá středu projekce. Některé rovinné projekce jsou perspektivní. Kuželová projekce Principem kuželové (cone) projekce je mapování povrchu koule na její tečný kužel. Stupně zeměpisné šířky jsou reprezentovány kružnicemi se středem ve středu projekce, stupně zeměpisné délky jsou rovné čáry vycházející z tohoto středu. Kuželové projekce mohou být navrženy tak, aby zachovávaly vzdálenosti od středu kuželu. Existuje rovněž řada pseudo-kuželových projekcí, které zachovávají například vzdálenosti od pólu a zároveň vzdálenosti od poledníků. Příklady běžně používaných mapových projekcí Nyní si uvedeme detaily několika široce používaných mapových projekcí. Proměnné definované v mapových projekcích jsou uvedeny v tabulce. Ekvidistantní válcová projekce Tento typ projekce je jedním z nejstarších a nejjednodušších typů projekce – cylindrické projekce. Tato technika mapuje poledníky na vertikální rovné čáry se stejnou vzdáleností od sebe. Rovnoběžky jsou mapovány na stejnoměrně rozložené horizontální rovné čáry. Sférické souřadnice jsou pak transformovány v poměru 1:1 na obdélníkový (pravoúhlý) povrch: x = λ, y = ϕ. Tento typ projekce nevyhovuje základním požadavkům kladeným na mapy a není ani konformní ani ekvivalentní. Díky svému velkému zkreslení se téměř nepoužívá pro navigaci, ale je vhodný při vytváření například tematických map. Lambertova válcová projekce Lambertova válcová projekce je typem ekvivalentní projekce, která je jednoduchá na napočítání a poskytuje poměrně pěkné mapy světa. Mapování je definováno jako: Hammer-Aitoffova projekce Jedná se o modifikovanou azimutální projekci. Hlavní poledník a rovník jsou reprezentovány rovnými čarami, přičemž poledník má poloviční délku než rovník. Ostatní poledníky a rovnoběžky jsou reprezentovány nerovnoměrně rozmístěnými křivkami. Mapování je definováno pomocí uvedených rovnic. 00 cos*)(  x 0cos sin   y 2 1 ) 2 coscos1( 2 sincos22      x 2 1 ) 2 coscos1( sin2     y Jedná se o ekvivalentní projekci a její eliptická forma ponechává uživateli vjem o tom, že zeměkoule je sférická. Tento typ mapování se využívá nejčastěji při vytváření tematických map. Mollweideova projekce Jedná se o ekvivalentní pseudo-válcovou projekci, která reprezentuje zeměkouli jako elipsu. Rovnoběžky jsou reprezentovány rovnými čarami a všechny poledníky kromě hlavního jsou znázorněny jako rovnoměrně rozloženy eliptické oblouky. Mollweide mapování je definováno pomocí uvedených rovnic. Proměnná Θ je spočtena s využitím Newtonovy interpolační metody. Mollweideovy projekce jsou využívány zejména při vytváření tematických map celého světa. Kosinusoidální projekce Kosinusoidální projekce je typem jednoduché pseudo-válcové ekvivalentní projekce, kterou lze spočítat velmi rychle. Má unikátní tvar a překvapivě dobré lokální vlastnosti. Mapování je definováno pomocí uvedených rovnic.   cos)(22 0 x sin22 1 y  sin)2sin(2   cos*)( 0x y Albersova ekvivalentní kuželová projekce Tato projekce je příkladem kuželové projekce s přesným zachováním plochy. Základní myšlenkou je využití dvou standardních rovnoběžek (označeny jako β_1 a β_2) k redukci deformací, které se objevují při projekci, která využívá pouze jednu standardní rovnoběžku. Poledníky jsou reprezentovány rovnoměrně rozloženými rovnými čarami, které se protínají v jednom bodě. Rovnoběžky jsou znázorněny soustřednými kružnicemi s nerovnoměrnou vzájemnou vzdáleností. Mapování je definováno pomocí sady rovnic. Není zachován tvar ani vzdálenosti, avšak zkreslení těchto vlastností je minimalizováno v regionu mezi dvěma standardními rovnoběžkami. Vzdálenosti jsou nejpřesnější ve středních zeměpisných šířkách, a proto je tento typ projekce využíván spíše pro menší regiony se západo-východní orientací ve středních šířkách. Vizuální proměnné pro prostorová data Mapy jsou využívány různým způsobem – například pro zjištění informace o určité lokaci, zjištění obecné informace o prostorových vzorech v mnoha mapách. Proto mapování vlastností prostorových dat na vizuální proměnné musí tyto cíle reflektovat. Vizuální proměnné pro prostorová data jsou následující: - Velikost – velikost jednotlivých symbolů, šířka čar, … - Tvar – tvar jednotlivých symbolů nebo vzorů v čarách a plochách - Jas – jas symbolů, čar a ploch - Barva – barva symbolů, čar, ploch 2 coscos 21   n 2221 2 ) 2 (sin*) 2 (sin* 4 ) 2 2 sin(* 4  nn p    )*sin( n p x  )*cos( n p y  - Orientace – orientace jednotlivých symbolů nebo vzorů v čarách a plochách - Textura – rozmístění vzorů v symbolech, čarách a plochách - Perspektivní výška – perspektivní 3D pohled na jevy , kdy jsou datové hodnoty mapovány na perspektivní výšku jednotlivých bodů, čar nebo ploch - Rozmístění, uspořádání (arrangement) – rozmístění vzorů v jednotlivých symbolech (pro bodové jevy), vzorů teček a čárek pro čárové jevy a vzorů pravidelného vs. náhodného rozmístění symbolů pro plošné jevy Vliv úpravy vstupních dat na výslednou mapu Kartografické návrhy jsou intenzivně studovány již po několik desetiletí a za tu dobu vznikly velmi kvalitní průvodci těchto návrhů map. Všechny jsou založeny na výsledcích výzkumu v oblasti lidského vnímání. Navíc vstupní data často podléhají různým úpravám (vzorkování, segmentace, normalizace, …), což může mít významný vliv na výslednou vizualizaci. Jako příklad si uveďme dvě vizualizace stejných dat ve formě choropletové mapy. Jediným rozdílem je odlišný výběr oddělení jednotlivých „tříd“, což má ale velmi významný dopad na generované mapy. Dalším příkladem je výrazná změna výsledné vizualizace, která vznikla pouze změnou absolutního mapování na relativní. Nalevo jsou vizualizována absolutní čísla, zatímco napravo jsou zobrazena relativně vzhledem k velikosti populace. Díky velkým rozdílům v populaci v některých oblastech může dojít ke zcela opačnému vyjádření, než bylo v absolutních číslech. Vizualizace rovněž silně závisí na hranicích oblastí, které shlukujeme. Obrázek ukazuje známý případ londýnské cholery s různými způsoby shlukování oblastí, což vede k odlišným choropletovým mapám. Vizualizace dat V další části se zaměříme na vizualizační techniky pro data podle jejich typů. Soustředíme se na tři základní typy dat – bodové, čárové a plošné. Vizualizace bodových dat První důležitou třídou prostorových dat jsou bodová data. Svou povahou jsou diskrétní, nicméně mohou popisovat spojitý jev, například měření teploty v daném místě. Podle povahy vstupních dat a požadovaného úkolu se musí návrhář rozhodnout, jestli chce data zobrazit spojitě či diskrétně, hladce nebo přerušovaně. Obrázek ilustrativně znázorňuje možné kombinace těchto rozhodnutí. U diskrétní dat předpokládáme, že se vyskytují v určitých místech, zatímco spojitá data musí být definována ve všech místech. Hladká data se mění postupně, zatímco přerušovaná (abrupt) se mění náhle. Bodové jevy mohou být vizualizovány takovým způsobem, že na místo, kde se jev vyskytuje, se umístí daný symbol. Nejjednodušší vizualizace tohoto typu se nazývá bodová. Kvantitativní parametr může být mapován na velikost nebo barvu symbolu. Nejčastěji používané symboly v bodových mapách jsou kruhy, avšak je možné využít čtverečky, sloupce atd. Pokud je velikost symbolu spojena s kvantitativním parametrem bodu, je nutné uvažovat, jakým způsobem škálovat symboly. Totiž korektní výpočet velikosti jednotlivých symbolů nutně neznamená, že symboly budou rovněž korektně vnímány. Vnímaná velikost symbolů nemusí nutně korespondovat se skutečnou velikostí a to zejména díky problémech s lidským vnímáním – vnímání velikosti symbolů závisí na lokálním okolí. Proto neexistuje globální výpočet pro perceptuální vnímání velikosti. Na obrázku je uveden příklad různého vnímání velikosti kruhu v závislosti na lokálním okolí. Zobrazený jev se nazývá Ebbinghausova iluze. Podobně, pokud je pro reprezentaci kvantitativního parametru využita barva, musíme podobně vzít v úvahu problémy s vnímáním barvy. Bodové mapy jsou elegantním způsobem, jakým sdělit velké množství informací o vztazích mezi bodovými jevy v kompaktní, vhodné a známé formě. Avšak při zobrazení velkého množství dat do mapy s rozdílnou hustotou dat může dojít k překryvu v hustě obsazených oblastech (například populace), zatímco řídce obsazené oblasti zůstávají v podstatě prázdné (viz obrázek). Obrázek vlevo reprezentuje prostorové rozmístění dané události. Pokud si mapu přiblížíme, je vidět, že dochází ke značnému překryvu dat. Příklady takovéhoto typu prostorových dat jsou platby kreditní kartou, telefonní hovory, zdravotní statistiky, záznamy o životním prostředí, statistika kriminality atd. Je dobré si všimnout, že analýzy mohou obsahovat několik parametrů, které mohou být vyneseny do několika map. Pokud všechny tyto mapy prezentují data ve stejné podobě, je možné dát jednotlivé parametry do určitých vztahů a detekovat lokální korelace mezi daty, závislosti a další charakteristiky. Existuje několik přístupů pro řešení problému se zobrazením „hustých“ dat. Jednou ze široce používaných metod je 2,5D vizualizace shlukující datové body do regionů. Tato technika je dostupná v komerčních systémech, jako například In3D firmy VisualInsight nebo ArcView od ESRI. Alternativní přístup ukazující větší detaily zobrazuje jednotlivé datové body jako sloupce vzhledem k jejich statistické hodnotě v mapě. Tuto techniku využívají systémy jako MineSet od Vero Insight a Swift 3D od AT&T. Problém této metody spočívá v překryvu sloupců v případě velkých datových množin. Ve finále je tedy viditelná pouze určitá část vstupních dat. PixelMaps Přístupem, jak neshlukovat data, ale zároveň se vyhnout jejich překryvu, je PixelMap přístup. Hlavní myšlenkou je přemístit pixely, které by se jinak překrývaly. Algoritmus provádějící přemístění rekurzivně dělí datovou množinu na čtyři podmnožiny obsahující datové body ve čtyřech stejně velkých podregionech. Efektivní implementace tohoto algoritmu využívá strukturu založenou na quad-tree přístupu, která podporuje rekurzivní proces dělení. Proces dělení funguje následovně. Začneme v kořeni quad-tree a v každém kroku dělíme datový prostor na 4 podregiony. Podmínkou dělení je, že prostor obsažený v subregionu (v pixelech) je větší než počet pixelů patřících danému podregionu. Pokud po několika opakováních rekurze zůstává v podregionu pouze omezený počet datových bodů, jsou body umístěny pomocí tzv. „pixel placement“ algoritmu, který umístí první datovou položku na její korektní pozici a následné datové položky jsou umístěny na nejbližší neobsazené pozice. Výsledné umístění je lokálně quasi-náhodné. Problém zobrazení bodových dat pomocí PixelMaps spočívá v tom, že v oblastech s vysokým překryvem dat závisí přemístění jednotlivých bodů na pořadí jejich uložení v databázi. Obrázek ukazuje čtyři časové úseky zobrazené pomocí tohoto typu vizualizace (0:00 AM, 6:00 AM, 10:00 PM a 6:00 PM, vše EST pásmo), kdy byl zaznamenán objem telefonních hovorů ve Spojených Státech v desetiminutových intervalech. Vizualizace intuitivně ukazuje „vývoj“ objemu telefonních hovorů podle časových pásem – tedy kdy se v daných oblastech lidé probouzí nebo například útlum hovorů v době oběda. Vizualizace odhaluje jak očekávané vzory chování, tak ukazuje ty neočekávané – například kde se vyskytují největší call centra fungující přes noc. Vizualizace čárových dat Základní myšlenkou vizualizace prostorových dat popisujících lineární jevy ke jejich reprezentace pomocí úsečkových segmentů mezi dvěma koncovými body určenými zeměpisnou délkou a šířkou. Standardní mapování čárových dat umožňuje rovněž mapování dalších parametrů vstupních dat, jako například šířka čáry, vzor čáry, barva, čáry a označování čar pomocí značek. Navíc je možné mapovat počáteční, koncové body a průsečíky na uzly se specifickou barvou, velikostí, tvarem a označením. Čáry nemusí být rovné, mohou to být polyčáry nebo splajny. Mapy sítí (network maps) se používají v široké škále aplikací. Některé přístupy pouze zobrazují konektivitu sítí pro pochopení jejich struktury. Eick a Wills použili funkce jako agregace, hierarchické informace, pozice uzlů a další pro prozkoumání rozsáhlých sítí s hierarchickou strukturou a bez přirozeného uspořádání. Dále využili barvu a tvar pro kódování informace v uzlech a šířku a barvu čáry pro kódování informace o spojích mezi uzly. Výzkumná skupina NCSA k těmto mapám sítí přidala i 3D grafiku, pomocí které animovali pohyb packetů v internetové páteřní síti. Becker, Eick a Wilks popsali systém známý pod názvem SeeNet. Hlavní myšlenkou je do procesu zahrnout uživatele a nechat jej interaktivně řídit zobrazení na displeji a tím se zaměřovat na zajímavé vzory v datech. K tomu využívají dvě statická zobrazení sítí pro vizualizaci geografických vztahů. Další zajímavý systém pro vizualizaci rozsáhlých síťových dat je Swift-3D System of AT&T (viz obrázek), který integruje sadu relevantních vizualizačních technik. Všechny zmíněné techniky pro zobrazení sítí trpí problémem při překrytí čárových segmentů v oblastech s hustým pokrytím dat. Mapy toku (flow maps) Technika flow map je inspirována grafovými algoritmy, které minimalizují protínání hran a deformaci pozic uzlů při zachování jejich relativní pozice. Algoritmus je založen na hierarchickém klastrování podle pozice uzlů a toků mezi nimi, které dokáže spočítat shluky a přesměrování toků. V porovnání s ostatními mapami toků generovanými počítačem (viz obrázek vlevo znázorňující tok turistů po Berlíně), Stanford flow maps dokáže produkovat mnohem „čistší“ grafy (viz obrázek vpravo ukazující migraci z Kalifornie). Shlukování hran rovněž přispívá k redukci nejasností v čárové reprezentaci. Pokud máme nad uzly definovánu hierarchii, mohou podle ní být shlukovány odpovídající hrany. Uzly spojeny skrz kořen hierarchie jsou maximálně ohnuty, zatímco uzly ve stejné úrovni hierarchie jsou ohnuty minimálně. Tato metoda může být kombinována s řadou dalších vizualizačních technik, jako jsou tradiční mapy, stromové vizualizace atd. Obrázky ukazují shlukování hran aplikováno na vizualizaci provozu IP toku. Vizualizace ukazuje provoz z externích uzlů do interních uzlů zobrazených pomocí treemapy. Na obrázku je zřejmá výhoda zobrazení shluků hran (vpravo) v porovnání s původním zobrazením všech přímých hran (vlevo). Vizualizace plošných dat Pro vizualizaci plošných jevů se nejčastěji využívají tzv. tematické mapy. Tyto mapy mají několik variant. Nejpopulárnější varianta jsou tzv. choropletové mapy (řecky choro = plocha, pleth = hodnota), kde jsou hodnoty atributů kódovány pomocí barevných nebo stínovaných regionů na mapě. Choropletové mapy předpokládají, že mapované atributy jsou uvnitř regionů uniformně rozloženy. Na obrázku je ukázka choropletové mapy znázorňující výsledky voleb ve Spojených Státech v roce 2008 (Obama vs. McCain). Pokud má atribut jiné rozložení, než je rozdělení do regionů, je nutné využít jiné techniky, jako například tzv. dasymetrické mapy. V dasymetrických mapách zobrazovaná proměnná formuje plochu nezávislou na původních regionech. Například v porovnání s choropletovými mapami, hranice oblastí odvozená z atributu nemusí odpovídat daným regionům v mapě. Dalším důležitým typem map jsou tzv. izarytmické mapy (isarithmic maps) ukazující kontury spojitých jevů (viz obrázek ukazující koncentraci fotografií pořízených na ostrově Mainau). Typickými zástupci tohoto typu map jsou konturové a topografické mapy. Pokud jsou kontury odvozené z reálných datových bodů (například teplota měřená v daném místě), pak se tyto mapy nazývají izometrické. Pokud jsou data měřena pro daný region (například kraj) a datový bod je považován za těžiště, pak tyto mapy zobrazují takzvané izoplety (isopleth maps). Jeden z hlavních úkolů při generování izarytmických map je interpolace datových bodů za účelem získání hladkých kontur. Toho lze dosáhnout například triangulací. Komplexní a méně frekventovanou mapovací technikou jsou takzvané kartogramy, kdy je velikost regionů škálována za účelem zobrazení statistické informace. Kartogramy mají několik variant – sahající od spojitých kartogramů, které zachovávají topologii polygonálních meshů, po nespojité kratogramy, které jednoduše škálují každý polygon nezávisle na obdélníkových nebo kružnicových aproximacích ploch. Všimněte si, že plošná informace může být rovněž vizualizována pomocí diskrétních bodů nebo symbolů na mapě – například pomocí symbolů o velikosti určené proporčně vzhledem ke statistickým parametrům v mapě nebo pomocí bodové mapy. Nyní se detailněji zaměříme na choropletové mapy a kartogramy. Choropletové mapy Choropletové mapy obvykle prezentují plošné jevy v podobě stínovaných polygonů, které jsou uzavřeny konturou tvořenou sadou body, kdy první a poslední bod jsou shodné. Příkladem mohou být státy, kraje, parky atd. Choropletové mapy jsou využívány pro zvýraznění prostorového rozložení jednoho nebo více geografických atributů. Při generování choropletových map se většinou provádí normalizace dat (viz kapitola o předzpracování vstupních dat) a barevné a šedotónní mapování. Problém choropletových map spočívá v tom, že nejzajímavější hodnoty jsou často koncentrovány v hustě zastoupených oblastech (například s hustým zalidněním) s malými a stěží viditelnými polygony a naopak méně zajímavé hodnoty jsou rozprostřeny přes oblasti s nízkým osídlením, které jsou většinou reprezentovány pomocí velkých a vizuálně dominantních polygonů. Choropletové mapy tedy zvýrazňují oblasti reprezentované velkými polygony, které ale mají většinou nižší důležitost. Kartogramy Kartogramy jsou zobecněním běžných tematických map, které se snaží vyhnout problémům objevujícím se u choropletových map, kdy dochází k deformaci geografických dat na základě jejich statistické hodnoty. Kartogramy jsou specifickým typem mapových transformací, kdy je velikost regionů změněna na základě určité vstupní proměnné, která je svázána s geografickými vlastnostmi vstupních dat. Příkladem využití kartogramů jsou zobrazení demografie, výsledků voleb či epidemiologická data. Kartogramy můžeme rozdělit do několika kategorií. • Nespojité kartogramy (noncontinuous) Zcela vyhovují omezením týkajícím se plochy a tvaru, avšak nezachovávají topologii vstupní mapy. Protože škálované polygony jsou vykresleny dovnitř původních polygonů, nedochází i přes ztrátu topologie k problémům s vnímáním takovéto mapy. Horší je, že původní velikost jednotlivých polygonů omezuje jejich finální velikost – proto není možné libovolně zvětšit malé polygony bez škálování (zvětšení) celé mapy. V důsledku jsou důležité oblasti těžko viditelné a prostor obrazovky je využit velmi omezeně. Nepřiléhající, nesousedící kartogramy Škálují všechny polygony na jejich cílové velikosti, které přesně vyhovují prostorovým požadavkům. Jednotlivé tvary mohou být mírně relaxovány, tudíž polygony se dotýkají, ale bez překryvu. Díky tomu je celá topologie mapy rovněž vysoce relaxována, protože polygony si neudržují vzájemné „sousedské“ vztahy. Tento typ kartogramů poskytuje velmi dobré uspořádání ploch včetně zachování jejich tvarů. Avšak dochází ke ztrátě globálního tvaru a topologie mapy, což může zhoršit vnímání mapy jako celku. Kruhové kartogramy Zcela ignorují tvar vstupních polygonů a reprezentují je pomocí kruhů. Ve většině případů jsou i plošná a topologická omezení relaxována, proto tento typ kartogramů vykazuje stejné problémy jako předchozí nepřiléhající kartogramy. Spojité kartogramy Poslední kategorií jsou tzv. spojité kartogramy, které na rozdíl od předcházejících typů zcela zachovávají topologii mapy a relaxují daná plošná a tvarová omezení. Obecně kartogramy nedokáží plně zachovat tvar a plochu, proto generování kartogramů v sobě zahrnuje poměrně složitý optimalizační problém, který se snaží najít uspokojivý kompromis mezi zachování tvaru a plochy. Ačkoliv je obtížné generovat spojité kartogramy, výsledné polygonální meshe připomínají původní mapu mnohem více než jiné počítačem generované varianty kartogramů. Proto se ve zbytku této sekce budeme zabývat právě spojitými kartogramy. Kartogramy pokračování: Ruční vytvoření kartogramů je velmi obtížné, proto je velmi populární oblast studování automatických metod pro generování kartogramů pomocí počítače. Kartogramy mohou být rovněž považovány za obecnou techniku pro vizualizaci informace. Poskytují prostředky, jak se vypořádat se zachováním tvaru versus zachováním plochy pomocí škálování původních polygonů na základě externích parametrů. V takzvaných „populačních“ kartogramech je větší prostor alokován pro oblasti s hustým osídlením a tyto oblasti jsou navíc zvýrazněny (protože s vysokou pravděpodobností obsahují ta nejzajímavější data). Obrázek vlevo znázorňuje tradiční mapu výsledků voleb ve Spojených Státech v roce 2000, obrázek vpravo prezentuje stejnou informaci pomocí populačního kartogramu. V kartogramu je plocha států upravena podle jejich populace, což umožní zobrazit těsné výsledky voleb v jednotlivých státech mnohem přesněji a efektivněji než v původní choropletové mapě vlevo. Abychom kartogram označili za efektivní, musí být jeho sdělení rychle pochopitelné uživatelem a zároveň musí uživatel pochopit jeho vztah k původní mapě. Toto rozpoznání závisí zejména na zachování základních vlastností, jako jsou tvar, orientace či sousednost. Toto zachování je však zejména u kartogramů velmi obtížné dosáhnout a bylo prokázáno, že obecně tento problém kartogramů vyřešit nelze. Dokonce pokud povolíme existenci těchto chyb v reprezentaci tvaru a plochy, stále nám zbývá problém obtížné optimalizace, díky kterému jsou současné algoritmy řešící tuto problematiku velmi časově náročné. Problém spojitého kartogramu Problém spojitého kartogramu může být definován jako problém deformace mapy. Vstupem je rovinná polygonální síť (mapa) P a sada hodnot X, jedna pro každý region. Cílem je deformovat mapu P do P’ takovým způsobem, že plocha každého regionu odpovídá jeho přiřazené hodnotě a zároveň je zachován celkový tvar jednotlivých regionů a regiony jsou všechny rozpoznatelné. • Vstup – rovinná polygonální síť P složená z polygonů p1, …, pk – hodnoty X = x1, …, xk, kde xi > 0, ∑xi = 1 – A(pi) označuje normalizovanou plochu polygonu pi, kde A(pi) > 0, ∑A(pi)= 1 • Výstup – Polygonální síť P’ zachovávající topologii, která se skládá z polygonů p1’, …, pk’takových, že funkce f(S’, A’), která je definována jako je minimalizována s shape error area error – i = 1, …, k a w je váhový faktor, 0 ≤ w < 1 Intuitivně zachování topologie znamená, že stěny vstupní sítě musí zůstat stejné, například cyklické pořadí sousedních hran v P musí být stejné i v P’. To se dá formálně vyjádřit tak, že tyto dvě sítě jsou tzv. pseudo-duální (graf, který obsahuje vrchol pro každou stěnu a hranu mezi dvěma vrcholy, pokud jsou odpovídající stěny sousední). Dokonce i jednoduchá varianta kartogramového problému, která ignoruje zachování tvaru (w = 0) je NP-úplným problémem. Protože je téměř nemožné souběžně splnit omezení na tvar a plochu, funkce f, d_s a d_A modelují chybu výsledného kartogramu. Existuje řada algoritmů řešících problém vytváření kartogramů. Avšak kvalita těchto automatizovaných řešení se velmi liší. Jedním z důvodů je, že rovné čáry a pravé úhly jsou velmi důležité při rozpoznávání kartogramů. Radiální metody, jako například konformní mapy navržené Toblerem, radiální expanzní metoda Selvina a spol. nebo čárová integrální metoda Guseyn-Zadeho a Tikunova, neposkytují v řadě případů akceptovatelné výsledky, protože tvary polygonů jsou často silně deformovány.     k i k i ii awswASf 1 1 )1()','( kdessS k },...,{' 1 ),( ' iiSi ppds  kdeaaA k },...,{' 1 ))(,( ' iiAi pAxda  Problém obdélníkového kartogramu Hlavní myšlenkou obdélníkových kartogramů je aproximace známých map pokrývajících dané území pomocí obdélníků a nalezení rozdělení dostupného prostoru obrazovky, kdy plochy obsazené jednotlivými obdélníky jsou určeny proporcionálně vzhledem ke statistickým hodnotám. Abychom podpořili co nejlepší pochopení informace prezentované pomocí takovéhoto kartogramu, jsou obdélníky umístěny co nejblíže jejich původním pozicím a původním sousedům. Problém může být definován jako optimalizační problém se sadou omezení a kritérií optimalizace, včetně plochy, topologie, relativní pozice polygonů, rozměru obdélníka a volného prostoru. Pro různé varianty tohoto problému existují různé algoritmy jejich řešení. Jedním z nich je i tzv. RecMap algoritmus. Zobecnění (generalizace) map Zobecnění mapy ke proces výběru a abstrahování informace z mapy. Využívá se v případech, kdy chceme vygenerovat mapu s menším měřítkem z mapy s měřítkem větším, která obsahuje veškeré detailní informace. Příklady typické generalizace dat jsou následující: - Zjednodušení bodů – odstraňování nebo spojování bodů, které nejsou relevantní nebo nejsou odděleně viditelné na mapě s menším měřítkem - Zjednodušení čar – odstranění malých výkyvů a ohybů nebo spojování čar do středových čar - Zjednodušení polygonů – odstranění malých výkyvů a ohybů při zachování základního tvaru Map labeling Jedná se o umístěná textových nebo obrázkových značek do blízkosti bodů, čar a polygonů. Přestože to vypadá jako jednoduchý a přímočarý úkol, bylo prokázáno, že tomu tak není. Existuje řada různých algoritmů řešících tento problém, které se liší efektivitou, kvalitou výsledků. Tyto algoritmy jsou většinou založeny na heuristických metodách.