Tvorba navigace v rámci budov MU

MASARYKOVA UNIVERZITA FAKULTA INFORMATIKY

Tvorba navigace v rámci budov MU

DIPLOMOVÁ PRÁCE

Bc. Vladislav Tesařík

Brno, podzim 2012

Prohlášení Prohlašuji, že tato 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: Mgr. Martin Vytrhlík

ii

Poděkování Děkuji vedoucímu práce Mgr. Martinu Vytrhlíkovi za vstřícnost a trpělivost, za zajímavé téma práce a za odpovědné vedení. Rovněž děkuji své manželce za vytrvalou podporu.

iii

Shrnutí Tato práce se zabývá využitím teorie grafů při navigaci, základními algoritmy pro hledání minimální cesty a geografickými informačními systémy, obzvláště pak systémem ArcGIS Desktop. Dále také seznamuje se stavebním pasportem Masarykovy univerzity, v rámci kterého jsou uchovávána data o univerzitních budovách. Právě stavební pasport Univerzitního kampusu Bohunice byl v rámci této práce analyzován pro možnost navigace. Geografická data byla doplněna o prvky pro zobrazování cest, nad těmito prvky byly vytvořeny vyhledávací struktury umožňující nalezení cesty mezi dvěma místnostmi. K dispozici je i možnost vizualizace cesty v aplikaci ArcGIS Desktop. Cesta může být vyhledána i jako bezbariérová.

iv

Klíčová slova ArcGIS, navigace, Univerzitní kampus Bohunice, stavební pasport

v

Obsah 1 Úvod..............................................................................................................................................2 2 Role teorie grafů v navigaci........................................................................................................3 2.1 Základní pojmy teorie grafů...............................................................................................3 2.2 Využití grafů při navigaci...................................................................................................5 2.3 Problém hledání minimální cesty......................................................................................6 2.3.1 Dijkstrův algoritmus...................................................................................................6 2.3.2 Algoritmus Floyda a Warshalla.................................................................................7 2.3.3 Dálniční hierarchie......................................................................................................9 3 Geografické informační systémy.............................................................................................11 3.1 ArcGIS Desktop.................................................................................................................15 4 Stavební pasport MU.................................................................................................................19 4.1 Struktura dat Stavebního pasportu.................................................................................20 4.2 Prezentace dat....................................................................................................................23 5 Navigace v rámci budov MU...................................................................................................24 5.1 Zobrazení cesty mezi dvěma místnostmi.......................................................................24 5.2 Sestavení vyhledávacích struktur....................................................................................33 5.3 Vyhledávání cest................................................................................................................35 5.4 Ukázky vyhledaných cest.................................................................................................38 6 Závěr...........................................................................................................................................43 A Seznam elektronických příloh.................................................................................................45

1

Kapitola 1

Úvod Oddělení pasportizace Ústavu výpočetní techniky Masarykovy univerzity spravuje stavební pasport jejích budov. Data, která stavební pasport obsahuje, se vybízí využít pro orientaci v tak rozsáhlých budovách, jako je Univerzitní kampus Bohunice – komplex budov propojených chodbami. Cílem této práce bylo analyzovat možnost využití dat právě stavebního pasportu pro implementaci navigace a realizovat takovou implementaci, která umožní hledání cest v rámci kampusu a jejich zobrazení, potažmo i vyhledání cesty vhodné pro vozíčkáře. Ve druhé kapitole jsou popsány základní pojmy teorie grafů. Práce sice není zaměřena přímo na grafy, ale při navigaci tato teorie hraje velkou roli. Podstatou navigace v této práci je vlastně hledání minimálních cest, čímž se teorie grafů také zabývá. Kapitola uvádí základní algoritmy a přístupy k problému hledání minimálních cest a dva tyto algoritmy formálně popisuje. Implementace jednoho z nich je totiž později zvolena pro zpracování dat z pasportu. Třetí kapitola pojednává o geografických informačních systémech a jejich využití. Uvádí se zde příklady prezentace geografických dat na internetu, odkazy na užitečné mapové služby a představen je i systém ArcGIS Desktop, se kterým je nutné při analýze dat pracovat. V této aplikaci jsou totiž data stavebního pasportu uložena a ve spolupráci s ní tvoří originální geografický informační systém. Tématem čtvrté kapitoly je již zmíněný Stavební pasport Masarykovy univerzity. Ten obsahuje několik typů dat, jejichž vizualizací jsou plány jednotlivých podlaží. Data Stavebního pasportu identifikuje tzv. polohový kód, s jehož strukturou tato kapitola také seznamuje. Důležité pro navigaci budou polohové kódy místností a vazby místností na dveře. Pátá kapitola se věnuje samotné analýze dat univerzitního kampusu. Podrobně popisuje tvorbu prvků přidaných do mapy pro zobrazení cesty, dále sestavení vyhledávacích struktur a nakonec postup vyhledání cesty a její vizualizaci v aplikaci ArcGIS Desktop.

2

Kapitola 2

Role teorie grafů v navigaci 2.1 Základní pojmy teorie grafů Úvodem je třeba vymezit základní pojmy teorie grafů, neboť ta umožňuje reprezentaci různých typů sítí a jejich analýzu: •

Grafem v této teorii je uspořádaná dvojice (V, E), kde V je konečnou množinou vrcholů a E množinou 2-prvkových podmnožin V zvaných hrany.

•

Orientovaný graf je graf, kde E⊆V ×V , hrana v takovém grafu tedy může vést z vrcholu u do vrcholu v, aniž by vedla z vrcholu v do vrcholu u.

•

Ohodnocený graf má navíc váhovou funkci w : E ℝ , která může vyjadřovat vzdálenost, cenu, kapacitu dané hrany atd.

•

Graf H =W , F  je podgrafem grafu G=V , E , jestliže W ⊆V a F ⊆E .

•

Sled délky

k ∈ℕ 0

v grafu

G=V , E 

je konečná posloupnost vrcholů

v 0 ,... , v k ∈V takových, že ∀ i=1,... , k : v i−1 v i∈E . Značení sledu je následující: k

p : v 0  v k … sled p délky k z v0 do vk ∗

p : v 0  v k … sled p z v0 do vk •

Tah délky k ∈ℕ 0 v grafu G=V , E je sled vrcholů v 0 ,... , v k ∈V takových, že hrany v i−1 v i jsou po dvou různé.

•

Cesta délky k ∈ℕ 0 v grafu G=V , E  je tah, jehož vrcholy v 0 ,... , v k ∈V jsou po dvou různé.

•

Vzdálenost z u do v ∈V v grafu G=V , E  :

{

{

k

}

d u , v = min k∣∃ p :u  v ∗ ∞ , pokud ¬∃ p : u  v Slovy se tedy jedná o délku nejkratšího sledu mezi u a v, pokud takový sled neexistuje, je vzdálenost rovna nekonečnu. •

Souvislost grafu – graf G=V , E je souvislý, jestliže ∀ u , v∈V : d u , v ≠∞ .

3

Mezi každými dvěma vrcholy souvislého grafu tedy existuje sled. •

Komponenta (souvislosti) grafu G=V , E je jeho maximální souvislý podgraf. Graf, který čítá jednu komponentu je tedy souvislý. Graf může být reprezentován různými způsoby, nejčastěji se jedná o grafickou

reprezentaci, o seznam následníků či o reprezentaci maticí sousednosti, resp. vzdáleností. Na příklad orientovaný graf G={v 0, v 1, v 2, v 3 },{v 0 v 2 , v 0 v 3 , v1 v 0 , v 1 v 3 , v 2 v 3 , v 3 v 1 , v 3 v 2 } je ze svého formálního zápisu na první pohled těžko představitelný, užitím uvedených způsobů reprezentace se však dá představit snáze. V grafické reprezentaci jsou hrany znázorňovány šipkami, v matici sousednosti A je potom prvek aij roven 1, pokud existuje hrana z vrcholu vi do vrcholu vj, jinak je roven nule. V matici vzdáleností ohodnoceného grafu jsou místo jedniček uvedeny váhy příslušných hran, na diagonále jsou nuly a pokud z vi do vj hrana nevede, je aij nekonečno.

v0

v1

v2

v3

Obrázek 2.1: Grafická reprezentace

Obrázek 2.2: Reprezentace grafu G

grafu G

maticí sousednosti

Zmíněný seznam následníků by pro vzorový graf G vypadal takto:

v 0 :v 2, v 3 v 1 :v 0, v 3 v 2 :v 3 v 3 :v 0, v 1 Jedná se tedy o výčet sousedů pro každý z vrcholů grafu.

4

2.2 Využití grafů při navigaci Člověk se může přepravovat z místa na místo různými způsoby. Vlaky využívají železniční síť, chodci síť chodníků, stezek, ale i silnic, cyklisté síť silnic a cyklostezek, automobily síť silnic. Pro následující jednoduchou demonstraci využití grafů při navigaci byla zvolena právě síť silniční. Tu je možné reprezentovat grafem, ve kterém vrcholy představují města, respektive křižovatky, a hrany spojují ty vrcholy (tedy ta města a ty křižovatky), které jsou spolu přímo spojeny silnicí. Obrázek 2.3 ilustruje taková propojení měst na mapě České republiky.

Obrázek 2.3: Silniční síť ČR (převzato z http://www.mdcr.cz/mdcr/flash/rocenka_02) Hrany grafu je vhodné ohodnotit vzdálenostmi mezi propojenými vrcholy (tj. délkou úseku silnice, který hrana reprezentuje). Rozdělí-li se hrany navíc na úseky dle maximální povolené rychlosti, lze z tohoto údaje čas potřebný na překonání daného úseku dopočítat. Protože se však maximální povolené rychlosti na stejném úseku v různých smě-

5

rech mohou od sebe lišit, ale hlavně proto, že existují i silnice jednosměrné, je nutné silniční síť reprezentovat grafem orientovaným. Tím se totiž při vyhledávání zabrání nalezení takové trasy, která by na některém ze svých úseků vedla v protisměru. Pokud je k dispozici takový graf nějaké oblasti pokud možno v co nejaktuálnější podobě, lze s jeho pomocí nalézt v rámci dané oblasti nejkratší či nejrychlejší cestu z výchozího bodu do cíle.

2.3 Problém hledání minimální cesty

Nechť graf G=V , E , w  má hrany ohodnoceny funkcí w : E  ℝ . Hodnota w uv  se nazývá váhou hrany

uv . Váha cesty

p=v 0, v 1, ... , v k

se potom vypočítá jako

k−1

w  p =∑ w v i−1 v i  . Jedná se tedy o součet všech vah hran, přes které cesta vede. i=1

Nejkratší (minimální) cestou mezi dvěma vrcholy x a y je ze všech možných cest mezi x a y ta s nejmenší váhou. Váhu cesty mezi dvěma vrcholy lze rovněž nazývat vzdáleností těchto dvou vrcholů. Hledání minimální cesty je problémem, kterým se zabývá řada algoritmů, klasickým příkladem je algoritmus Dijkstrův či algoritmus Floyda a Warshalla.

2.3.1

Dijkstrův algoritmus

Algoritmus navržený nizozemským informatikem Edsgerem Wybe Dijkstrou najde v orientovaném grafu G=V , E , w  s nezáporným ohodnocením hran minimální cesty z daného vrcholu u ∈V do všech vrcholů grafu. Postupuje tak, že má v každém kroku množinu U ⊆V , jejímiž prvky jsou vrcholy s již spočítanými vzdálenostmi, a pro každý vrchol v ∉U hodnotu t v  , což je délka nejkratší cesty z u do v jdoucí pouze přes vrcholy z U . Na začátku je výchozí vrchol u vložen do množiny U a nastaví se vzdálenost

d u , u=0 a t v  pro ostatní vrcholy z V následujícím způsobem:

{

t v = w uv  ∞

pro uv∈E pro uv∉E

Dokud nejsou spočítány vzdálenosti z u do všech vrcholů, opakuje algoritmus krok, ve kterém vybere libovolný vrchol v ∉U s minimální hodnotou t v  a provede: 1.

U :=U ∪{v }

6

2.

d u , v =t v  ∀ x∈V ∖ U : t  x :=mint  x , t v w vx  3. Časová složitost Dijkstrova algoritmu je O∣E∣∣V ∣⋅log∣V∣ v implementaci pro řídké grafy, avšak O∣V ∣2∣E∣ v implementaci pro grafy husté. Obrázek 2.4 ilustruje postup algoritmu, počáteční bod je na něm značen jako s .

Obrázek 2.4: Postup hledání minimálních cest Dijkstrovým algoritmem (převzato z http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap25.htm)

2.3.2

Algoritmus Floyda a Warshalla

Na rozdíl od Dijkstrova algoritmu, který hledal nejkratší cesty z daného vrcholu do všech vrcholů grafu, hledá algoritmus Floyda a Warshalla nejkratší cesty mezi všemi dvojicemi vrcholů grafu, a to i v grafu se záporně ohodnocenými hranami (ovšem bez záporných cyklů). Vstupem je matice vzdáleností W prohledávaného grafu s vrcholy v 1 ,... , v n . k V jednotlivých krocích algoritmus počítá matice D k (kde k =0,1, ... , n a d ij vyjadřuje

délku cesty z vrcholu v i do vrcholu v j jdoucí pouze přes vrcholy v 1 ,... , v k ) tímto způsobem:

d ijk =

{

wij pro k =0 k−1 k −1 k−1 min  d ij ; d ik d kj  pro k 0

Výsledná D n je matice délek nejkratších cest mezi jednotlivými vrcholy. Časová složitost algoritmu je O∣V ∣3  . Pro získání informace, přes které vrcholy nejkratší cesty povedou, je třeba v každém kroku vypočítat také tzv. matici předchůdců P k takto:

{

p 0ij = nil i

{

k −1

pro i= j ∨ w ij =∞ pro i≠ j ∧ wij ∞ k−1

k−1

k−1

p = p ijk −1 pro d ijk−1 ≤ d ikk−1d kjk−1 p kj pro d ij  d ik d kj k ij

7

n V konečné matici P n pak p ij znamená index posledního vrcholu před v j na

nejkratší cestě mezi v i a v j . Postupným zjišťováním předchůdců cíle lze tedy dohledat celou minimální cestu. Počítání matic předchůdců má rovněž časovou složitost O∣V ∣3  .

v2 3

4 8

v1 7 -4

v3 1

2

v5

-5

6

v4

Obrázek 2.5: Ohodnocený graf Pro graf na obrázku 2.5 by matice při provádění algoritmu Floyda a Warshalla vypadaly následovně:



0 ∞ 0 W =D = ∞ 2 ∞



3 8 ∞ −4 0 ∞ 1 7 5 4 0 ∞ ∞ ,D = ∞ −5 0 ∞ ∞ ∞ 6 0



nil 3 4 4 nil 4 P 5= 4 3 nil 4 3 4 4 3 4



0 1 −3 2 −4 3 0 −4 1 −1 7 4 0 5 3 , 2 −1 −5 0 −2 8 5 1 6 0

5 1 2 1 2 1 nil 1 5 nil



Z matice D 5 je patrné, že nejkratší cesta z vrcholu v 3 do vrcholu v 5 má délku 3. Samotná cesta se postupně konstruuje z matice P 5 :

v 3 ... v 5 v 3 ... v 1−v 5 ⋮ v 3−v 2−v 4−v 1−v 5

Hledá se předposlední vrchol na cestě. Hledá se předposlední vrchol na cestě z v 3 do v 1 atd. Jakmile je výsledkem hledání výchozí vrchol, je celá cesta zkonstruována.

8

2.3.3

Dálniční hierarchie

Hledání minimální cesty v rozsáhlých grafech (např. silniční síť Evropy) může být časově velice náročné. Pokud se navíc v krátkém čase na minimální cestu vyskytne více požadavků, jako tomu je např. na mapových serverech typu Google Maps, je nutné proces hledání nějakým způsobem optimalizovat. Jako řešení se nabízí tzv. dálniční hierarchie. Je-li např. v Evropě hledána trasa mezi dvěma místy nacházejícími se ve dvou různých státech, základní použití Dijkstrova algoritmu by si vynutilo práci nad celou evropskou silniční sítí. Optimalizace formou dálniční hierarchie je založena na tom, že stát má oproti počtu silnic výrazně menší počet hraničních přechodů [1]. A protože se některými státy na cestě pouze projíždí, není nutné znát jejich celou silniční síť, ale postačí pouze znalost minimálních cest mezi jeho hraničními přechody. Pokud se tyto základní cesty předem vypočítají, nalezení celkové minimální cesty se tím podstatně zrychlí. V první fázi se totiž budou hledat minimální cesty z výchozího místa k hraničním přechodům výchozího státu, ve druhé fázi se vyhledají minimální cesty z těchto hraničních přechodů do hraničních přechodů cílového státu a ve fázi třetí minimální cesty z hraničních přechodů cílového státu do cílového místa. Složením výsledků všech tří fází vznikne acyklický orientovaný graf o mnohem menším počtu vrcholů, lze v něm tedy mnohem rychleji (v lineárním čase) vyhledávat.

Obrázek 2.6: Síť bez hierarchie

Obrázek 2.7: Síť s hierarchií

Převzato z http://computer.howstuffworks.com/routing-algorithm5.htm Dálniční hierarchie může být i víceúrovňová, státy se mohou dále dělit např. na

9

kraje či jiné územní jednotky, důležité je, aby každá taková jednotka měla co nejméně „hraničních přechodů“. Obrázky 2.6 a 2.7 ukazují příklad vytvoření hierarchie na grafu. Uvedený způsob optimalizace je možné vztáhnout i na hledání cest v rámci rozsáhlých budov či celých jejich areálů (př. Univerzitní kampus Bohunice). Budovy totiž mívají zpravidla nízký počet východů a mezi podlažími rovněž nevede mnoho cest (řádově jednotky schodišť a výtahů). Dálniční hierarchii složitějšího komplexu budov lze tedy konstruovat tak, že vstupy do budov a schodiště či výtahy uvnitř nich budou zastávat stejnou roli, jakou zastávají hraniční přechody mezi státy v dálniční hierarchii výše zmíněné evropské silniční sítě.

10

Kapitola 3

Geografické informační systémy Informační systém lze chápat jako systém vzájemně propojených informací a procesů, přičemž pod pojmem procesy se rozumí funkce, které zpracovávají informace do systému vstupující a transformují je na informace ze systému vystupující [2]. Procesy jsou zjednodušeně řečeno funkce zabezpečující sběr, přenos, uchování, zpracování a prezentaci informací. Geografickým informačním systémem (dále jen GIS) je pak informační systém pracující s prostorovými informacemi [3], respektive s daty vztaženými k povrchu zemskému.

GIS

s prostorovými

je

vztahy

především mezi

analytickým

objekty.

nástrojem

Zpravidla

zahrnuje

umožňujícím možnost

pracovat

vizualizovat

uchovávaná data do podoby map či modelů zemského povrchu. Mapa je totiž základním prostředkem pro sdílení geografických dat, její formou lze přehledně prezentovat velké množství informací různého typu. GIS tak zasahují do mnoha oborů, kromě tzv. geověd (geografie, geodézie, kartografie...) také do matematiky, informatiky a dalších. Uplatnění najdou při územním plánování, demografických výzkumech, ochraně proti přírodním katastrofám, řešení krizových situací, distribuci energií a vody, studiu životního prostředí, u lesnictví, zemědělství, v meteorologii, při výuce...

11

Obrázek 3.1: Ukázka z prohlížeče soustavy Natura 2000, červeně jsou Ptačí oblasti, modře Evropsky významné lokality (převzato z http://natura2000.eea.europa.eu) Mnoho GIS poskytuje tzv. veřejné mapové služby. Výstupem takových služeb je počítačová mapa, se kterou mohou uživatelé interaktivně pracovat. Běžně jsou u těchto map k dispozici ovládací prvky jako ukazatel severu, posuvník pro přibližování a oddalování pohledu a s tím související měřítko. GIS jsou samozřejmě schopny uchovávat i historická data, v takovém případě pak je možné prohlížet také vývoj mapy v čase. Interaktivní počítačová mapa je součástí např. soustavy chráněných území Natura 2000, která má za cíl chránit nejvíce ohrožené či vzácné druhy živočichů a rostlin na území Evropské unie. V rámci této soustavy jsou evidovány 2 typy území – Ptačí oblasti a Evropsky významné lokality. Tato území je možné najít na webu v prohlížeči soustavy Natura 2000 s tím, že červeně šrafované jsou Ptačí oblasti a modře Evropsky významné lokality. Dalším příkladem mapové služby je aplikace CrimeMapping, která mapuje kriminalitu ve městech USA a ve které lze identifikovat ohniska různých typů kriminální činnosti. Aplikace si dává za cíl zvýšit ostražitost občanů a tím pomoci policejním stanicím snížit kriminalitu. Při stěhování také může být dobrým ukazatelem, do jaké čtvrti se raději nestěhovat.

12

Obrázek 3.2: Ukázka aplikace CrimeMapping. V mapě je zanesena kriminální činnost ve městě Miami ze dne 26. 4. 2012 (převzato z http://www.crimemapping.com/map.aspx?aid=0e08f633ec2e-4579-a612-3f050ea76d8d) Veřejné mapové služby lze ale najít také u nás. Kupříkladu Ředitelství silnic a dálnic ČR v rámci projektu Jednotného systému dopravních informací pro ČR (JSDI) provozuje Dopravní portál ČR. Na něm se nacházejí informace o uzavírkách a událostech na pozemních komunikacích, sjízdnost v zimě, povětrnostní podmínky, u některých úseků silnic i stupně provozu či kamerové snímky. Ty využívá např. Policie ČR, Hasičský a záchranný sbor ČR, zdravotnické záchranné služby, správci komunikací, ale i rozhlas či televize. Návštěvník portálu může také událost (nehodu či uzavírku) nahlásit. Ta se brzy objeví v mapě ostatním uživatelům služby (ověřeno autorem práce).

13

Obrázek 3.3: Ukázka z Dopravního portálu ČR, na snímku je obchvat města Brna směrem ku Praze (převzato z http://www.dopravniinfo.cz) Užitečné služby na svém webu poskytuje také Český hydrometeorologický ústav (ČHMÚ). Mezi ty nejvýznamnější patří aktuální mapa srážek na území ČR měřených radarem každých 15 minut a Hlásná a předpovědní povodňová služba, v rámci které jsou evidovány a předpovídány stavy hladin a průtoky řek. Mapa na obrázku 3.4 zahrnuje data z období sucha na jaře roku 2012.

14

Obrázek 3.4: Mapa míst sledování vodního stavu a průtoku řek (převzato z http://www.chmi.cz) Různorodost uvedených příkladů naznačuje, že geografickou informaci lze přiřadit prakticky jakémukoliv typu dat. V úvodu kapitoly zmíněné funkce GIS je schopna naplnit řada komplexních systémů. Z volně dostupného software jsou to např. GRASS (Geographic Resources Analysis Support systém) nebo Quantum GIS, z komerčních systémů potom např. Autodesk Infrastructure Map Server, Intergraph GeoMedia, GE SmallWorld GeoSpatial Server či Esri ArcGIS. V posledně jmenovaném systému jsou ukládána také data Stavebního pasportu MU (který je představen v kapitole 4), proto následuje stručný popis tohoto systému.

3.1 ArcGIS Desktop ArcGIS Desktop od firmy Esri je softwarový balík, který umožňuje shromažďování, využívání a správu geografických informací. Zahrnuje komplexní sadu nástrojů pro provádění běžných úloh GIS, jako je práce s mapami, sběr dat, analýza, správa geodatabáze a sdílení geografických dat. Ta se v rámci ArcGIS ukládají v tématických vrstvách (např. vrstva ulic, administrativních celků, řek...), které jsou tvořeny strukturami běžnými pro GIS. Těmi mohou být sady prvků stejného typu (Feature datasets), sady rastrových dat (Raster datasets) či tabulky atributů a popisných informací o geografických datech v rámci uvedených sad.

15

Obrázek 3.5: Ukázka vrstvy ulic reprezentované 4 sadami (Feature datasets): body, linie, polygony a popisky ulic (převzato z http://help.arcgis.com/en/arcgisdesktop/10.0/help/00v2/00v20000000r000000.htm) Součástí balíku ArcGIS Desktop je také bohatá sada nástrojů pro tzv. geoprocessing – provádění operací nad geografickými daty, jejichž výstupem jsou nová data. Užitím geoprocessingu lze modelovat a analyzovat geografická data a automatizovat různé úlohy GIS. Jednotlivé úlohy je možné buď spouštět jednotlivě prostřednictvím uživatelského rozhraní ArcGIS Desktop, nebo je zapsat jako příkazy skriptu v jazyce Python. K tomu je určený balík ArcPy, který tyto úlohy pro práci s geografickými daty zapouzdřuje. Jedním z těchto nástrojů je také tzv. „Network Analyst“, který umožňuje tvorbu a analýzu sítí. S pomocí tohoto nástroje lze odpovědět na otázky typu: ke kterým domům je dojezdnost do pěti minut od nejbližší požární stanice, kde se nachází nejbližší bankomat, které auto policejní hlídky se nejdříve dostane do místa nějakého incidentu, kde je nejvhodnější místo pro otevření nové restaurace, ale hlavně jaká je nejkratší či nejrychlejší cesta z jednoho místa na druhé [5]. Firmy i jiné instituce mohou s pomocí tohoto nástroje dosáhnout svých cílů mnohem efektivněji, neboť jsou schopny činit lepší strategická rozhodnutí. Síť je tímto nástrojem chápána jako systém vzájemně propojených prvků, což

16

odpovídá definici grafu dle teorie grafů (viz podkapitola 2.1). Takovouto sítí mohou putovat lidé, zdroje či zboží, automobily po silnicích, voda v trubkách... ArcGIS rozlišuje dvě kategorie sítí: geometrické sítě a tzv. síťové datasety. V geometrické síti může médium procházet po hranách v jednom momentě pouze jedním směrem a nemůže se samo rozhodnout, který směr to bude. Do této kategorie tedy spadají říční sítě (s vodou coby médiem), u kterých je směr toku řízen zemskou přitažlivostí, nebo inženýrské sítě, kde směr mohou řídit technici. V síťových datasetech si naopak médium většinou směr pohybu určit může, transportní sítě (ulice, chodníky, železnice, řeky s loděmi coby médiem) jsou tedy součástí této kategorie. Síťové datasety mohou být vytvořeny jak pro jediný typ přepravy, tak i pro kombinaci různých typů (pak se nazývají multimodálními). Datasety mohou být také trojrozměrné a modelovat tak cesty uvnitř budov, jeskyní atp. Při hledání nejkratší cesty mezi různými podlažími lze použít omezení, díky kterým se algoritmus vyhne schodištím (cesta vhodná pro vozíčkáře) či výtahům (evakuační plány).

3.1.1 Tvorba síťového datasetu Tvorba síťového datasetu probíhá v ArcGIS Desktop v pěti krocích [6]: 1. Příprava sady prvků a zdrojů Jako vstup pro vytvoření síťového datasetu je třeba jednoduchých prvků (linie a body), zatáček a propojení těchto prvků. Všechny prvky musí být uloženy v jedné sadě prvků. Pokud je vytvářena síť ze souborů typu shapefile (formát Esri pro ukládání geometrických dat), je nutné jejich umístění do stejné složky. 2. Příprava metrik, směrů a úrovní Zdrojové prvky reprezentující hrany by měly mít definovaná pole pro vzdálenost, čas atp. Pokud se budou tato pole jmenovat stejně jako jednotka dané metriky, průvodce vytvořením nového síťového datasetu je automaticky rozpozná a ohodnotí jimi hrany výsledné sítě. Jestliže chceme dosáhnout mimoúrovňového křížení hran, je třeba mít k dispozici další dvě pole – pro výšku počátečního a výšku koncového bodu hrany. 3. Příprava zatáček a informací o nich U zatáček mohou taktéž figurovat metriky (čas potřebný na projetí zatáčky) či různá omezení (nákladní automobily nemohou projet touto zatáčkou). Zatáčky však nejsou pro vytvoření síťového datasetu nutné. Uplatňují se hlavně v dopravních sítích.

17

4. Vytvoření síťového datasetu pomocí průvodce Průvodce vytvořením síťového datasetu nabídne pojmenování síťového datasetu, identifikaci zdrojových prvků sítě, nastavení propojení, rozpoznání výškových dat, určení zdrojů zatáček a definici atributů (délky, časy, popisky, omezení, hierarchie). 5. Sestavení síťového datasetu Při sestavování síťového datasetu jsou vytvořeny prvky sítě, definována jejich propojenost a přiřazeny hodnoty daným atributům. Díky vytvořenému síťovému datasetu již lze danou síť analyzovat a odpovídat tak na otázky zmíněné v úvodu této podkapitoly.

18

Kapitola 4

Stavební pasport MU Stavební pasport MU slouží pro získávání a údržbu jednotné stavební dokumentace budov Masarykovy univerzity [7]. Pasport sestává ze dvou částí – popisné a grafické [8]. Popisná data jsou uložena v relační databázi a jsou tzv. polohovým kódem provázána s grafickou částí. Grafická data jsou uchovávána v geodatabázi systému ArcGIS v souřadnicích S-JTSK1 a prezentována na webu2. Oba typy dat se využívají v účetních systémech, v systémech pro správu majetku či pro správu klíčů, ale mohou být rovněž exportována do formátu DWG, který je užitečný zejména při stavebních úpravách. Evidence budov ve Stavebním pasportu umožňuje optimalizovat jejich provoz a využití místností a podporovat jejich údržbu – na příklad z plochy chodby lze odhadnout výši nákladů na její úklid. U místností je evidováno i její vybavení, typy povrchů (podlahy, stěn a stropu) a velikosti ploch (koberce, obkladů...). Díky tomu lze určit, jakým způsobem se podlaha v určité místnosti bude ošetřovat, ale také kolik barvy se má nakoupit pro vymalování dané místnosti. Plány budov mohou posloužit též pro orientaci při záchranářských pracích či při evakuaci. U nově stavěných budov nebo při rekonstrukci budov stávajících je součástí smlouvy s dodavatelem i předání stavební pasportu dané budovy. Ten je poté zařazen do Stavebního pasportu MU, který spravuje Oddělení pasportizace budov Ústavu výpočetní techniky MU ve spolupráci se správci budov. Ti dodávají tomuto oddělení informace o případných změnách v jimi spravovaných budovách.

1 Systém jednotné trigonometrické sítě katastrální (Křovákovo zobrazení) 2 http://maps.muni.cz

19

4.1 Struktura dat Stavebního pasportu Již zmíněný polohový kód v rámci stavebního pasportu jednoznačně identifikuje každou jeho jednotlivou entitu.

Obrázek 4.1: Ukázka identifikace místnosti ve Stavebním pasportu MU polohovým kódem (převzato z https://gisweb.muni.cz/Pasport) Díky hierarchické struktuře kód usnadňuje orientaci ve všech budovách Masarykovy univerzity. Protože čtyřmi základními entitami pasportu jsou lokalita, budova, podlaží a místnost, struktura polohového kódu vypadá následovně:

20

XXX

99

X99

999x Číslo místnosti 999 – číslo místnosti; čísla me nší než 100 se pře dřazují nulami (např. 001, 024 apod.) x – malý alfabetický znak – re zerva pro případ rozdě le ní stávající místnosti (např. 023a)

Znak pro podlaží X – identifikace podlaží (N nadze mní; P podzemní; v případě me zipodlaží bude použito M u nadzemního a Z u podzemního; S pro stře chu). 99 – identifikace čísla podlaží ( 01– 99); v případě me zipodlaží bude číslo podlaží vztaže no k podlaží pod (bude -li v N01 mezone t bude značen M01, bude -li mezi patry P01 a P02 mezone t bude označe n Z02).

Identifikace budovy 99 – ide ntifikace čísla budovy v lokalitě, podmínkou je , že obje kt je zapsatelný do katastru nemovitostí re spe ktive obje kt má své základy a je ne přenositelný. 01-49 – stave bní obje kty pro výukové , vě de ckovýzkumné, administrativní a výrobní činnosti 50-99 – stave bní obje kt menšího významu, garáže, vrátnice, skleníky, te chnologické budovy (trafostanice, vodárna, atd.) a jiné

Identifikace lokality XXX – třímístný alfabe tický znak vychází z ide ntifikace lokalit podle NUTS 2 (první znak ze tří), zbylé dva znaky upřesňují polohu lokality v rámci její identifikace . Identifikace lokality je vytvoře na tak, aby bylo možné identifikovat jakýkoliv obje kt v rámci celého svě ta

Obrázek 4.2: Struktura polohového kódu (převzato z [9]) Díky takovémuto polohovému kódu lze snadno určit vazbu místnosti na podlaží, budovu a lokalitu a rozšiřovat pasport o další budovy, kterých již nyní obsahuje přes 250 s více než 20 tisíci místností. Specifickou entitou stavebního pasportu jsou schodiště, která by se měla číslovat

21

vždy v rámci celé budovy (např. BNA01E001, u většiny schodišť v pasportu však chybí část s písmenem E, to by však mělo být postupně uváděno do pořádku), a dveře, které jsou číslovány v rámci jednoho podlaží (např. BNA01P01D001), a to nezávisle na konkrétním (štítek, cedule...) označení dveří. Součástí entitní množiny dveří klíčovou pro hledání cesty jsou dva atributy, které uchovávají polohové kódy místností, mezi kterými se dveře nacházejí. Schodiště bohužel tyto atributy postrádají. Z polohového kódu schodiště tak vyčteme pouze budovu a podlaží, ve kterém se nachází. Pokud je schodiště evidováno v n-tém podlaží, znamená to, že se po něm lze dostat do (n+1)-tého podlaží. Objekty typu schodiště se však navzdory tomuto pravidlu vyskytují i v podlažích, ze kterých už výše nevedou. Grafická data pasportu jsou rozdělena do osmi sad prvků, jedná se o: 1. Půdorysy podlaží budov 2. Půdorysy stavebních konstrukcí (stěn, sloupů...) 3. Půdorysy místností 4. Půdorysy schodišť 5. Půdorysy výtahů 6. Půdorysy oken 7. Půdorysy dveří 8. Oblouky otvírání dveří Následující obrázek ukazuje celkový pohled, kterým je překryt půdorys podlaží a na kterém jsou číselně dle uvedeného seznamu rozlišeny ostatní typy prvků Stavebního pasportu:

22

2 2

3

6

6 5 8

3

4 3

7

Obrázek 4.3: Ukázka různých typů grafických dat (mapa převzata ze Stavebního pasportu MU)

4.2 Prezentace dat Pokud již jsou někým sbírána a spravována geografická data, bude je chtít většinou také někde publikovat, s někým sdílet. To v tomto případě umožňují služby aplikace ArcGIS Server, díky kterým lze přistupovat k centrálně spravovaným datům (ale také nad nimi provádět GIS operace) jak prostřednictvím aplikace ArcGIS Desktop, tak i pomocí webové aplikace. Stavební pasport MU je ostatně publikován rovněž na webu3. Postup zveřejnění geografických informací má 3 kroky: vytvoření zdrojových dat pomocí ArcGIS Desktop, publikování dat ve formě služby pomocí ArcGIS Server a používání služby klientskou aplikací. Tou může být již zmíněná ArcGIS Desktop, ale také weboví klienti založení na JavaScriptu, Adobe Flex či Microsoft Silverlight.

3 https://gisweb.muni.cz/Pasport

23

Kapitola 5

Navigace v rámci budov MU Pro umožnění vyhledávání cest ve stavebním pasportu je třeba vyřešit dva základní problémy: jak se bude cesta mezi dvěma místnostmi hledat a jakým způsobem se bude následně zobrazovat. Řešení těchto problémů je rozepsáno v následujících podkapitolách. V první řadě byl proveden návrh zobrazování cest, který posléze určil, jakým způsobem se vytvoří struktura pro hledání cest.

5.1 Zobrazení cesty mezi dvěma místnostmi Cestu mezi dvěma místnostmi lze jednoduše vyjádřit lomenou čarou, která propojí všechny místnosti na této cestě. Toho lze docílit vygenerováním spojnic všech místností, které spolu sousedí. Při zobrazení určité cesty se pak zobrazí pouze ty spojnice, které jsou součástí této cesty. Pro znázornění přechodu mezi podlažími se nabízí zobrazení šipky nahoru či dolů u schodiště či výtahu. Tyto šipky se přichystají vygenerováním dvou sad středů jak pro schodiště, tak i pro výtahy:

Obrázek 5.1: Střed schodiště se symbolem pro stoupání vzhůru

24

Obrázek 5.2: Spočtené středy místností a propojené středy těch místností, mezi kterými vedou dveře Pokud se v prostředí ArcGIS Desktop vygenerují středy všech místností a liniemi propojí středy těch místností, mezi kterými vedou dveře, část výsledku vypadá tak, jak ilustruje obrázek 5.2. Na obrázku 5.3 je pak zvýrazněná cesta mezi dvěma místnostmi,

25

Obrázek 5.3: Vyhledání cesty mezi dvěma místnostmi ve struktuře z obrázku 5.2 z nichž každá se nachází na jiném konci budovy. Z obrázků je zjevné, že vygenerované linie vedou skrze zdi a na několika místech navíc křižují místnosti, přes které vlastní cesta vůbec nevede. Pro zpřehlednění trasy se nabízí vygenerovat navíc středy dveří a středy místností propojovat přes ně, nikoliv na přímo. Takto optimalizovaná struktura linií a trasa v ní

26

Obrázek 5.4: Optimalizovaná vyhledávací struktura – nalezená trasa vede přes dveře znázorněná se nacházejí na obrázku 5.4.

Struktura se díky této optimalizaci navíc

„roztáhne“ až k okrajům budovy, respektive ke vstupním dveřím. Dosud s okolím budovy propojena nebyla, neboť se propojovaly pouze středy místností. Ani takto vylepšená však není ideální. Některé trasy totiž mohou křižovat schodiště nebo mohou být zbytečně klikaté. Např. pokud se výchozí i cílová místnost nacházejí na stejném konci

27

chodby, nemá smysl, aby trasa vedla přes její střed. S pomocí dalších, geometricky náročnějších optimalizací (jako třeba vygenerování středové osy chodby a kolmic od ní ke dveřím) by bylo možné sestavit takovou strukturu linií, ve které by bylo možné znázorňovat ještě přehlednější trasy. To ale není předmětem této práce, důležité je především zjistit, jakým způsobem data kampusu interpretovat, aby bylo možné hledat cesty mezi jeho místnostmi. Dále je tedy potřeba stanovit postup pro místnosti, které spolu očividně sousedí, ale nejsou spojeny linií. Z obrázků 5.2 až 5.4 je zjevné, že právě schodiště se nacházejí ve vlastní místnosti (uprostřed chodby), pro kterou byl sice vygenerován střed, ale jelikož z této místnosti nevedou žádné dveře, není s žádnou místností propojena. Protože schodiště a výtahy (dále jen přípojné body podlaží) umožňují přechod mezi podlažími a je tedy třeba se k nim při cestách v rámci víe podlaží dostat, byly vytvořeny dva CSV soubory. V prvním z nich byla ručně shromážděna data o všech schodištích kampusu, ve druhém data o všech výtazích. U schodišť se v CSV souboru eviduje: •

OBJECTID z atributové tabulky datasetu Q3_kce_schodis,

•

polohový kód sousední místnosti,

•

informace o tom, zda je schodiště bezbariérové (tzn. buď není tvořeno stupni, ale jedná se o nakloněnou rovinu, nebo sice je tvořeno stupni, ale je doplněno o pojízdnou plošinu)

•

polohový kód vlastní místnosti schodiště,

•

OBJECTID schodiště, které se nachází bezprostředně nad daným schodištěm,

•

informace o tom, zda je schodiště únikové, nebo běžně užívané.

Pro každou položku tohoto seznamu schodišť se vygenerují nové linie takto: 1. Eviduje-li se u schodiště sousední místnost i vlastní místnost: a) Spojí se střed sousední místnosti se středem vlastní místnosti. b) Spojí se střed vlastní místnosti se středem schodiště. 2. Eviduje-li se u schodiště pouze sousední místnost: a) Spojí se střed sousední místnosti se středem schodiště. 3. Eviduje-li se u schodiště pouze jeho vlastní místnost: a) Spojí se střed vlastní místnosti se středem schodiště. Případ 1 nastává u schodišť, která jsou umístěna ve vlastní místnosti, která sousedí s nějakou další místností, jak to ilustrují předchozí obrázky pro již zmíněné schodiště uprostřed chodby. Druhý případ je typický pro schodiště, která spojují dvě místnosti

28

místo dveří, tzn. z jedné místnosti se dá po schodech sestoupit či vystoupat do druhé. Takto se tedy zajistí propojení těchto sousedních a dosud nepropojených místností. Poslední případ platí pro schodiště, která náleží k nějaké místnosti, jež je však se svým okolím provázána nebo nemá žádné okolí a slouží pouze jako přechod mezi podlažími. Taková schodiště lze nalézt např. v přednáškových učebnách či v rámci únikových schodišť (viz obrázek 5.5).

Obrázek 5.5: Únikové schodiště a jeho místnost (červeně napojení) Právě místnosti únikových schodišť jsou tedy popsaným postupem napojeny do celého systému a pokud budou později např. cílovou místností hledané trasy, bude tato nalezena. Pro výtahy byl vytvořen obdobný CSV soubor s tím rozdílem, že se u jednotlivých položek sleduje méně atributů: •

OBJECTID z atributové tabulky vytahy,

•

polohový kód místnosti, ve které se výtah nachází (dále vlastní místnost výtahu),

•

OBJECTID výtahu, který se nachází bezprostředně nad daným výtahem.

Výtahem v předešlém seznamu se rozumí prostor, kde kabina staví, proto se tedy v tomto pohledu na výtahy může jeden výtah nacházet nad druhým. Má-li tedy budova čtyři podlaží a výtahovou šachtu obsluhující každé z nich, obsahuje také dataset vytahy v pasportu čtyři prvky. U každé položky z připraveného CSV se vygenerují nové linie tak, že se propojí

29

střed vlastní místnosti výtahu se středem výtahu. Jako jsou pro všechny linie spojující dvě místnosti evidovány polohové kódy těchto místností, tak i pro linie, které spojují místnosti se schodišti či výtahy, jsou evidovány polohový kód místnosti a OBJECTID schodiště či výtahu:

Obrázek 5.6: Atributy spojnic To později umožní pro podlaží budov identifikovat tzv. přípojné body podlaží (místa, kde se dá přecházet mezi podlažími). Pohled na všechny vygenerované linie odhalil, že některá propojení ještě chybějí – propojení místností, které spolu sousedí, ale nevedou mezi nimi dveře ani schodiště:

Obrázek 5.7: Sousední místnosti s volným průchodem

30

Pro tyto dvojice místností byl zaveden třetí CSV soubor již pouze se dvěma sloupci pro polohové kódy obou místností. Na základě tohoto seznamu se automaticky doplní další chybějící spojnice, po kterých mohou vést cesty. Dále je na vygenerovaných spojnicích očividné, že jich většina chybí ve východní části kampusu. Důvod je prostý – v této části kampusu ještě nejsou zaneseny dveře do datasetu Q3_op_dvere, a chybí zde tedy i informace o propojení místností. Na oddělení pasportizace budov Ústavu výpočetní techniky Masarykovy univerzity však probíhá postupné doplňování těchto chybějících dveří do pasportu, jakmile tedy budou tyto práce dokončeny, stačí pouze spojnice na základě propojení místností dveřmi vygenerovat znovu. Uvedené tři CSV soubory již není potřeba pro „dveřmi nepokrytou“ část kampusu zvláště aktualizovat, neboť schodiště, výtahy i dvojice místností s volným průchodem jsou v těchto souborech zadány pro celý kampus.

Obrázek 5.8: Chybné propojení místností, nenapojení budov na chodbu

31

Ve spojnicích se objevily i určité anomálie, a to např. nenapojení jednotlivých budov na přilehlou chodbu, propojení místností různých budov (obě anomálie jsou pozorovatelné na obrázku 5.8), propojení místností různých podlaží či propojení místností jednoho podlaží dveřmi z jiného podlaží. Tato chybná propojení byla způsobena chybnými údaji u dveří v pasportu. To znamená, že záznam pro dveře měl polohové kódy jiných přilehlých místností, než mezi kterými dveře ve skutečnosti vedou. Dveře (chybně) spojující dvě místnosti různého podlaží byly odhaleny jednoduchou filtrací prvků datasetu dveří s podmínkou na nerovnost podlaží přilehlých místností. Vyskytly se i duplicitní polohové kódy dveří či místností. Všechny odhalené chyby byly opraveny, byl také sepsán seznam těchto chyb, který byl předán oddělení pasportizace a je rovněž přílohou této práce. K práci jsou přiloženy i tři CSV soubory se zpracovanými schodišti, výtahy a dvojicemi místností s volným průchodem jako: •

stairs.csv

•

elevator.csv

•

neighbours_without_doors.csv

Dále je přiložen také skript script.py, napsaný v jazyce Python, který pomocí balíku ArcPy pro práci nad daty ArcGIS Desktop vygeneruje potřebné struktury. V jeho úvodu je třeba nastavit cestu souboru, do kterého se budou ukládat propojující linie, cesty k připraveným CSV souborům, cestu k příslušné geodatabázi a pravdivostní hodnotu proměnné ommitStairsAndElevators. Pokud tato bude True, nebudou se mazat a znovu vytvářet středy schodišť a výtahů, což je vhodné při opakovaném spouštění skriptu po úpravách dat o dveřích. Ve shrnutí pak skript postupuje takto: 1. Zruší filtrace dat, aby se analýza aplikovala na všechna. 2. Smaže všechny datasety vytvářené v dalších krocích. 3. Vytvoří středy místností. 4. Vytvoří středy dveří. 5. Vytvoří po dvou sady středů schodišť a výtahů. 6. Místnosti, mezi kterými vedou dveře, přes tyto dveře propojí liniemi, ke kterým přidá polohové kódy dotyčných místností. 7. Načte z CSV souborů data o schodištích, výtazích a dvojicích místností s volným průchodem a provede potřebná propojení. Díky tomuto skriptu se spojnice (hrany) vytvoří poměrně rychle a automaticky, ručně tak bylo potřeba pouze shromáždit data do CSV souborů a zkontrolovat chyby. Skript při

32

opětovném spuštění v ArcGIS Desktop často selže v bodě 2 – test na existenci datasetu buď vrátí informaci, že dataset existuje, i když neexistuje, a následně selže při mazání neexistujícího datasetu, a nebo vrátí informaci, že dataset neexistuje, i když existuje, a následně dojde k selhání při pokusu o vytvoření již existujícího datasetu. Tyto potíže vždy zmizely po restartu aplikace ArcGIS Desktop.

5.2 Sestavení vyhledávacích struktur Data pro zobrazování cest a o provázání místností jsou připravena k další analýze, která by měla vyústit v sestavení datových struktur, nad kterými bude možné vyhledat cestu mezi dvěma místnostmi. K dispozici je soustava bodů a linií, nabízí se zde tedy vytvoření sítě pomocí příslušného nástroje ArcGIS Desktop. Taková síť sice umožňuje nastavit i mimoúrovňové křížení hran, při jejich množství a několika podlažích se toto jeví jako náročná varianta pro pasport kampusu, kde jsou data jednotlivých podlaží uložena v rovině přes sebe. Proto bylo po delších úvahách zvoleno řešení na míru, které je popsáno v této podkapitole. Prvotní myšlenkou bylo spočtení matice předchůdců pomocí algoritmu Floyda a Warshalla pro graf všech místností kampusu. Ten jich ovšem čítá 3 804, algoritmus by tedy musel počítat dvakrát 3 804 matic o rozměrech 3 804 x 3 804, což představuje přes 11 milionů počítaných hodnot pro každou matici, takže by bylo vhodné hledat nějakým způsobem dekomponované řešení. Nápovědu skýtá pohled na vygenerované linie. Ty totiž tvoří graf skládající se z izolovaných komponent souvislosti, které svými vrcholy odpovídají místnostem konkrétní budovy v rámci konkrétního podlaží. Tyto komponenty si lze představit jako vrcholy dalšího grafu, které spolu sousedí dle sousedství podlaží, která jsou přímo nad sebou a jsou spojená schodištěm či výtahem. Idea vyhledávání v takových grafech je pak jednoduchá – zjistí se, do jakých komponent souvislosti patří výchozí a cílová místnost. Pokud jsou obě místnosti ve stejné komponentě, vyhledá se cesta v rámci ní, pokud jsou v různých komponentách, vyhledá se cesta z výchozí místnosti k nejbližšímu přípojnému bodu (tj. schodišti či výtahu) podlaží, cesta z cílové místnosti k nejbližšímu přípojnému bodu podlaží a nakonec cesta v grafu komponent, tedy přes která podlaží kterých budov se půjde. Tato idea je podobná dálniční hierarchii zmíněné na konci 2. kapitoly této práce – na rozdíl od ní zde však nejsou spočteny minimální cesty mezi přípojnými body v rámci jedné komponenty. Pro toto řešení bylo nutné sestavit a uložit potřebné vyhledávací struktury, což

33

provádí další přiložený skript: prepare_search_structure.py4. Ten kromě balíku ArcPy využívá i doinstalovaného balíku NumPy5 a postupuje tak, že si na začátku načte seznam všech místností a seznam všech linií. S pomocí těchto seznamů sestaví graf s místnostmi jako vrcholy a liniemi jako hranami. Tento graf je ve skriptu reprezentován jako seznam následníků (pojem vysvětlen v kapitole 2), pro jehož implementaci byl zvolen slovník – datová struktura programovacího jazyka Python: graph = { "kód místnosti": [[<seznam kódů sousedů>], ], ... }

V tomto grafu jsou rozpoznány komponenty6, které se uloží jako seznam seznamů polohových kódů místností, které tvoří jejich vrcholy. Poté se pro každou komponentu v tomto seznamu spočte matice sousednosti a pomocí algoritmu Floyda a Warshalla matice předchůdců. Tyto matice se uloží do seznamů tak, že příslušné komponenty mají v seznamu komponent stejný index. Dále se pro každou komponentu (tedy pro každé podlaží každé budovy) najdou její přípojné body. Vznikne tak další seznam, který bude mít na pozici i uložený seznam všech schodišť a výtahů nacházejících se v i-té komponentě. Souběžně vznikne také slovník, který naopak pro dané schodiště či daný výtah uchová index komponenty, ve které se nachází. Skript následně vytvoří další seznam, ovšem pouze těch komponent, které mají nějaký přípojný bod. Pro tyto komponenty pak vygeneruje graf. Ty ostatní by v grafu figurovaly stejně jako vrcholy bez hran. Navíc je takových komponent poměrně mnoho, neboť ve východní části kampusu dosud chybí informace o propojení místností, a tak vlastně každá samostatná místnost z této části kampusu odpovídá jedné komponentě. Z vygenerovaného grafu se spočte matice sousednosti jednotlivých komponent a matice předchůdců (jejíž výpočet by byl nad všemi komponentami podstatně pomalejší). Zároveň se sestavováním grafu je také vytvořen slovník pro schodiště: 4 Skript se osvědčilo spouštět v samostatném Python IDLE, zde totiž jeho běh trvá kratší dobu, než přímo v aplikaci ArcGIS Desktop. 5 Rozšíření Pythonu, které mimo jiné podporuje také práci s maticemi, dostupné na http://www.numpy.org 6 Při rozpoznávání komponent je využito pole index komponenty ve slovníku reprezentujícím graf jako příznak, že místnost již byla do nějaké komponenty zařazena.

34

stairsNeighbours = { : [, ], … } Analogicky je vytvořen slovník i pro výtahy. Tyto dvě struktury při hledání cesty umožní zjistit, zda a jaké schodiště či výtah se nachází v další komponentě na cestě. Pro zjištění místnosti, ze které se bude v další komponentě vycházet, se vytvoří i seznamy vlastních místností schodišť a výtahů. Všechny uvedené struktury jsou ze svých proměnných skriptem pomocí modulu pickle uloženy do souborů, kde jsou de facto připraveny pro vyhledávání cest. Takto připravené struktury zahrnují celý kampus, pro vynechání střech a únikových schodišť je nutné na začátku skriptu nastavit proměnné limited hodnotu True.

5.3 Vyhledávání cest Idea pro vyhledávání cest již byla nastíněna v předchozí podkapitole. Součástí práce je soubor search_route.py, který obsahuje funkce implementující uvedený postup pro prostředí ArcGIS Desktop. Tento postup bude dále ještě upřesněn. Pro zobrazení cesty pomocí vygenerovaných prvků v mapě (středy schodišť a výtahů a linie) je potřeba jejich seznam. Ten lze získat ze seznamu místností, přes které daná cesta vede. Nejprve bude popsána funkce getRoute(start, target, barrierFree = False), která pro danou dvojici místností vrací seznam místností na jednotlivých úsecích cesty oddělených schodištěm či výtahem a seznam schodišť a výtahů oddělujících tyto úseky (čili změn podlaží). Jejími prvními dvěma parametry jsou polohové kódy výchozí a cílové místnosti, třetí, nepovinný parametr barrierFree s výchozí hodnotou False, určuje, zda se má hledat bezbariérová cesta. Funkce po nezbytných kontrolách na existenci místností s danými polohovými kódy zjistí, ve kterých komponentách se výchozí a cílová místnost nacházejí. Pokud jsou tyto dvě komponenty totožné, vrátí se seznam místností na cestě mezi kýženými místnostmi prostřednictvím funkce getRouteWithinComponent a prázdný seznam změn podlaží. Cesta mezi dvěma místnostmi v rámci jedné komponenty je získána rekurzívním

35

voláním této funkce nad maticí předchůdců vygenerované algoritmem Floyda a Warshalla pro danou komponentu. Pokud jsou zjištěné komponenty různé, ověří funkce getRoute, zda obě z nich obsahují nějaký přípojný bod a tím i jejich přítomnost v grafu komponent. Je-li některá z nich bez přípojného bodu, funkce skončí výjimkou se zprávou „Cesta neexistuje“. Jinak pomocí rekurzívního volání funkce getRouteOverComponents nad maticí předchůdců komponent obstará seznam komponent udávající, ve kterých komponentách a v jakém pořadí se budou hledat dílčí cesty. Poté do seznamu dílčích cest (úseků) vloží první úsek ve formě seznamu o jedné položce – výchozí místnosti a vytvoří prázdný seznam změn podlaží. Následně se pro každou komponentu získanou funkcí getRouteOverComponents hledají jednotlivé úseky, a to opět pomocí funkce getRouteWithinComponent. Výchozí místností v tomto případě bude poslední místnost posledního úseku z dosavadního seznamu úseků. Jedná-li se o poslední hledaný úsek, jeho cílovou místností bude cílová místnost celé cesty. Jinak se musí cílová místnost najít, respektive se musí najít přípojný bod podlaží, přes který se přejde do následující komponenty. Proto se dle následující komponenty určí, zda se mezi ní a komponentou stávající půjde směrem nahoru, nebo dolů a vyberou se pouze ty přípojné body, které daným směrem do následující komponenty vedou. Má-li být cesta bezbariérová, vyberou se z těchto přípojných bodů jen nakloněné roviny (zaznačeno v CSV souboru pro schodiště zmíněném v podkapitole 5.1) a výtahy. Do místností těchto přípojných bodů se vyhledají cesty a jako cesta daného úseku se vybere ta nejkratší. Při rovnosti délky se vybere ta cesta, která má případně za cíl místnost ze stejné budovy, z jaké pochází cílová místnost celé cesty. Výchozí místnost se již v seznamu úseků nachází, zbytek této zvolené cesty se k němu připojí a na konec seznamu se připojí nový úsek (jednoprvkový seznam obsahující místnost navazujícího přípojného bodu), se kterým se postup opakuje pro další komponentu. Ještě předtím se však do seznamu změn podlaží vloží zvolený přípojný bod. Funkce getRoute tedy vrátí seznam úseků cesty a seznam změn podlaží ve formátu dvojice: ([[<místnosti úseku 1>], [<místnosti úseku 1>], ...], [<schodiště či výtah mezi úseky 1 a 2>, ...]) Místností se zde rozumí její polohový kód a schodištěm či výtahem směr a OBJECTID. První seznam lze použít k obstarání seznamu linií, které danou cestu znázorňují. Tak činí funkce

36

showRoute(start, target, floor=None, barrierFree = False), jež s parametry start, target a barrierFree zavolá funkci getRoute a zobrazí ty úseky cesty, které se nacházejí na daném podlaží. Pokud funkci není podlaží předáno, vezme podlaží výchozí místnosti. Na základě polohových kódů sousedních místností zobrazí a vybere příslušné linie. Pokud cestou dochází ke změně podlaží, zobrazí se příslušné středy schodišť či výtahů dle druhého seznamu vráceného funkcí getRoute. Nakonec se zvýrazní i cílová místnost, pokud je součástí zobrazovaného úseku, a mapa v aplikaci ArcGIS Desktop se zaměří na aktuální výběr. Následují ukázky vyhledaných cest.

37

5.4 Ukázky vyhledaných cest

Obrázek 5.9: Cesta v rámci jedné komponenty, BHA22N02018–BHA22N02034

38

Obrázek 5.10: Cesta mezi dvěma komponentami, BHA16N01005–BHA15N01013, 1. podlaží

Obrázek 5.11: Cesta mezi dvěma komponentami, BHA16N01005–BHA15N01013, 2. podlaží 39

Obrázek 5.12: Cesta mezi dvěma komponentami, BHA16N01005–BHA15N01013, 1. podlaží

Obrázek 5.13: Cesta mezi dvěma komponentami, BHA16N01005–BHA15N01013, 2. podlaží

40

Na začátku souboru search_route.py lze nastavit cestu k sadě uložených vyhledávacích struktur. Přílohou této práce jsou dva adresáře nazvané whole a limited. V prvním adresáři jsou uloženy struktury pro vyhledávání v celém kampusu, v tom druhém jsou vynechány střechy a úniková schodiště. Obrázek 5.14 demonstruje rozdíl v hledání cest v uvedených dvou sadách.

Obrázek 5.14: Vlevo cesta BHA22N02018–BHA22N0318 vyhledaná v celém kampusu, vpravo vynechána úniková schodiště a střechy

41

Některé vyhledané cesty napříč různými budovami nemusí být nutně nejkratší, neboť vyhledávací struktury se generují nad neohodnoceným grafem. Pokud v tomto grafu existuje více nejkratších cest, je zvolena jedna z nich. Obrázek 5.15 ilustruje cestu mezi budovami, která jde oklikou.

Obrázek 5.15: Cesta BHA22N02009–BHA14N02006 mezi budovami Takovéto cesty by bylo možné eliminovat ohodnocením hran původního grafu místností např. délkou linií mezi nimi. To ovšem povede k problému u jiných cest, kde by délku cesty mohly zkreslit dlouhé linie jdoucí přes střed velké místnosti. Proto by bylo vhodné v budoucnu linie optimalizovat tak, aby více odpovídaly skutečné cestě. To by mohlo být provedeno na příklad rozdělením dlouhých chodeb na více místností, jejichž středy tak budou blíže jednotlivým dveřím, nebo i ruční úpravou (zalomením) linie, atd. Podobný problém stejně dlouhých cest vzniká i u některých cest v grafu komponent. Ty tak někdy mohou vést zbytečně přes další budovy, i když počet komponent bude stejný. Tomuto problému by šlo při hledání cesty předejít, kdyby se u určování cílové místnosti každého úseku zjišťovalo, zda není daná místnost v cílové budově a zda do ní nevede schodiště či výtah z cílové komponenty.

42

Kapitola 6

Závěr Cílem práce bylo analyzovat data Stavebního pasportu Masarykovy univerzity pro navigaci v rámci jejích budov. Při analýze bylo zjištěno, že je k tomuto použití kampus s částečnými úpravami způsobilý. V rámci práce byly vygenerovány grafické prvky pro jednoduché znázorňování cest. Dále byly s využitím algoritmu Floyda a Warshalla připraveny vyhledávací struktury, a to takovým způsobem, že je možné při hledání vynechat střechu, únikové místnosti, ale i nesjízdná schodiště pro vyhledání bezbariérových cest. V samotném závěru došlo rovněž k umožnění vizualizace nalezených cest po jednotlivých podlažích pomocí dříve vygenerovaných grafických prvků. Přínosem této práce je také odhalení chyb v datech kampusu, které dosud nebyly z prvního pohledu na plány budov zřejmé a ukázaly se až jako anomálie při přípravě pasportu pro hledání cest. Díky tomu lze nalezené chyby odstranit a dle uvedených postupů odhalit další chyby v jiných budovách Masarykovy univerzity. Na práci lze v budoucnu navázat na příklad optimalizací propojovacích linií a eliminací oklik vzniklých při některých hledáních cest. Po takových optimalizacích se může hledání cest zpřístupnit koncovému uživateli, kterým je v tomto případě (potenciální) návštěvník kampusu, pomocí internetové mapové služby, jež může být dostupná např. i na nějaké obrazovce přímo v budově kampusu.

43

Literatura [1] ČERNÝ, Jakub. Základní grafové algoritmy [online]. 2010 [cit. 2012-03-09]. Dostupné na: http://kam.mff.cuni.cz/~kuba/ka/ka.pdf [2] ŠMÍD, Vladimír. Management informačního systému: Pojem informačního systému.

[online].

[cit.

2012-03-16].

Dostupné

na:

http://www.fi.muni.cz/~smid/mis-infsys.htm [3] BŘEHOVSKÝ, Martin a Karel JEDLIČKA. Úvod do geografických informačních systémů:

Přednáškové

texty

[online].

[cit.

2012-03-16].

Dostupné

na:

http://gis.zcu.cz/studium/ugi/e-skripta/ugi.pdf [4] ESRI. What is ArcGIS Desktop? [online]. 2011 [cit. 2012-03-16]. Dostupné na: http://help.arcgis.com/en/arcgisdesktop/10.0/help/00v2/00v200000005000000.htm [5] ESRI. What is Network Analyst? [online]. 2012 [cit. 2012-03-16]. Dostupné na: http://help.arcgis.com/en/arcgisdesktop/10.0/help/0047/004700000001000000.htm [6] ESRI. Creating a network dataset [online]. 2012 [cit. 2012-03-21]. Dostupné na: http://help.arcgis.com/en/arcgisdesktop/10.0/help/0047/00470000000w000000.htm [7] KROUTIL, Petr a Martin VYTRHLÍK. Stavební pasport MU, import a export grafických dat a automatické generování kót. Zpravodaj ÚVT MU Bulletin pro zájemce o výpočetní techniku na Masarykově univerzitě. 2010, XXI, č. 2, s. 11-14. ISSN 1212-0901. Dostupné na: http://www.ics.muni.cz/bulletin/articles/658.html [8] KROUTIL, Petr. Stavební pasport MU v současnosti. Zpravodaj ÚVT MU Bulletin pro zájemce o výpočetní techniku na Masarykově univerzitě. 2009, XIX, č. 5, s. 67. ISSN 1212-0901. Dostupné z: http://www.ics.muni.cz/bulletin/articles/619.html [9] BLAŽEK, Pavel, Petr GLOS, Jitka HANUŠOVÁ, Petr KROUTIL a David MIKSTEIN.

ÚSTAV

VÝPOČETNÍ

TECHNIKY

MU.

Metodika

stavební

pasportizace MU. Brno.

44

Příloha A

Seznam elektronických příloh •

data_pro_navigaci.zip ◦ arcgis_data – obsahuje mapu a geodatabázi ◦ csv – obsahuje CSV soubory s dodatečnými informacemi ◦ skripty – obsahuje v práci popisované Python skripty ◦ struktury – obsahuje struktury připravené pro hledání cest ▪ limited – struktury pro hledání bez únikových schodišť a střech ▪ whole – struktury pro hledání v celém kampusu ◦ chyby.txt – výčet chyb odhalených při implementaci navigace

45