Kartografické modelování IX – síťové analýzy vzdáleností jaro 2014 Petr Kubíček kubicek@geogr.muni.cz Laboratory on Geoinformatics and Cartography (LGC) Institute of Geography Masaryk University Czech Republic Kartografické modelování Analýzy nad vektorovou sítí • Analýzy sítí jsou významnou oblastí aplikace GIS. • V podstatě se jedná opět o hledání nejkratší vzdálenosti, ale s tím rozdílem, že sítě jsou vektorovou reprezentací. • Síť tvoří (orientovaný) ohodnocený graf, skládající se z uzlů (průsečíků) a hran (linií). Kartografické modelování Tvorba sítě • Před využíváním síťových analýz je nutné vytvořit všechny datové struktury, které jsou pro pozdější analýzy nutné – tedy vytvořit síť. • Postup tvorby sítě: – Je třeba získat liniovou vrstvu, nad kterou budou analýzy prováděny (ulice, rozvody, kanalizace). – Tato data musí být topologicky čistá (hlavně musí splňovat konektivitu a znalost směru) – nutná a v zásadě postačující podmínka pro analýzy sítí. – Následně lze síti přiřadit pravidla, která určují, jak je možné se pohybovat mezi jednotlivými uzly. – Přiřazení dalších atributů pro výstupy z analýz (zejména itineráře) – přidání jmen ulic, významných bodů (adres), názvy křižovatek, … Kartografické modelování Pravidla pohybu po síti Pravidla uzlová a hranová: • Uzlová pravidla definují směr pohybu uzlem. – Například, pokud budu mít uliční síť, na některých křižovatkách není povoleno odbočení doleva či doprava. • Hranová pravidla definují směr a rychlost pohybu po hraně. – Ulice mohou být jednosměrné, uzavřené, s nadefinovanou maximální a průměrnou rychlostí. • Pravidla mohu definovat pro různé druhy dopravy, pro různou denní dobu, … atd. • Pravidla jsou obvykle uložena v atributových tabulkách. • Poznámka: protože změna atributu nemusí vždy přijít pouze v uzlu (například změna max. povolené rychlosti), využívá se někdy speciální datový model pro liniové vrstvy – dynamickou segmentaci. Dynamická segmentace a lineární referencování Kartografické modelování Vlastnosti Pravidla umožní simulovat následující vlastnosti: • Cena cesty (pomocí max. rychlosti, času cesty a vzdálenosti) – základní atribut síťových dat, hrana musí obsahovat tento atribut vyjádřený alespoň jedním z těchto způsobů. • Lze vytvořit i další modifikace cen cesty: – Může se měnit s denní dobou – ráno, odpoledne, v noci. – Může záviset na směru průchodu hranou či uzlem (cesta tam je časově kratší, než cesta zpět, odbočení doprava je kratší než zabočení doleva). – Změna atributu může v reálném světě přijít kdykoli na linii a ne jen v uzlu (např. změna maximální rychlosti). Pokud nemáme možnost do našeho modelu implementovat cesty (routes), pak je nutné linie rozdělit na více segmentů spojenými uzly. Kartografické modelování Vlastnosti Směrování – přikázané směry jízdy, zákazy (speciální uzlová pravidla), včetně speciálních zákazů pro určité typy pohybujících se objektů (do ulice nesmí nákladní vozidlo) a přiřazení cen za provedení změny směru. Kartografické modelování Vlastnosti Neuzlové body – díky topologickému požadavku konektivity (linie se mohou protínat pouze v uzlových bodech) je třeba vyřešit situace, kdy je třeba modelovat podjezdy a nadjezdy. K tomuse obvykle používají dvě metody: • neplanární uzel – systém povolí protnutí liniových prvků bez nutnosti vytvoření uzlových bodů takže pro tento bod neexistuje křižovatka. • planární uzel – systém protíná liniové prvky pouze v uzlech, pak je nutné zadat takové uzlové atributy, které systém informují zda se jedná o křižovatku nebo o podjezd či nadjezd. Kartografické modelování Vlastní analýzy nad sítí • Hledání optimální trasy – jde o vyhledání optimální trasy mezi dvěma nebo více body (ve stanoveném pořadí nebo bez) na základě ceny cesty (vzdálenost, čas, …). Analýza umí produkovat i pokyny o cestě pro řidiče. Kartografické modelování Vlastní analýzy nad sítí Hledání cesty do nejbližšího zařízení – drobná modifikace předchozí analýzy. Jde o vyhledání optimální trasy do nejbližšího (optimálního) zařízení. • Příklad: Hromadná dopravní nehoda ve velkém městě. Jde o to, nalézt co nejrychlejší způsob, jakse k nehodě dostat sanitkou.Řešení je nalezení optimální cesty od optimálního zařízení k nehodě. • Je možné ještě hledat optimální cestu od nehody do nejbližší nemocnice.Tyto cesty totiž vzhledem ke konfiguraci sítě (jednosměrky) či vzhledem k času (ucpané ulice v určitém v důsledku nehody) nemusí být stejné! Kartografické modelování Vlastní analýzy nad sítí Alokace zdrojů – další možnost aplikace analýzy sítí. • Vyhledání všech lokalit, které jsou od vybraného objektu vzdáleny nějakou cenu cesty. • Příklad: vzdálenost do 30 minut od vyhlášené restaurace. Jak je vidět, je to analýza podobná vytváření obalových zón (buffers), ale bere v úvahu cenu cesty definovanou pomocí sítě (není to jen vzdálenost vzdušnou čarou). • Výsledkem této analýzy jsou tzv. izochrony, což jsou čáry spojující body se stejným časem k dosažení výchozího bodu. Kartografické modelování Vlastní analýzy nad sítí • Problém obchodního cestujícího – návštěva vybraných bodů tak, aby trasa byla optimální. • Cestující musí navštívit každý bod (místo) a na závěr se vrátit do původního bodu. • Aplikační využití při rozvoru balíků, obsluze automatů… Kartografické modelování Úseky a uzly Kartografické modelování Vlastnosti úseků • Delka_us - délka silničních úseků vyjádřená v metrech • Kod_tr_kom - kód třídy komunikace Kartografické modelování Uzly Kartografické modelování Ohodnocení úseků hran • Metrika? • čas, potřebný pro pohyb v síti silničních komunikací. • Délka komunikací (hran) a průměrná rychlost=čas. Kartografické modelování Ohodnocení úseků • Pro úseky silnic jednotlivých tříd jsou přiřazeny průměrné rychlosti a vypočítán čas potřebný k jejich překonání. Kartografické modelování Dijkstra algoritmus Algoritmus sloužící k nalezení nejkratší cesty v grafu. Je konečný (pro jakýkoliv konečný vstup algoritmus skončí), protože v každém průchodu cyklu se do množiny navštívených uzlů přidá právě jeden uzel, průchodů cyklem je tedy nejvýše tolik, kolik má graf vrcholů. Funguje nad hranově kladně ohodnoceným grafem. Kartografické modelování Kartografické modelování Kartografické modelování Kartografické modelování Kartografické modelování Kartografické modelování Dijkstra algoritmus