Mendelova zemědělská a lesnická univerzita v Brně Provozně ekonomická fakulta
Převodník geografických dat Aplikace vývojových technik semestrální práce
Jan Grmela, 2. ročník, Ekonomická informatika Brno, 6. 6. 2008
Obsah 1 Úvod...................................................................................................................................3 2 Cíl práce.............................................................................................................................3 3 Postup řešení......................................................................................................................3 3.1 Vstupní data................................................................................................................3 3.2 Data Silniční databanky Ostrava.................................................................................4 3.2.1 Tabulka VUZLY.dbf............................................................................................5 3.2.1.1 Formát CIS_UZLU.......................................................................................5 3.2.1.2 Formát ICZUJ...............................................................................................6 3.2.1.3 Formát CHAR_UZLU..................................................................................6 3.2.2 Tabulka VUSEKY.dbf.........................................................................................6 3.2.2.1 Formát CIS_USEKU....................................................................................7 3.2.2.2 Formát SILNICE..........................................................................................7 3.2.3 Tabulka CDMAB.dbf...........................................................................................7 3.3 Výstupní data..............................................................................................................8 3.3.1 Tabulka adm_units...............................................................................................9 3.3.2 Tabulka edges......................................................................................................9 3.3.3 Tabulka node_types.............................................................................................9 3.3.4 Tabulka nodes......................................................................................................9 3.3.5 Tabulka edges_systems........................................................................................9 3.3.6 Tabulka places...................................................................................................10 3.3.7 Tabulka roads.....................................................................................................10 3.3.8 Tabulka systems.................................................................................................10 3.4 Algoritmus převodu...................................................................................................10 4 Diskuse.............................................................................................................................11 5 Závěr................................................................................................................................12 6 Seznam použité literatury.................................................................................................13
-2-
1 Úvod Grafové algoritmy (v našem případě aplikované na geografické mapy) prošly od doby svého vzniku, kterou je obvykle uváděna doba vzniku problému sedmi mostů v Královci (Prusko, dnes Rusko), dlouhou cestou. Otázka tehdy byla položena následovně: Je možné přejít všechny mosty tak, abychom na každý vstoupili jen jednou? Problém vyřešil v roce 1736 Leonhard Euler s tím, že to možné není. Podle něj byl pojmenován speciální případ grafu – eulerovský. Je to takový graf, který „lze nakreslit jedním tahem“. Dalším významným momentem historie grafových algoritmů je vytvoření algoritmu pro nale zení minimální kostry grafu. Tento algoritmus byl vytvořen 1926 a následně použit pro výstavbu elektrické sítě na Moravě. Od té doby se teorie grafů stala významnou matematickou disciplínou, na které závisí mnohé vymoženosti dnešní doby. Silniční sítě, zásobování energiemi, či například to, zda se dostanete včas na dovolenou. Jednou z podskupin teorie grafů je i hledání nejkratších či nejvýhodnějších cest. Tato práce má připravit půdu pro další možné aplikace tímto problémem se zabývající.
2 Cíl práce Cílem práce „Převodník geografických dat“ je realizace aplikace, která umožní import dat o silniční síti České republiky do databáze jiného formátu. Vstupní data pocházejí od Ředitelství silnic a dálnic ČR a jsou volně dostupná ve formátu dBase III [1] na jejich webových stránkách. Jako výstupní databáze byla zvolena oblíbená PostgreSQL kvůli jejímu vysokému výkonu, dobré přenositelnosti a snadnému použití. Vzniklá databáze může později sloužit jako datový sklad pro účely aplikace implementující některé grafové algoritmy.
3 Postup řešení 3.1
Vstupní data Největším problémem, který bylo nutno před započetím práce na samotném programu vyře
šit, bylo získání vstupních dat. Geografická data, a to jak rastrová, vektorová či textová (popisná) jsou významným obchodním artiklem a není snadné je získat. Téměř všechny organizace, které s ta kovým daty pracují, jsou ochotny je poskytnout výhradně pro osobní použití (nikoli tedy pro auto matizované zpracování), mnohdy za úplatu. Velké množství dat je taktéž v nepoužitelných vstupních formátech (zejména rastrových), jde například o oblíbené mapové servery Seznamu či Googlu. Zde se taktéž vyskytuje licenční problém -3-
zakazující automatizované použití zmíněných serverů. Ani v případě státní správy není situace o mnoho lepší. Server portálu Ministerstva vnitra a Ministerstva životního prostředí, který posky tuje data na adrese
http://geoportal.cenia.cz
disponuje sice množstvím vhodných dat, bohužel
ale jen v rastrovém formátu. Snad jediným volně dostupným zdrojem (pokud pomineme projekt OpenStreetMap na adrese http://www.openstreetmap.org/,
jenž je ale zaměřen spíše na koncového uživatele), který zároveň
zveřejňuje data v dobře dokumentovaném a snadno čitelném formátu je Ředitelství silnic a dálnic České republiky, konkrétně Silniční databanka Ostrava. Na jejich webových stránkách (http://www.rsd.cz) je k dispozici sada souborů popisující silniční síť České republiky. Sada je aktualizována dvakrát ročně.
3.2
Data Silniční databanky Ostrava Data, která lze stáhnout ze stránek ŘSD, jsou ve standardizovaném formátu ERSI Shapefile
(specifikace viz [2]), který popisuje nejen grafickou strukturu formou vektorového zobrazení, ale také zobrazená místa formou textových nebo číselných údajů. Po důkladné analýze za pomocí nástrojů dodaných firmou ERSI (zejména ArcExplorer) a prostředky operačního systému, bylo zjišťeno, že právě soubor, obsahující data popisná (nikoli grafická), by mohl být klíčem k vyřešení problému nedostupnosti dat. Jde totiž o sadu tabulek v dobře podporovaném formátu dBase III. Bohužel, k těmto datům takřka neexistuje dokumentace (mimo několika řádků na webu). Zodpovědné osoby ŘSD na e-mailové dotazy ohledně dokumenta ce nereagovaly a tak bylo nutno značný čas věnovat analýze dat kvůli zjištění významu jednotlivých sloupců v tabulkách. Po důkladném prohledání webu se podařilo získat dokument analyzující zátěž životního prostředí zpracovaný Ministerstvem dopravy ČR [3]. V dokumentu byly použity dotazy právě na databázi Silniční databanky, což přineslo mnoho užitečných informací. Ze souborů, které jsou na webu k dispozici byly nakonec použity tyto tři: ●
VUSEKY.dbf – tabulka úseku (silnic) propojujících jednotlivé uzly
●
VUZLY.dbf – tabulka uzlů (křižovatek)
●
CDMAB.dbf – tabulka administrativních jednotek
Ilustrace 1: Náhled tabulky VUZLY.dbf -4-
Bohužel, tak, jak je databáze navržena, je dost obtížně použitelná. Tedy alespoň, chceme-li dosáhnout přijatelné rychlosti při práci s ní. Databáze porušuje mnoho doporučení pro tvorbu re lačních databází. Kupříkladu nevhodné použití textového primárního klíče či téměř žádná norma lizace tabulek. Příkladem může být ilustrace výše, kdy je jasně vidět zbytečná redundance v podobě textového popisu druhu křižovatky. Z výše uvedených důvodů a také kvůli omezeným možnostem, které dBase III nabízí, bylo rozhodnuto, že musí být tato data převedena do jiného formátu, kde budou silněji aplikována dopo ručení pro tvorbu relačních databází a bude taktéž provedena normalizace a lepší návrh tabulek.
3.2.1
Tabulka VUZLY.dbf
Tabulka obsahuje seznam uzlů, tedy obvykle křižovatek. Některé body jsou ale například za čátkem či koncem komunikace či hraničním přechodem. Popisuje název umístění (pokud nějaký existuje) a identifikační číslo územní jednotky (nekompatibilní s ČSÚ). Zjištěný význam dat popi suje následující tabulka: CIS_UZLU ADM[1-2] ICZUJ ICZUJ_TEXT SOU_X SOU_Y VYS_SOU_Z CHAR_UZLU CHAR_TEXT POCKR_DUZ POCV_DUZ KR_UZEL[1-8] ORIENT[1-8] NAV_UZEL[1-8] DAT_ZAZNAM
číslo uzlu čísla administrativních jednotek, ve kterých se uzel nachází (CDMAB) identifikační číslo základní územní jednotky název územní jednotky souřadnice v ose X – nevyužito souřadnice v ose Y – nevyužito souřadnice v ose Z – nevyužito typ uzlu (k řižovatk a, hraniční přechod, …) název typu uzlu význam není znám význam není znám do kterého úseku křižovatky úsek vchází/vychází Orientace -- + vstupuje do uzlu, - vystupuje z uzlu CIS_UZLU spojeného s tímto uzlem datum vytvoření záznamu
Tabulka 1: Struktura tabulky VUZLY.dbf 3.2.1.1
Formát CIS_UZLU
CIS_UZLU je primárním klíčem VUZLY.dbf. Jde tedy o unikátní označení konkrétního uzlu. Formát je popsán regulárním výrazem ^([0-9]{4}[ABC]{1}[0-9]{3})([0-9]{2})$. První ozávor kovaná část uvozuje číslo uzlu, druhá (volitelná) v případě křižovatek udává, o jaký úsek křižovatky jde. Z výše uvedeného plyne, že může existovat několik uzlů se stejnou „první částí“ lišících se jen v čísle úseku křižovatky. Takovou křižovatku nazýváme komplexní. Obvykle jde o stavby, ja kými jsou dálniční mosty s přivaděči nebo křižovatky, kde se cesty nekříží v jednom místě, jsou ale propojeny pomocnými komunikacemi (kruhový objezd). -5-
Tabulka VUZLY.dbf neobsahuje údaje k dílčím uzlům komplexních křižovatek, jen ke kři žovatkám samotným. 3.2.1.2
Formát ICZUJ
Původní domněnka byla taková, že tento kód bude souhlasit s údaji poskytovanými Českým statistickým úřadem (http://www.czso.cz). Ta se bohužel ukázala jako nepravdivá, jelikož kódy IČZÚJ s ČSÚ vůbec nesouhlasí. Bylo tedy nutno využít i sloupec ICZUJ_TEXT pro vytvoření vlast ního seznamu územních jednotek. 3.2.1.3
Formát CHAR_UZLU
Písmeno či číslo uvedené v CHAR_UZLU (a duplicitně textově zapsané v CHAR_TEXT) udává, o jaký druh uzlu se jedná. Druhy mohou být následující:
3.2.2
●
1 – začátek nebo konec komunikace
●
2 – začátek nebo konec přívozu
●
3 – začátek nebo konec nevybudované ulice
●
4 – začátek nebo konec vojenského prostoru
●
5 – státní hranice
●
6 – začátek nebo konec směrového rozdělení
●
7 – bod jednoznačnosti
●
8 – změna počtu dopravních pruhů (slovo „pruhů“ je odhad)
●
9 – jiný bod
●
M – křižovatka mimoúrovňová
●
N – křižovatka mimoúrovňová (jiný typ, není určeno)
●
R – křižovatka úrovňová světelná (slovo „světelná“ je odhad)
●
U – křižovatka úrovňová
Tabulka VUSEKY.dbf
Tato tabulka popisuje propojení jednotlivých uzlů (křižovatek) mezi sebou. Nese důležité informace týkající se například délky úseku, názvu silničního tahu, ke kterému úsek přísluší či čísla silnice. Významy jednotlivých sloupců (které se podařilo zjistit) shrnuje následující tabulka.
-6-
CIS_USEKU DAT_ZAZNAM ADMINJ DELKA_US DOPR_SMERY PAPR_VETEV KOD_TR_KOM SILNICE VYBR_SIT VYM_TAHY PEAZ_KOM[1-8] ETAH[1-4] PORADI_US
číslo úsek u -- <do uzlu>
datum vytvoření záznamu k ód administrativní jednotk y (seznam jednotek v CDMAB) délk a úsek u v metrech dopravní směry – 0 obousměrný úsek , 1 jednosměrný zda jde o paprsek či větev k řižovatk y (hodnoty: PAPRS, VETEV) k ód třídy k omunik ace – 1 dálnice, 2-4 silnice 1.-3. třídy číslo silnice prázdné není známo. Hodnoty U, R, P, O, K, I, F, prázdná číslo peážující (souběžné) k omunikace číslo evropsk ého silničního tahu pořadí úseku v celé silnici
Tabulka 2: Struktura tabulky VUSEKY.dbf 3.2.2.1
Formát CIS_USEKU
CIS_USEKU je zadáno formou dvou CIS_UZLU v jedné buňce. Formát tohoto pole popisuje regulární výraz
^[0-9]{4}[ABC]{1}[0-9]{3}[0-9\ ]{2}[0-9]{4}[ABC]{1}[0-9]{3}[0-9\ ]{0,2}$.
Z tohoto regulárního výrazu je zřejmé, že formát sloupce je naprosto nevhodný pro jakoukoli manipulaci prostřednictvím databázového stroje. V dnešní době sice již existují i SŘBD, které dokáží vyhledávat data v tabulkách pomocí regulárního výrazu, je ale velmi pravděpodobné, že půj de o operaci značně časově náročnou a proto je lepší se použití tohoto kódu jako primárního klíče vyhnout. 3.2.2.2
Formát SILNICE
Pole silnice udává číslo silnice. Toto pole má následující tvar:
3.2.3
●
1 až 71 – I. třída
●
101 až 648 – II. třída
●
0031 až libovolné pětimístné číslo – III. třída
●
formát <číslo> – nebyl zjištěn význam, může obsahovat číslo dálnice
Tabulka CDMAB.dbf
Tabulka obsahuje pouze dva využité sloupce – KOD a VYZNAM. Dále obsahuje sloupec ZKR, ten ale není na žádném řádku použit. KOD udává číslo administrativní jednotky a VYZNAM její název. Aby byla tabulka kompletní a mohli jsme se na ni odkazovat z relačně spojených tabulek, je třeba doplnit do ní ještě čtyři položky – kódy okolních států: SRN, SR, RAKOUS a POLSKO. Z jejich kódu je význam zřejmý. Jejich neuvedení v původní tabulce je porušením relačních vztahů databáze.
-7-
3.3
Výstupní data Jak již bylo zmíněno, původní databáze ve formátu dBase III zcela nevyhovuje požadavkům
na výkon a formát dat. Byla proto navržena nová databáze na platformě PostgreSQL. Databáze ob sahuje tyto tabulky:
Ilustrace 2: Struktura databáze
●
adm_units – seznam administrativních jednotek
●
edges – úseky (silnice)
●
node_types – druhy uzlů (křižovatek)
●
nodes – uzly
●
edges_systems – propojovací tabulka „systems“ s „edges“ (vztah M:N)
●
places – seznam pojmenovaných míst
●
roads – seznam silnic
●
systems – seznam silničních tahů
Ve většině tabulek byl vytvořen více než jeden index (nad primárním klíčem) – nad textový mi daty (jako je například původní číslo úseku či uzlu). Důvodem je značné zvýšení rychlosti při konverzi původní databáze na novou. Textová data totiž provizorně slouží jako primární klíč (spo jení s původní databází) a provádí se podle nich výběr. Tyto indexy mohou být později zrušeny, ne bude-li aplikace, která bude s databází pracovat, vyžadovat data v původním formátu.
-8-
Databáze v současné podobě nepodporuje uložení komplexních křižovatek, ty jsou reduková ny na jediný uzel. Taktéž nejsou do databáze uložena data s dosud neznámým významem, případně jsou uložena jen data, která lze zpracovat (jako v případě tabulky roads, kde nejsou dokonale zpra covávány informace ze vstupního sloupce VUSEKY.SILNICE).
3.3.1
Tabulka adm_units
Tabulka obsahuje údaje o administrativních jednotkách.
3.3.2
●
id – primární klíč
●
code – kód administrativní jednotky dle původní databáze ŘSD
Tabulka edges
Údaje o úsecích silniční sítě – silnicích.
3.3.3
●
id – primární klíč
●
from_node – výstupní uzel
●
to_node – vstupní uzel
●
lenght – délka úseku v metrech
●
road – informace o silnici příslušící k úseku, odkaz do tabulky roads->id
●
bidirectional – TRUE v případě, že jde o obousměrný úsek
●
canonical_name – původní jméno úseku dle ŘSD
Tabulka node_types
Druhy uzlů (křižovatek).
3.3.4
●
id – primární klíč
●
code – kód druhu uzlu dle ŘSD
●
name – název druhu uzlu
Tabulka nodes
Uzly silniční sítě – křižovatky.
3.3.5
●
Id – primární klíč
●
adm_unit1 – první administrativní jednotka (odkaz do adm_units->id)
●
adm_unit2 – druhá administrativní jednotka (odkaz do adm_units->id)
●
place – název místa, kde se uzel nachází (odkaz do places->id)
●
node_type – druh uzlu (odkaz do node_types->id)
●
canonical_name – původní název uzlu dle ŘSD
Tabulka edges_systems
Propojovací tabulka mezi tabulkami edges a systems. -9-
3.3.6
●
id – primární klíč
●
edge_id – odkaz do edges->id
●
system_id – odkaz do systems->id
Tabulka places
Pojmenovaná geografická místa (např. silnice prochází městem a zde se uloží jeho název).
3.3.7
●
id – primární klíč
●
name – název místa
●
code – IČZÚJ dle ŘSD (nekompatibilní s ČSÚ)
Tabulka roads
Silnice navázané k úsekům.
3.3.8
●
id – primární klíč
●
code – kód silnice dle ŘSD
●
class – třída silnice – 1 dálnice, 2-4 silnice I. až III. třídy
●
number – číslo silnice
Tabulka systems
Evropské silniční a dálniční tahy (např. E461, E50, …).
3.4
●
id – primární klíč
●
name – název tahu bez „E“, tj. jen 461, 50, …
Algoritmus převodu Celý algoritmus je snadno možno vyčíst z přiloženého zdrojového kódu, v následujících od
stavcích bude popsán zjednodušenou formou, která však postačí pro vytvoření základní představy o procesu převodu. Algoritmus byl realizován v programovacím jazyce Perl [3] kvůli jeho snadno čitelné syntaxi, dobré přenositelnosti a snadném rozšiřování pomocí přídavných programových mo dulů. Při návrhu struktury databáze a algoritmu převodu byly využity některé poznatky z diplomové práce Jana Koláře [4]. Na začátku běhu aplikace je nezbytná kontrola spojení s databází PostgreSQL a ověření exis tence vstupních souborů. Poté již může začít samotný převod. Program informuje o průběhu své práce vypisováním informací na standardní výstup. Jeho práce se dělí 8 relativně samostatných čás tí. Tyto není nutné provádět atomicky, je to však doporučeno kvůli zachování dokonalé integrity dat. Každý krok ovšem už atomický být musí. Dojde-li k neočekávanému přerušení běhu programu uprostřed některého z kroků, je nezbytně nutné databázi (nebo alespoň tabulku, na které se pra covalo) před pokračováním vyprázdnit. Při standardním běhu program automaticky pokračuje krok - 10 -
po kroku až do okamžiku, kdy je celá databáze převedena. Celý program realizuje následující kroky: 1. Převod uzlů (křižovatek) – Vyčtení veškerých uzlů z tabulky VUZLY.dbf a jejich prosté uložení (včetně originálního názvu). Prozatím není povolena možnost tvorby komplexních křižovatek. 2. Převod úseků (silnic) – Tento krok je již značně komplikovanější, je třeba dle originálního čísla úseku najít v nové tabulce uzlů odpovídající uzly a tyto dva prostřednictvím úseku spo jit. Taktéž je úsek doplněn o směrovost. V případě jednosměrnosti je nastaveno správné pořadí dat ve sloupcích from_node a to_node. 3. Vytvoření administrativních jednotek – Přenese se původní seznam z tabulky CDMAB.dbf, změní se jeho kódování na UTF-8 a připojí se k němu také kódy zemí, se kterými ČR souse dí. 4. Propojení administrativních jednotek s uzly – Znovu se projde původní tabulka uzlů a provede se propojení dle canonical_name v nové tabulce nodes. 5. Vytvoření tabulky míst a propojení s uzly – Opět se prochází původní tabulka uzlů a při řazují se k jednotlivým položkám místa z tabulky places. Není-li místo nalezeno, vytvoří se. 6. Propojení druhů křižovatek s uzly – Je naplněna tabulka node_types druhy křižovatek a je spojena s tabulkou nodes. 7. Propojení názvů silnic s úseky – Projde se tabulka úseků. Jednotlivým položkám je na stavováno příslušné umístění. V případě, že umístění v tabulce places dosud neexistuje, je vytvořeno. 8. Propojení silničních tahů s úseky – Stejný postup jako v předchozím kroku, jen je apli kován na silniční tahy. Dokončení převodu program oznámí na standardní výstup. V té chvíli máme k dispozici novou databázi naplněnou aktuálními daty.
4 Diskuse Celý algoritmus byl navržen s ohledem na jednoduchost. Je zřejmé, že některé kroky by moh ly být prováděny současně (např. vytvoření uzlu a současně přiřazení administrativní jednotky k uzlu). Tento přístup by však následně znesnadnil správu kódu a zbytečně zvýšil jeho složitost na úkor čitelnosti a snadné pochopitelnosti. Jak již bylo na několika místech zmíněno, algoritmus prozatím nedokáže vytvářet komplexní křižovatky. Každou takovou nahradí jednoduchým uzlem. Tento postup vnáší do databáze ne
- 11 -
přesnosti jelikož neznáme délku trasy z jedné části křižovatky do druhé, což se může u některých tras projevit podhodnocením celkové délky trasy. Tento nedostatek je poměrně snadno řešitelný a bude zřejmě opraven v některé z novějších verzí programu. Dalšími možnými vylepšeními je například odhad časové náročnosti převodu na konkrétním počítači, analýza obsahu databáze před začátkem převodu či možnost spuštění jen některých kroků programu.
5 Závěr Realizace tohoto programu nám dala možnost vystavět na jím vygenerované databázi aplika ce, týkající se grafových algoritmů – hledání nejkratší cesty, různé analýzy silniční sítě a podobně. Největším problémem nebyla samotná realizace, tj. naprogramování převodních algoritmů, nýbrž analýza vstupních dat. Pokud by v době návrhu existoval dostatek dokumentace, byla by i doba rea lizace mnohem kratší a je pravděpodobné, že by výsledek obsahoval mnohem více dat příslušících jak k uzlům, tak k úsekům silniční sítě. Program byl vyvíjen na 64-bitovém linuxovém počítači s následující konfigurací: Intel Cele ron 220 1,2 GHz, 1 GiB DDR2/533 RAM, CentOS 5.1 x86_64, Perl 5.8.8, PostgreSQL 8.1.11. Testovací běh programu s lokálně připojenou databází zabral necelých 31 minut. Výstupní databáze má (vzhledem k použití indexů na textové sloupce) 43 MiB. Tabulka edges asi 31 tisíc a tabulka nodes asi 22 tisíc záznamů. Zdrojový kód programu rsd2mroute je volně k dispozici na adrese lu.cz/~xgrmela1/gpl-sw/mroute/
http://akela.mende
pod licencí GNU GPL 3 nebo novější. Vstupní data jsou k dispo
zici na stránkách Silniční databanky [5].
- 12 -
6 Seznam použité literatury [1] Více autorů. Wikipedia: dBase . Wikimedia , 2008 [2] Environmental Systems Research Institute. ESRI Shapefile Technical Description. ERSI, 1998. [3] DOSTÁL, Ivo. Hodnocení stávající dopravní infrastruktury a variant jejího plánovaného rozvoje z hlediska záboru půdy a vlivů na morfologii a fragmentaci krajiny. Centrum dopravního výzkumu, Ministerstvo dopravy ČR, 2004 [3] DAŘENA, František. Myslíme v jazyku Perl. Grada, 2005. ISBN 80-247-1147-8 [4] KOLÁŘ, Jan. Implementace algoritmů prohledávání dopravní sítě v prostředí PostgreSQL – diplomová práce. VŠB – TU Ostrava, 2006. [5] Více autorů. Využití informační základy Silniční databanky Ostrava .
Ředitelství silnic a dálnic ČR, 2008.
- 13 -
