Problém průchodnosti terénu a nalezení nejlevnější cesty (rastrová data)

Semestrální práce z předmětu Algoritmy prostorových analýz (KMA/APA)

Tomáš Řehák


1. Úvod
2. Vypracování
2.1. Teoretický základ
2.2. Praktická ukázka
3. Závěrečné zhodnocení
Seznam použitých pramenů a literatury

Abstrakt

Práce se zabývá hledáním tzv. nejlevnější cesty mezi dvěma body na mapě, která je reprezentována rastrovými daty. Nejlevnější cesta je taková, k jejímuž překonání je potřeba nejméně nákladů.

1. Úvod

Hledání nejvhodnější cesty mezi výchozím a cílovým bodem patří mezi jedny z nejzáslužnějších aplikacích v GIS. Požadavky na naplánovanou cestu se mohou lišit, ale obecně chceme najít takovou cestu, která by nás stála nejméně sil a tedy náklady na její překonání by byly co nejmenší.

Podobnou anlýzu lze provádět také nad daty ve vektorové formě. Mým úkolem ovšem bylo zkoumat tuto problematiku s využitím rastrových dat. Práce byla zpracována v prostředí ArcGIS od společnosti ESRI.

V této práci nejprve objasním základní termíny a poté uvedu stručný postup při hledání nejlevnější cesty, který bude doplněn obrázky s výsledky. Ukázka byla provedena nad daty NP Šumava.

2. Vypracování

2.1. Teoretický základ

K práci s rastrovými daty slouží mapová algebra, která je ekvivalentní k nástroji topologického překrytí u dat vektorových. Mapová algebra v sobě zahrnuje matematické operace s rastry a pomocí mapové algebry může docházet ke kombinaci mezi více rastrovými vrstvami. Díky tomuto nástroji provádíme různé prostorové modelování a analyzování. Nástrojem mapové algebry je jazyk mapové algebry, který je definovaný v každém GIS software. Mapová algebra obecně používá:

  • Objekty (slouží k uložení informací; jedná se o vstupní hodnoty a mezivýsledky).

  • Činnosti (příkazy jazyka – funkce; vykonávají operace na objektech).

  • Operátory (matematické,statistické,relační a logické operátory).

Abychom nalezli výslednou nejlevnější cestu mezi dvěma body, musíme nejprve vytvořit povrch nákladů a poté povrch vážené vzdálenosti. Než se zmíním o povrchu nákladů, rád bych ještě objasnil pojem vážené vzdálenosti.

Při stanovení vážené vzdálenosti nehraje roli jen absolutní vzdálenost mezi objekty v terénu (nebo dokonce na mapě), ale mnoho jiných faktorů ovlivňujících přechod z jednoho místa na druhé (viz obr. 1). O tom, kolik energie vydáme na překonání cesty, rozhoduje fakt, jestli jdeme z kopce, nebo do kopce, jestli jdeme po upravené cestě, nebo se probíjíme křovinami, nebo jestli používáme nějaký dopravní prostředek. Vážená vzdálenost tedy vystihuje skutečnou vzdálenost a vypovídá mnohem více o dostupnosti různých cílů z výchozího místa než prosté odměření na mapě. Proto se při analýze dostupnosti místa pro záchranou službu považuje vážená vzdálenost a nikoli přímá vzdálenost vzdušnou čarou. Analýza vážené vzdálenosti vyžaduje vytvoření povrchu nákladů.

Obrázek 1. Vážená vzdálenost

Vážená vzdálenost

Pracujeme s rastrovými daty. Základním stavebním prvkem je tedy rastrová buňka. Po vytvoření povrchu nákladů musí každá buňka vědět, jak drahé je její překonání. Nejprve se započítá faktor rovinné vzdálenosti (každá buňka zná své rozměry). Dále se započítá faktor terénního reliéfu. Jeho úkolem je převedení rovinné vzdálenosti mezi buňkami na vzdálenost po reliéfu. Máme-li určenou vzdálenost po reliéfu mezi výchozím a cílovým bodem, uvažujeme další faktory ovlivňující pohyb v terénu, které můžeme rozdělit na horizontální a vertikální. Vertikální faktor je různý ve směru z místa A do B od směru z místa B do A (snadnější je jít z kopce). Viz obr. 2. Odpovídá povrchu vážených směrů (viz kapitola 2.2).

Obrázek 2. Vliv vertikálního faktoru na váženou vzdálenost

Vliv vertikálního faktoru na váženou vzdálenost

V této práci je pozornost věnována především horizontálním faktorům, které ovlivňují dostupnost k cíli (např. místu nehody). Horizontální faktor udává účinek převládajícího horizontálního směru na energii, kterou musíme vynaložit na překonání buňky. Typickým příkladem horizontálního působení je definování převládajících vzdušných, nebo vodních proudů. V našem příkladě je nejdůležitějším horizontálním faktorem povrch, po kterém se pohybujeme. Na základě povrchu definujeme, jestli se pohybujeme pomocí sanitky, nebo pěšky a jakou rychlostí. Ohodnotíme-li jednotlivé typy povrchů vznikne povrch nákladů z horizontálních faktorů. Tento polohopisný povrch nákladů je ukázán na obrázku č. 3

Obrázek 3. Ukázka povrchu nákladů s ohodnocenými prvky polohopisu

Ukázka povrchu nákladů s ohodnocenými prvky polohopisu

Výsledný povrch nákladů (vzniklý z polohových a výškových dat) je počítán jako funkce všech faktorů, protože každý z výše jmenovaných faktorů nabývá jiných hodnot v jiných jednotkách. Sestavení funkce je klíčové pro celou práci a výsledky práce jsou závislé především na správném uvážení vah jednotlivých faktorů a sestavení takového vzorce - funkce, která váhy jednotlivých faktorů co nejlépe zohledňuje.

Z povrchu nákladů se počítá povrch vážené vzdálenosti, ze kterého se již lehce určí nejlevnější cesta mezi místem výjezdu a cílovým bodem. K určení povrchu vážené vzdálenosti je třeba znát výchozí bod. V tomto bodě má povrch váženné vzdálenosti minimum. Od cílového bodu povrch stoupá na všechny strany a rychlost stoupání je závislá na povrchu nákladů. Vzniká tak jakýsi trychtýř, který je ale nepravidelný a který ma dno (jedno, nebo více) v cílových bodech. Pro ujasnění situace dodám, že kdybychom brali jako faktor překonání vzdálenosti jen vzdálenost absolutní, byl by trychtýř dokonale hladký. Povrch vážené vzdálenosti na následujících obrázcích byl vypočten z povrchu nákladů na obrázku č. 3.Ukázku ohodnoceného rastru (povrchu vážené vzdálenosti) zobrazuje obrázek č.4. Grafický model vytvořený nad tímto rastrovým ohodnocením je zobrazen na obrázku č. 5. Prosterový graf je pouze ilustrativní. Ve skutečnosti se jedná o GRID a graf je tak nespojitý, neinterpolovaný jako na obrázku č.5. Barvy na zmíněném obrázku odpovídají interpolovaným hodnotám povrchu vážené vzdálenosti podle rozdělení v legendě.

Obrázek 4. Ukázka povrchu vážené vzdálenosti

Ukázka povrchu vážené vzdálenosti

Obrázek 5. Graf povrchu vážené vzdálenosti

Graf povrchu vážené vzdálenosti

Každá buňka povrchu vážené vzdálenosti ví, kudy se dostat do cílového bodu nejrychleji. Algoritmus z vybrané buňky postupuje tak, „aby to bylo co nejvíce z kopce“, tj. nejrychleji do dna trychtýře. V našem případě, jak se nejrychleji dostat do nemocnice. Tento postup souhlasí s principem hledání nejlevnější cesty, jakožto hlavním úkolem naší práce. Jen je třeba úlohu obrátit: Postupujeme od cílového bodu do okolí a hodnotíme jak rychle se dostane záchranka na libovolné místo v okolí na základě povrchu vážené vzdálenosti. Při tomto je hledána nejlevnější cesta k požadovanému bodu.

2.2. Praktická ukázka

Příklad, který byl teoreticky popsán v předchozí kapitole byl prakticky aplikován na data Národního parku Šumava. Postup využívá funkcí Spatial Analyst Tools ArcToolboxu. Nejdůležitější a stěžejní částí je vytvoření správného povrchu nákladů. Vytvoření povrchu vážené vzdálenosti a vyhledání nejlevnější cesty se poté stává otázkou jedné, respektive dvou operací.

Při postupu bylo nejprve nutné vybrat potřebné vrstvy ze ZABAGED a omezit je na zadanou lokalitu. Vybrané polohopisné vrstvy jsou uvedeny v obr. č. 4. Navíc bylo třeba pracovat s vrstevnicemi a teréními zlomy oblasti NP Šumava. Dalším úkolem bylo vektorové vrstvy polohopisu převést na rastrové. Velikost buňky jsme zvolili 5 x 5 metrů. Výšková data byla využita na vytvoření výškového rastru a povrchu sklonů reliéfu.

Nejprve jsme pracovali s vrstvami polohopisu. Každou vrstvu bylo nutné ohodnotit celým číslem, které by představovalo relativní náročnost překonání vzhledem k ostatním druhům buňek. Při ohodnocení bylo postupováno tak, že se určila průměrná rychlost pohybu po daném druhu buňky a vzhledem k rychlosti sanitky po dálnici ( tj. nejmenší hodnota překonání buňky = 1) byla nepřímou úměrou vypočtena další celočíselná ohodnocení překonání ostatních buněk. Výsledná tabulka ohodnocení vrstev polohopisu je zobrazena na obr. č. 6.

Obrázek 6. Postup a ohodnocení vrstev polohopisu

Postup a ohodnocení vrstev polohopisu

K ohodnocení rastrových buněk jsme použili funkcí Reclassify (nahradí původní hodnoty rastru za nové tj.definované uživatelem a nulové, tam, kde se prvek nevyskytuje) a Raster Calculator. Pomocí tohoto nástroje vytvoříme ucelený rastr nákladů sečtením hodnot prvků (buněk každého prvku) a hodnot nulových, tam kde se prvek v rastru nevyskytuje.

Nyní máme vytvořený povrch nákladů, do něhož jsme započítali pouze horizontální faktory. Ovšem do povrchu nákladů musí vstupovat také vertikální faktory. Především sklon svahu, na němž závisí i velikost buňky promitnutá do terénu. Musíme tedy do hodnot rastru povrchu nákladů započíst i tento faktor. Empiricky jsme odvodili, že situaci velmi dobře popisuje tato funkce: ((0,25*([sklon svahu]+1))*[horizontalní hodnoty])/2. Tuto funkci jsme vytvořili na základě hodnot svahovitosti (0-45) a dále jsme hledali vhodný vztah, který by zohlednil fakt, že svahovitost nám nevadí v případě jízdy autem (malé hodnoty horizontálního ohodnocení) a jsou nepříjemné zvláště při chůzi (vyšší hodnoty horizontálního ohodnocení).

Jak vypadá výsledný povrch nákladů zobrazuje obr. 7. Z uvedeného ohodnocení je zřejmé, že jako nepřekonatelné (tmavé) se jeví řeky a vodní plochy. Naopak cesty jsou s ohledem na předpokládaný pohyb záchrankou s nejmenšími hodnotami charakterizující náročnost překonání buňky (světlá místa).

Obrázek 7. Výsledný povrch nákladů

Výsledný povrch nákladů

Máme-li vytvořený povrch nákladů musíme na mapě určit výjezdové body záchranné služby, abychom mohli vytvořit povrch vážené vzdálenosti se dny právě v těchto výjezdových bodech. V národním parku Šumava jsem jako výjezdové body zvolil centra obcí Horská Kvilda a Modrava. Pro výjezdové body vytvoříme samostatný shapefile. Před spuštěním funkce na vytvoření povrchu vážené vzdálenosti je nejprve nutné nadefinovat v nastavení (Options) Spatial Analystu oblast, na kterou se bude výpočet vztahovat. Vytvořili jsme si proto obal (pomocí funkce Buffer) kolem národního parku a výpočet provedl nad ním.

Povrch nákladů vytvoříme funkcí ve Spatial Analystu: Cost Weighted, kterou nalezneme v menu Distance. Tato funkce vytvoří vytvoří kromě Cost distance raster (povrch vážené vzdálenosti - obr. 8) také Cost direction raster (povrch vážených směrů) a pokud uživatel vyžaduje, tak také Cost allocation raster (ohraničí území pro jednotlivá dna povrchu nákladů). Tyto rastry se následně použijí pro analýzu „nejkratší“ vzdálenosti.

Obrázek 8. Povrch vážené vzdálenosti

Povrch vážené vzdálenosti

Nyní již máme vše připravené na zadání místa nehody a nalezení nejlevnější cesty. Místo nehody (cíl dojezdu) uložíme jako bod do samostatného shapefile a spustíme funkci Shorthest Path, která se nachází také v menu Spatial Analyst - Distance. Do dialogového okna je třeba zadat kromě shapefile s místem nehody povrch vážené vzdálenosti a povrch vážených směrů.

Obrázek 9. Vyhledání nejlevnější cesty

Vyhledání nejlevnější cesty

Na závěr je vhodné dodat, že postupy je vhodné vytvořit v Model Builder, aby mohl být uvedený postup aplikován pro různé oblasti, pro různá výjezdová místa záchranky a s jinými hodnotami, které byly používány při tvorbě povrchu nákladů. V této práci byl vytvořen model na zádávání hodnot při ohodnocování druhů povrchů (ukázka viz obr.9). Při tvorbě ostatních kroků uskutečňující samotné nalezení nejlevnější cesty v Model Builder (viz obr.10) je třeba zmínit, že funkce, které jsou v tomto modelu použity a některé jejich mezivýsledky mají jiné názvy. V Model Builder je třeba použít funkce, které nabízí Spatial Analyst v ArcToolbox a tyto funkce se nepatrně liší od funkcí ve Spatial Analystu umístěném v hlavním menu Programu ArcMap. Funkce Cost Weighted, kterou jsme výše vytvořily povrch nákladů (a další povrchy), odpovídá funkci z ArcToolboxu pod názvem Path Distance a výše zmíněnou funkci Shortest Path nalezneme v ArcToolboxu Spatial Analystu pod názvem Cost Path (obr. 10).

Obrázek 10. Ukázka části modelu pro reklasifikování polohopisných rastrových prvků

Ukázka části modelu pro reklasifikování polohopisných rastrových prvků

Ukázka výsledné nejlevnější cesty je zobrazena na obrázku č. 11.

Obrázek 11. Ukázka nalezení nejlevnější cesty nad povrchem rastrů

Ukázka nalezení nejlevnější cesty nad povrchem rastrů

3. Závěrečné zhodnocení

Práce poukázala na jednu z metod nalezení nejlevnější cesty mezi dvěma body na mapě. Pracovali jsme výhradně s rastrovými daty (původní vektorová data byla převedena narastrová). Další z možností jak nalézt nejlevnější cestu je nad provést tuto analýzu nad daty vektorovými. Touto úlohou se blíže zabýval David Velhartický a vzhledem k charakteru dat využívá jiné prostředky pro určení nejlepší dostupnosti k cíli. Jeho práce je obdobně jako tato součástí referátů z předmětu KMA/APA.

Na rozdíl od síťových analýz, prováděných nad vektorovými daty pokryjeme výše uvedeným postupem celé zájmové území a nejen komunikační siť. Ovšem práce s rastrovými daty je polohově méně přesnější (záleží na rozměru buňky) a práce s rastrovými daty je také paměťově a výpočetně náročnější.

Jsem si vědom, že některé části práce by si zasloužily hlubší analýzu, která by jistě zpřesnila zkoumanou problematiku. Obzvlášť nalezení výsledné funkce pro vytvoření povrchu nákladů by zasluhovalo podrobnější zkoumání a porovnání výsledků s jinými funkcemi, ovšem pro názornost a potřeby této práce je toto dostačující.

Seznam použitých pramenů a literatury

Knihy

[1] Tuček , Ján . Geografické informační systémy – principy a praxe, Computer Press, 1998. 424 s. ISBN: 80-7226-091-X.

Články z internetu

[2] Úvod do geografických informačních systémů. [online]. KMA, FAV, Západočeská univerzita v Plzni12.2.2005. Dostupné z: < http://www.gis.zcu.cz/studium/ugi/elearning/index1.htm >.