Fakulta Informatiky, Masarykova Universita v Brně Fólie k přednášce PV019 - Úvod do geoinformačních systémů Fl MUNI, Drášil 2011 1 Úvod do GIS I 1. Geoinformační systém, místo na povrchu Země. 1.1. Vymezení pojmu GIS Příklad 1 - Informační systém o nemovitostech Katastrální úřady evidují vlastnické vztahy fyzických a právnických osob k nemovitostem (budovám a pozemkům). Poloha nemovitostí je zaznamenána v katastrálních mapách. Fl MUNI, Drášil 2011 2 Úvod do GIS I Uvažujme „klasický" informační systém o nemovitostech s datovým modelem v relačním databázovém systému, entity systému jsou navrženy v E-R diagramu. Klasický IS je schopen reagovat na dotazy typu: • kdo vlastní parcelu ..?. • jaké parcely vlastní osoba ...?; jakou cenu mají parcely, které vlastní osoba ...? GIS jsou navrhovány tak, aby byly schopny reagovat na dotazy typu: • kde se nalézá parcela ...? • jaké typy parcel se nalézají v daném regionu ...? • Jakou výměru parcel vlastní daný oprávněný subjekt Fl MUNI, Drášil 2011 3 Úvod do GIS I Vymezení pojmu GIS: GIS je jakýkoliv manuálně nebo počítačově založený soubor postupů užívaných k ukládání a manipulování geograficky vztažených dat. Geograficky vztažená data mají dvě složky: • fyzikální rozměr respektive třídu (průměrná výška stromů v lese, počet obyvatel města, šířka silnice respektive typ sídla, typ vegetace, geomorfologický typ, apod.) • lokalizační složku, instance je vztažena k zemskému povrchu Typy GIS - tradiční dělení • Land Information System (LIS), Land Related Information System (LRIS), územně orientovaný informační systém -speciální případ GIS v podrobnosti velkého měřítka, který zahrnuje vlastnické vztahy (hranice parcel a informace o vlastnících parcel). • Geoinformační systém - systém pracující s daty, která lze lokalizovat v území, ale ne vždy je lze považovat za geografická (umístění vodovodního šoupátka, dopravní značky). • Grafický informační systém - systém pracující s obrazovými daty, která nemá smysl lokalizovat v nějakém Qednotném) prostoru. • V poslední době toto dělení ztrácí smysl, po geoinformačních systémech je požadována komplexní funkcionalita. Fl MUNI, Drášil 2011 4 Úvod do GIS I 1.2. místo na zemském povrchu Geoid (1871 Listing) - Matematické těleso, model povrchu Země. Ekvipotenciální plocha vůči zemské gravitaci, která se nejvíce přimyká ke střední klidové hladině oceánu. Plocha se stejnou úrovní tíhového potenciálu způsobeného gravitací Země. Rovina místního poledníku - je rovina určená osou rotace Země a určovaným bodem. Zeměpisná délka 00 - úhel, který svírá rovina místního poledníku procházejícího určovaným bodem a rovina nultého poledníku. Udává se většinou v úhlových jednotkách [-180°, 180°] Zeměpisná šířka (g>) - úhel, který svírá rovina rovníku a přímka procházející středem Země a určovaným bodem. Udává se většinou v úhlových jednotkách [-90°, 90°]. Souřadnice [q>, X] jednoznačně určují místo na zemském povrchu. Loxodroma - křivka, která protíná poledníky pod stejným úhlem. Ortodroma - nejkratší spojnice dvou bodů, v případě kulového modelu Země kratší oblouk hlavní kružnice. 1.3. Kde jsem? Stručný pohled do historie Eratosthenes (cca. 240 před n. I.) Pravděpodobně první dochovaný pokus změření zemského obvodu s popisem metody. Úhlová metoda, změření maximální výšky slunce na dvou místech na stejném poledníku ve stejný čas. Byla vybrána města Alexandrie a Syéné (dnešní Asuán). Fl MUNI, Drášil 2011 5 Úvod do GIS I Poměr rozdílu úhlů dopadajícího slunečního paprsku (v poledne) a velikosti kruhového oblouku mezi dvěma místy na stejném poledníku Poměr 27i a obvodu Země Vzdálenost Alexandrie a Syéné byla změřena na 5000 stádií (záznamy obchodníků, pochodující legie), úhlový rozdíl slunečních paprsků by změřen na cca. 2%/50 Úhel byl měřen za slunovratu v Alexandrii, úhel slunce v poledne za slunovratu v Syéné byl znám jako %/2, sloupy kolmé k zemi nevrhaly stín -místo leží přibližně na obratníku Raka. Obvod Země = 50 x 5000 = 250 000 stádií 1 stadion = 177.6 metrů, obvod Země je tedy 44 400 000 m. Fl MUNI, Drášil 2011 6 Úvod do GIS I Geometrický princip Eratosthenovy metody P - maximální výška slunce za slunovratu v Alexandrii y - maximálni výška slunce za slunovratu v Syéné ( = %/2) a - středový úhel mezi Syéné a Alexandrií i' »> ■>» * •¥ >'i; -'it «. * «> ■'• , '•, ~ ijfi i< ii ú i, >>■ „. (I1 , Á, (včetně volby základního poledníku) - Zobrazovací rovnice do rovinných souřadnic - Souřadný systém rovinných souřadnic X,Y Fl MUNI, Drášil 2011 18 Úvod do GIS I 2.2. Nejpoužívanější souřadné systémy v ČR Civilní souřadnicový systém S-JTSK'\e určen - Besselovým elipsoidem z roku 1841 s referenčním bodem Herrmanskogel, zeměpisné délky se určují od ferrského poledníku, zobrazovací rovnice dvojitého konformního kuželového zobrazení v obecné poloze (Křovákovo zobrazení) s volbou délkového faktoru 0.9999 pro snížení vlivu délkového zkreslení. Vojensky souřadnicový systém S-42 je určen Krasovského elipsoidem z roku 1942 s referenčním bodem Pulkovo, zeměpisné délky se měří od Greenwiche, zobrazovací rovnice Gaussova-Krúgerova zobrazení s opakovatelností vždy pro šestistupňové poledníkové pásy. Od r. 2005 je nahrazen WGS84 - zobrazení UTM (Universal Transversal Mercator) Souřadný systém WGS 84 - Word Geodetic System 1984 Systém byl původně definován Ministerstvem obrany USA pro obranné účely, dnes je celosvětově používanou technologií prostorové lokalizace. UTM (Universal Transversal Mercator) - Systém transverzálního válcového zobrazení používající elipsoid WGS 84. Jsou použity šestistupňové pásy. Cassini-Soldner - Válcové zobrazení na Záchově elipsoidu s referenčními body Sv. Štěpán, resp. Gusterberg. Definováno v Rakousko Uherské monarchii pro stabilní katastr v měřítkách 1:2800 a 1:1440 (dodnes používaná). ETRS-LAEA: ETRS89 (Lambert Azimuthal Equal Area) -Elipsoid ETRS89 (téměř shodný s WGS 84), azimutální zobrazení používané pro střední a malá měřítka. Fl MUNI, Drášil 2011 19 Úvod do GIS I 2.3. Transformace souřadných systémů Problém: Mapy různých kartografických zobrazení transformovat do zobrazení cílového. Základem je znalost, jak transformovat bod. Přímá transformace 1. Zdrojové souřadnice [x,y] převedeme na geografické souřadnice zdrojového systému [q>, A]. 2. [q>,A] transformujeme do cílových geografických souřadnic [q>', A' ] 3. Geofrafické souřadnice [q>', A' ] převedeme do cílového rovinného zobrazení [x',y'] Transformace geografických souřadnic: 1. Geografické souřadnice [ [Xí',Yí'] určíme koeficienty polynomiální transformace a tuto potom použijeme pro jednotlivé body. Používáme polynomy do 3. stupně, vyšší stupeň vede k nestabilitě řešení (omezený počet platných cifer). Používá se v případech, kdy: • Není známá zdrojová kartografická projekce prostorových dat. • Zdrojová projekce je sice známá, avšak je zatížena takovou chybou, že obecná polynomiální transformace dává lepší výsledky. • Zdrojová projekce je známá, ale její výpočet je příliš náročný vzhledem k počtu geometrických elementů a polynomiální transformace výsledek významně nezkreslí. V tomto případě použijeme kartografickou transformaci pro generování sítě odpovídajících si bodů (např. rohové body dotazového okna) a tyto body potom použijeme pro výpočet transformačního klíče. Fl MUNI, Drášil 2011 21 Úvod do GIS I Základní typy polynomiálních transformací: Lineárni: x = f (u, v) = aiu + biv + ci y = g(u,v) = a2u + b2v + c2 Bilineární: f (u, v) = aiu + biv + Ciuv + di g (u, v) = a2u + b2v + c2uv + d2 Kvadratická, kubická, obecná polynomiální... Nalezení koeficientů polynomiální transformace: Vstup: Dva seznamy „odpovídajících" si bodů: { [xi,yi] . . [xn,yn] } { [Ui,Vi] . . [un,vn] } Výstup: Seznam koeficientů polynomiální transformace zvoleného stupně. Transformujeme [u,v] do [x,y] s co nejmenší chybou, tedy: Sdist2 ( [Xi,yi] , [f (Uí,Ví) ,g(Ui,v±) ]) = min kde dist2 ( [xi,yi] , [x2,y2] ) = (xi-x2)2+ (yi-y2)2 Fl MUNI, Drášil 2011 22 Úvod do GIS I Lineární regrese (příklad pro lineární transformaci): (E označuje sumu pro všechny dvojice odpovídajících si bodů) Z = £ (aiUi+biVi+Ci-Xi) + (a2Ui+b2Vi+C2-yi) = min Výraz Z derivujeme podle proměnných ax. . c2 a derivaci položíme rovnu 0 (hledání extrémů funkcí více proměnných). diľ/dai = E 2 (aiUi + biv± + ci - x±) .u± = 0 cLZ/dbi = E 2 (aiUi + biv± + Ci - x±) .v± = 0 diľ/dci = E 2 (aiUi + biv± + ci - x±) = 0 ■ ■ Dostáváme soustavu tzv. normálních rovnic (pro g(u,v) analogicky): ai Sui2 + bi EuíVí + Ci Eu± = ExíUí ai EuíVí + bi Ev±2 + ci Ev± = ExíVí ai Euí + bi Eví + Ci .n = Ex± Fl MUNI, Drášil 2011 23 Úvod do GIS I Příklad: Ukázka zdrojového kódu pro převod geografických souřadnic do systému S-JTSK. Je zřejmé, že použití např. bilineární transformace je mnohem méně výpočtově náročné, v některých případech (např. pro rastrový obrázek 1024*1024 pixelů) hodně významně. public override bool FromEllipsoid ( double lat, double Ion, double alt, ref double x, ref double y, ref double h ) { try { Double dpom; Double de, dsfi; Double du, dv, ddeltav; Double ds, dd; Double dro, depsilon; Double xx, yy; /* konstanty Besselova elipsoidu */ Double consta = 6377397.15508; Double constb = 6356078.962 90; /* konstanty */ Double constalfa = 1.00059749837159; Double constr = 6380703.610617; Double constk = 0.996592486879232; /* uhel v radianech odpovidajici 45 */ Double constu45 = 0.785398163397448; /* uhel v radianech odpovidajici 78:30 */ Double constu7830 = 1.3700834 62815548; /* uhel v radianech odpovidajici 59:42:42.6969 */ Double constuk = 1.042168563853224; /* uhel v radianech odpovidajici 42:31:31.41725 */ Double constvk = 0.742208135432484; /* uhel v radianech odpovidajici 17:39:59.7354 */ Double constferra = 0.308340218368665; /* převod vzhledem k ferra */ Ion += constferra; /* převod lat,Ion (Bessel) -> u,v (Gaussova koule) */ dv = constalfa * Ion; de = Math.Sqrt(consta * consta - constb * constb) / consta; dsfi = Math.Sin(lat); dpom = (1 - de * dsfi) / (1 + de * dsfi) ; Fl MUNI, Drášil 2011 24 Úvod do GIS I dpom = Math.Pow(dpom, de / 2); dpom = dpom * Math.Tan(lat / 2 + constu45); dpom = Math.Pow(dpom, constalfa) / constk; du = 2 * (Math.Atan(dpom) - constu45); /* prevod u,v (Gaussova koule) -> s,d (sirka,delka) */ ddeltav = constvk - dv; dpom = Math.Sin(constuk) * Math.Sin(du) + Math.Cos(constuk) * Math.Cos(du) * Math.Cos(ddeltav); ds = Math.Asin(dpom); dd = Math.Asin(Math.Sin(ddeltav) * Math.Cos(du) / (ds)) ; /* prevod s,d -> x,y (rovinne, JTSK) */ dpom = Math.Tan(constu7830 / 2 + constu45) / Math.Tan(ds / tu45); dpom = Math.Pow(dpom, Math.Sin(constu7830)); dro = dpom * 0.9999 * constr / Math.Tan(constu7830); depsilon = Math.Sin(constu7830) * dd; x = dro * Math.Cos(depsilon); y = dro * Math.Sin(depsilon); h = alt; return (true); } catch { return (false); } } Fl MUNI, Drášil 2011 25 Úvod do GIS I 2.4. Tradiční mapy a pojmy související s GIS . Mapovaní - vytváření map měřením nebo fotogrammetrickým mapováním pomocí geodetických základů - bodů geodetických sítí. Mapa je 2D obraz zemského povrchu. . Měřítko mapy-v GIS kontextu neznamená poměr skutečné a zobrazované velikosti objektů. Měřítkem mapy se spíše rozumí úroveň územní podrobnosti obsahu geografického informačního systému. . Dálkový průzkum Země (DPZ) - získávání informací o zemském povrchu a jeho blízkém okolí pomocí snímacích zařízení (kamery, skenery) umístěných v letadlech nebo družicích . Topografická mapa - je grafická prezentace (zobrazení) části zemského povrchu se standardizovaným obecným obsahem (voda, lesy, komunikace, objekty viditelné na zemském povrchu..) . Tématická mapa - zobrazení geografických dat a jevů v topografickém podkladu pomocí grafické reprezentace prostorových dat: bodů, linií a areálů. Metody reprezentace: bodové značky, lokalizované kartodiagramy, kartodiagramy, symbologie čar, kartogramy. Fl MUNI, Drášil 2011 26 Úvod do GIS I 2.5. Mapové dílo v ČR Mapy velkých měřítek do 1:5000 - katastrální mapy (mapy stabilního katastru) v systému Cassini-Soldner (počátek Gusterberg v Čechách, Sv. Štěpán na Moravě) v sáhových měřítkách 1:2880, 1:1440, 1:720 (měřítko je odvozeno ze vztahu 1 jitro - 1600 čtverečních sáhů - je zobrazeno jako čtvereční palec), ale v dekadických měřítkách - katastrální mapy v S-JTSK (systém jednotné trigonometrické sítě katastrální - Křovák), měřítka 1:1000 ve městech (intravilán), 1:2000 v extravilánu vznikaly po roce 1928 - Státní mapa odvozená v měřítku 1:5000, systém JTSK, obsah: vlastnické hranice, polohopis (vnitřní kresba) - Digitální katastrální mapa - mapa vedená digitálně, postupně ji vytvářejí katastrální úřady Státní mapové dílo velkých měřítek v České republice vznikalo v průběhu dvou století. Mapové dílo je charakteristické svou rozmanitostí a rozdílnou kvalitou (především vzhledem k přesnosti a aktuálnosti mapy). Mapy středních měřítek 1: 10000 až 1: 200 000 - Základní mapa středního měřítka - v měřítkách 1:10000, 1:25000, 1:50000, 1:100000, 1:200000 s obsahem topografické mapy, v digitální formě mapové dílo ZABAGED. - Topografická mapa GŠ ČSA, měřítko 1:25000 (v některém území i 1:10000) Fl MUNI, Drášil 2011 27 Úvod do GIS I 3. Datové sklady geoinformačních systémů 3.1. Typy prostorových dat Vektorová data - reprezentují objekty pomocí datových struktur, jejichž základní položkou je bod 2-rozměrného spojitého (euklidovského) prostoru. Termínem "spojitý" myslíme spojitý, až na technické omezení použité počítačové aritmetiky. Rastrová data - podmnožina 2D prostoru je pravidelně rozdělena (většinou čtvercovou) sítí, každý element této sítě je nositelem tématické části (geografické) informace. Prostorová lokalizace je určena indexem elementární složky sítě, popřípadě jeho zobrazením do cílového (kartografického) souřadného systému. Grid data - Základem této reprezentace je opět pravidelná síť položená na 2D prostor. Rozdíl oproti rastrovým datům spočívá v tom, že tématická část informace je získávána na základě předem definované sítě, kterou je rozděleno zájmové území. Topologie - vymezuje vztahy mezi entitami (objekty) systému, aniž by obsahovala umístění objektu v prostoru. Například informační systémy o spojení míst silniční sítí nevyžadují přesné umístění uzlů v prostoru, pracují pouze s relací na množině všech uzlů. Fl MUNI, Drášil 2011 28 Úvod do GIS I 3.2. Rastrové datové sklady Využívají běžné formáty obrazových dat (bmp, png, jpeg tif, gif,ecw..). Některé z nich mohou mít informace o vztahu k souřadnicím kartografické projekce přímo ve své hlavičce (ecw, tif) u ostatních se používá „doplňující" textový soubor (*.tfw), který obsahuje parametry lineárního převodu z/do pixelových do/z kartografických souřadnic. Nechť [i, j]jsou pixelové souřadnice, [x,y]kartografické souřadnice x = ax * i + bx * y + cx y = aY * i + bY * y + cY tfw soubor je potom textový soubor obsahující parametry Cx f 3-X f bX f Cy f a.y f by. Příklad tfw souboru: 12.7011007620660457239627434377653 0 0 -12.701100762066045723962743437765 -775450 -965225 Poznámka: V naprosté většině případů je bx = 0 a ay= 0. To znamená, že osy obrázku jsou rovnoběžné s osami kartografického zobrazení. Fl MUNI, Drášil 2011 29 Úvod do GIS I 3.3. Vektorové datové sklady Pro fyzickou reprezentaci je možné použít vlastních datových struktur a ukládat je přímo ve file systému operačního systému. Přes nesporné výhody tohoto přístupu, jako je optimalizace uložení prostorové složky informace, převažují nevýhody, zejména aplikační závislost. Běžnější přístup je použití robustních databázových strojů, které vektorovou geometrii běžně používají (Oracle, Microsoft SQL-Server, MySQL). Není jednotný standard ukládání vektorové geometrie. Nejpoužívanější veřejné formáty: Shape file (systém ARC/INFO fy. ESRI) Geograficky vztažená informace je obsažena ve trojici souborů • *.shp prostorová informace • *.shx prostorový index • *.dbf popisná informace a topologické vazby Základní geometrické primitivy: Point bod MultiPoint body Line lomená čára MultiLine lomené čáry Polygon areál MultiPolygon areály Vše 2D a 3D varianty. Norma neobsahuje symbologii (barva, síla, styl linií, výplň polygonu). Tu obsluhuje aplikace na základě popisných informací. Norma neobsahuje „heterogenní" kolekce geometrií a tím i definici mapových symbolů. Jako mapové symboly jsou použity speciální znakové sady (fonty). Fl MUNI, Drášil 2011 30 Úvod do GIS I Shape file byl jedním z prvních obecně používaných formátů, dodnes je podporován většinou „velkých" geoinformačních systémů. DGN file, norma IGDS (Intergraph, Bentlev) Geometrická informace je obsažena v souboru *.DGN, soubor sám o sobě nenese popisnou informaci, taje uložena v relační databázi (nebo *.dfb souboru), DGN soubor obsahuje pouze tzv. „link" = společný klíč v souboru/databázi. Základní geometrické primitivy: cell header elm Hlavička buňky line elm Úsečka line string elm Lomená čára shape elm Polygon text elm Text text node Textový uzel curve elm Křivka cmplx string elm Komplexní linie cmplx shape elm Komplexní polygon ellipse elm Elipsa arc elm Oblouk point string elm Body bspline elm B-spline dimension elm Kóta • Komplexní linie se mohou skládat z různých segmentů -např. lomených čar a oblouků. • Geometrie obsahuje symbologii geometrických primitiv. • Typ cell může opět obsahovat buňku. Podobné vlastnosti mají i ostatní CAD formáty (DXF, DWG..) Fl MUNI, Drášil 2011 31 Úvod do GIS I Bohatý repertoár geometrických primitiv CAD formátů umožňuje i definici mapových symbolů. Problematickejšou interpretace nelineárních geometrií v různých klientských aplikacích (např. B-spline) a složitějších zobrazovacích symbolik (např, linie vzorovaná symbolem). Dalším problémem jsou operace na složitějšími geometriemi (např. průnik polygonů, jejichž hranice se skládají z lomených čar, eliptických oblouků ...). Příklad: Definice složitého mapového symbolu (Sídla Městského úřadu v GIS pro města). Je zřejmé, že v takovém případě je výhodné mít k dispozici robustní CAD formát vektorových dat, u kterého si každý geometrický element nese i „default" symbologii kresby. Fl MUNI, Drášil 2011 32 Úvod do GIS I ORACLE 7x (Spatial Data Option): Geometrie je reprezentována čtyřmi tabulkami: _sdolayer - obsahuje služební údaje pro prostorovou indexaci _sdodim - obsahuje rozsah pro jednotlivé dimenze geometrie _sdogeom - obsahuje vlastní geometrii _sdoindex - obsahuje prostorové indexy objektů možné typy geometrie jsou: bod, lomená čára a areál, Jednalo se o první pokus o standardizaci geometrie - ten se vlivem denormalizace uložení souřadnic ukázal jako slepá ulička, v současné době není rozvíjen. Fl MUNI, Drášil 2011 33 Úvod do GIS I ORACLE 8x a vyše - datový typ S DO GEOMETRY: unknown geometry neznámá geometrie point bod linestring lomená čára polygon areál (oblast) collection kolekce geometrií multipoint Body multilinestring více linií mutipolygon více areálů • Linie jsou tvořeny sekvencemi bodů a kruhových oblouků. • Typ COLLECTION nemůže obsahovat typ COLLECTION. • Definice neobsahuje symbologii geometrických primitiv. Open GIS Consortium, Inc. Je sdružení soukromých, veřejných organizací (universit, komerčních firem..) se zájmem na vybudování „standardu" struktur a služeb v prostorových datech. I přes byrokratickou těžkopádnost způsobenou množstvím subjektů, které se účastní vývoje standardů lze konstatovat, že standardy OGC jsou poměrně rozšířeny a podporovány (např. Oracle podporuje konverzi datových typů, prostorová informace MySQL je přímou implementací OGC), i když původní proklamace zní s odstupem času až úsměvně. Our Vision - is a world in which everyone benefits from geographic information and services made available across any network, application, or platform. Our Mission - is to deliver spatial interface specifications that are openly available for global use. Fl MUNI, Drášil 2011 34 Úvod do GIS I OGC Well known binary: Je norma binárního ukládání vektorové geometrie včetně C-definic: // Basic Type definitions // byte : 1 byte // uint32 : 32 bit unsigned integer (4 bytes) // double : double precision number (8 bytes) // Building Blocks : Point, LinearRing Point { double x; double y; }; LinearRing { uint32 numPoints; Point points[numPoints]; } enum wkbByteOrder { wkbXDR = 0, // Big Endian wkbNDR = 1 // Little Endian }; WKBPoint { byte byteOrder; uint32 wkbType; // 1 Point point; }; WKBLineString { byte uint32 uint32 Point byteOrder; wkbType; // 2 numPoints; points[numPoints]; }; Fl MUNI, Drášil 2011 35 Úvod do GIS I WKBPolygon { byte uint32 uint32 LinearRing }; byteOrder; wkbType; // 3 numRings; rings[numRings]; WKBMultiPoint { byte uint32 uint32 WKBPoint }; byteOrder; wkbType; // 4 num_wkbPoints ; WKBPoints[num wkbPoints]; WKBMultiLineString { Byte byteOrder; uint32 wkbType; // 5 uint32 num_wkbLineStrings ; WKBLineString WKBLineStrings[n\am_wkbLnStrgs] }; wkbMultiPolygon { byte byteOrder; uint32 wkbType; // 6 uint32 n\am_wkbPolygons ; WKBPolygon wkbPolygons [n\am_wkbPolygons] ; } WKBGeometry { union { WKBPoint WKBLineString WKBPolygon WKBGeometryCollection WKBMultiPoint WKBMultiLineString WKBMultiPolygon } point; linestring; polygon; collection; mpoint; mlinestring; mpolygon; }; Fl MUNI, Drášil 2011 36 WKBGeometryCollection { Byte by te_order ; uint32 wkbType;// 7 uint32 num_wkbGeometries; WKBGeometry wkbGeometries[num_wkbGeoms] ; } Základní datové typy WKB neumožňují vykreslit mapu, neobsahují: • Symbologie (grafická reprezentace - barva, síla, tloušťka) geometrických elementů • reprezentace bodových prvků, mapové symboly • texty (velikost, rotace, font...) Definice WKB neobsahuje definici kruhových oblouků, což může působit obtíže při práci v měřítkách, kde platí Euklidovská geometrie a „kružítko" běžně používáme. Rekurzivní definice WKBGeometryCollection umožňuje i definici mapových symbolů. GML - Geoqraphic Markup Lanquaqe: Norma WKB v XML formátu Formát GML definuje XML reprezentaci geometrie, popisnou část informace nijak neomezuje. Vzhledem k masivní podpoře XML parserů mnoha vývojových prostředí se zřejmě jedná výměnný „formát budoucnosti". Pro ukládání prostorových informací je však nevhodný, jeho velikost je oproti binárnímu formátu až desetinásobná. Verze 3.2 této normy už podporuje složitější geometrické primitivy (kruhový oblouk, křivka, ...). Fl MUNI, Drášil 2011 37 Úvod do GIS I Príklad GML: " 541484 .77 1113662 .92 541484 .36 1113666. 36 541476 .26 1113665 .3 541469 .89 1113664. 51 541469 .62 1113662 .23 541453 .022 1113662 .01 541452 .31 1113662 .01 541451 .77 1113664. 1 541446 .27 1113662 .85 541446 .96 1113668. 85 541438 .25 1113668 .81 541440 .74 1113661. 7 541432 .057 1113660 .152 541427 .45 1113659. 33 541426 .737 1113661 .296 541425 .54 1113664. 6 541419 .741 1113662 .802 541401 .42 1113657. 12 541397 .74 1113655 .81 541391 .63 1113653. 68 541394 .736 1113649 .478 541395 .23 1113648. 81 541407 .55 1113652 .235 541427 .96 1113657. 91 541438 .177 1113658 .825 541438 .209 1113658. 828 541440 .8 1113659 .06 541469 .46 1113660. 94 541484 .77 1113662 .92 9 Fl MUNI, Drášil 2011 38 Úvod do GIS I OGC specifikace pro ukládání prostorových informací v relačních databázích: OpenGIS Simple Features Specification For SQL metamodel GEOMETRY COLUMNS ■F_TABLE_CATALOG ■ F_TABLE_SCHEMA -F_TABLE_NAME ■ F_GEOMETRY_COLUMN G_TABLE_CATALOG— G_TABLE_SCHEMA- G_TABLE_NAME- STORAGE_TYPE- GEOMETRY_TYPE C00RD_DIMENSI0N MAX_PPR SRID- Feature Table/View ■GID (Geometry Column)- SPATIAL REFERENCE SYSTEMS SRID AUTH_NAME AUTH_SRID SRTEXT GEOMETRY COLUMNS ■GID ESEQ ETYPE SEQ XI Yl X Y or GEOMETRY COLUMNS GID XMIN YMIN XMAX YMAX WKB GEOMETRY Fl MUNI, Drášil 2011 39 Úvod do GIS I 3.4. Webové služby a jejich standardy 3.4.1. OGC - Web Map Service (WMS): Je webová služba poskytující mapu v zadaném výřezu a zadané kartografické projekci. Obsahuje dva základní dotazy: Getcapabilities - vrací metainformace o službě ve formátu XML. Metainformace obsahují zejména výčet mapových vrstev, podporované kartografické projekce a rozsah měřítek, pro které jsou tato data poskytována. WMS KN - CUZK EPSG:102067 EPSG:32633 EPSG:32634 obrazy_parcel Obrazy parcel ... Fl MUNI, Drášil 2011 40 Úvod do GIS I GetMap - vrátí obrázek s požadovanou mapou. Příklad: http://wms.cuzk.cz/wms.asp? request=GetMap& version=l.1.1& layers=dalsi_p_mapy_i,hranice_parcel_i, obrazy_parcel_i,OMP,parcelni_cisla_i& srs=EPSG:102067& bbox=-815350,-1096562,-815058,-1096388& width=1371& height=815& bgcolor=0x9 9 9 9 9 9 & Fo rmat=image/gi f Fl MUNI, Drášil 2011 41 Úvod do GIS I 3.4.2. OGC - Web Map Tile Service (WMTS) Je služba, která poskytuje „dlaždice map" v definované kartografické projekci. Je používána tam, kde se obsah mapy příliš nemění v čase a dlaždice je možné předem připravit. Na podobném principu pracují i robustní světové servery (Google maps, Bing maps). Služba obsahuje opět dva základní dotazy: Getcapabilities - vrací metadata služby ve formátu XML. Metadata obsahují informace o dlaždicových sadách (TileMatrixSet, TileMatrix), jejich měřítkách a umístění v souřadném systému. Příklad: LZRL?reguest=GetCapabilities&version=l. 1. 1& service=WMTS OrtoFoto ORTOMAPA EPSG:102067 Zoom_0 9 Zoom_09 14285.714285714286 -931496 -819102 < Ti1eWidth>2 5 6 256 512 512 Zoom_10 Zoom_10 7142.8571428571431 -931496 -819102 < Ti1eWidth>2 5 6 256 1024 1024 Fl MUNI, Drášil 2011 42 Úvod do GIS I GetTile - vrací mapovou dlaždici. URL&sgrvicg=WMTS&request=GgtTi1g& TilGMatrixSGt=ORTOMAPA&TilGMatrix=Zoom_ll& Tí1gRow=1024&Tí1gCo1=1024 Fl MUNI, Drášil 2011 43 Úvod do GIS I 3.4.3. OGC Web Feature Service (WFS) Je služba, která poskytuje vektorová data v normě GML a atributy libovolné struktury. Getcapabilities - vrací xml soubor popisující služby a seznam poskytovaných datových datové sad (feature). CP:CadastralParcel Cadastral parcel polygons Cadastral parcel polygons urn:ogc:def:crs:EPSG::102067 urn:ogc:def:crs:EPSG::102066 urn:ogc:def:crs:EPSG::2065 text/xml; subtype=gml/3.2.K/Format> 10 43 22 55 DescribeFeatureType - vrací XSD šablonu pro požadovaný feature (= typu datové sady). Fl MUNI, Drášil 2011 44 Úvod do GIS I ListstoredQueries - vrací xml soubor se seznamem uložených dotazů a návratových typů. CP:CadastralBoundary < S to redQuery i d=11 Cadas t r al Par cel_Envel ope_Query " > CP:CadastralParcel CP:CadastralZoning CP:CadastralBoundary Cadastral Parcel Boundaries Fl MUNI, Drášil 2011 45 Úvod do GIS I GetFeature - Vrací sadu prostorových (geometrických) dat. Požadavek je definován parametrem Filter, což je xml fragment definující prostorovou a logickou podmínku na požadovaná data. Je možné definovat velmi složité podmínky. 557658 106440 557489 106330 CP:zoning KU601977 CP: labeK/ValueRef erencG> 215 CP rbeginLifespanVersion 2010-03-08Tl2:46:20 CP:zoning < /No t X / AndX / Filter> Fl MUNI, Drášil 2011 46 Úvod do GIS I Příklad - implementace tříd akceptujících typy objektů směrnice INSPIRE (EU): Typ "Typ 1" obsahuje atribut, vlastnost typu "Typ 2". Typ "Typ 2" je potomkem typu "Typ 1" (dědí jeho vlastnosti] "Inspire Cadastral Parcels" generovaný C# kód: Musí se serializovat NameSpace CP PiSpatialDataSetType CP:CadastralParcel "Inspire Cadastral Parcels" validni C# kod: Kopie z gml, akceptuje objekty z CP CP:S SpatialDataSetType J CP:lnspireFeaturePropertyType CP:CadastralParcel I í gmhAbstractFeatureType gml: Abst ra cG M LTy pe Fl MUNI, Drášil 2011 47 Úvod do GIS I 4. Efektivní přístup k prostorovým datům 4.1. Vymezení problému Problém vyhledání: - Pole v (seznam) objektů stejného typu tl7 ve které vyhledáváme. - Množina q (potenciálně nekonečná) typu t2, definující možné dotazy. - Množina R (typu t3) definující možné odpovědi. - Funkce check (r,q) : R x Q - {true,falše), která určuje, zda reR vyhovuje dotazu qeQ. Problém vyhledání je funkce libovolná search (q,v), která pro dotaz q nad množinou Q vrací všechny možné vyhovující odpovědi: search (q,V)= {reR \ check (r,q) =true} Příklad - Problém příslušnosti prvku k množině: - Položme r2 = t2 (typ vyhledávací množiny je totožný s typem dotazu) - v c r a | v\ xmirKxmax a ymin <^> [x,y]eV a xminšxšxmax a yminšyšymax Funkce search (q, v) řeší problém rozsahového dotazu na body ve 2D prostom. Fl MUNI, Drášil 2011 50 Úvod do GIS I Príklad Rozsahový dotaz na obdélníky ve 2D prostom: - v d e2 x e2 a | v\ < oo, taková, že [xmin, ym±n, xmax, ymax] eV =^> => xmin => xminCKxmaxQ a yminCKymaxQ Dotazem je libovolný obdélník ve 2D prostom jehož strany jsou rovnoběžné s osami souřadného systému. r = e2 X e2 - check ( [xmin, ymin, xmax, ymax] , [xminQ, yminQ, xmaxQ, ymaxQ] ) =true <=> [xmin r ymin r xmax r ymax] eV a xminúxmaxQ a ymin xmin < xmaxQ a xmax > xminQ Lineární indexovací metoda (tj. uspořádání podle jednoho či více klíčů), nám nepomůže, neboť nejhorší případ dotazu vede prohledání celého souboru. Fl MUNI, Drášil 2011 53 Úvod do GIS I Problémy vyhledávání rozdělíme na dvě hlavní třídy: - problém statický - problém dynamický Staticky: - build(v) vybuduje podpůrné struktury pro množinu v - search (q, v) odpoví na vyhledávací dotaz Dynamicky: - insert (x, v) vloží do množiny v nový objekt x - delete (x,v) vymaže z množiny v objekt x - search (q, v) odpoví na vyhledávací dotaz Dynamické řešení problému zároveň řeší statickou variantu (opakujeme funkci insert). Funkce search bývá většinou rozdělena na dvě části, a to - init(q,v) inicializace dotazu - fetch (x) vrací jeden objekt z množiny v práce potom probíhá podle jednoduchého schématu: init(q,V); while(fetch(x)==SUCCESS) { zpracuj_objekt(x); } Fl MUNI, Drášil 2011 54 Úvod do GIS I Poznámka: Všechny uvedené příklady lze triviálně řešit jedním průchodem množiny v, tedy v lineární časové složitosti o (\ v\). Uvádění jiných metod má tedy smysl pouze v případě, že tento základní odhad nějak zlepšíme. Pro rozsahové výběry se většinou studuje časová složitost „zásahu" prvního objektu, který splňuje podmínku rozsahového výběru. Fl MUNI, Drášil 2011 55 Úvod do GIS I 4.2. Metoda „GRID": Spočívá v pravidelném rozdělení 2d prostom, resp. zájmového území obdélníkovou sítí. Elementy sítě lze maticově indexovat, tím prostor „linearizovat" a využít je tím pro primární prostorový filtr. ■4 . i .5 .4 3 __ ._____ .6 2 ]\ .i .3 1 ] 1 2 3 ■4 5 7 -< ~. 1 •= _^ / — r / l ......—/ 1 1 2 3 ^ Č. C "y Prostorový dotaz v GRIDu": Prohledáváme pouze čtverce incidentní s dotazem, tedy (4,2) a (5,2), pro efektivní přístup ke čtvercům použijeme libovolnou vyhledávací metodu podporující rozsahový dotaz na úplně uspořádaných množinách. Tyto metody jsou standardně implementovány ve všech databázových strojích a lze je téměř okamžitě použít. Fl MUNI, Drášil 2011 56 Úvod do GIS I Realizace GRID metody v prostředí SQL: Každé prostorové tabulce (tj. obsahující vektorovou geometrii např. ve formátu WKB) přiřadíme indexovací prostorovou tabulku. gtablejdx "gÍĎ number grid x number grid y number spatialqueryidx TĎ number grid x number grid y number gid = gid id id gtable gid number xmin number ymin number xmax number ymax number wkb geometry blob spatial_query id number xmin number ymin number xmax number ymax number Tabulka s prostorovými daty: create table GTABLE ( GID number, XMIN number, YMIN number, XMAX number, YMAX number, WKB_GEOMETRY blob, constraint GTABLE_PK primary KEY (GID) ) ; Tabulka grid indexů: create table GTABLE_IDX ( GID number, GRID_X number, GRID_Y number ) ; Fl MUNI, Drášil 2011 57 Úvod do GIS I Omezení a prostorové indexy: alter table gtable_idx add constraint gtable_idx_pk primary key (gid,grid_x,grid_y); alter table gtable_idx add constraint gtable_idx_fkl foreign key (gid) references gtable(gid) on delete cascade; create index gtable_idx_i1 on gtable_idx(grid_x, grid_y); Triggerem zajistíme vkládání prostorových indexů: create trigger gtable_spatial before insert or update of x,y on gtable for each row begin xf rom: =get_grid_x (: new. xmin) ; xto : =ge t_grid_x ( : new. xmax) ; yf rom: =get_grid_y (: new. ymin) ; y to : =ge t_grid_y ( : new. ymax) ; pro xfrom<=i<=xto a yfrom<=j <=yto begin insert into gtable_idx values(:new.gid,i,j); end; end; / (funkce get_grid_x/y vrací gridové indexy) Fl MUNI, Drášil 2011 58 Úvod do GIS I Implementace prostorového dotazu: Vytvoříme dotazovou tabulku: create table spatial_query ( id int, xmin int, ymin int, xmax int, ymax int, constraint spatial_query_pk primary key (id) ) ; A ostatní objekty (indexová tabulka, integritní omezení, trigger) stejně jako u tabulek s prostorovými daty. Prostorový dotaz pro Obdélník [xmin,ymin,xmax,ymax] provedeme následovně: 1. Identifikace dotazu: Z databáze získáme nový (jednoznačný) klíč dotazu id, například ze sekvence. 2. Inicializace dotazu: insert into spatial_query values (id,xmin,ymin,xmax,ymax) , vlivem triggeru spatial_query_spatial automaticky vloží identifikace gridových čtverců to tabulky spatial query idx Fl MUNI, Drášil 2011 59 Úvod do GIS I 3. Prostorový dotaz: select ... from gtable A, gtable_idx B, spatial_query_idx C where A. GID=B.GID AND B. grid_x=C.grid_x AND B. grid_y=C.grid_y AND C. query_id=id; Ukončení prostorového dotazu: delete from spatial_query where id=id; Jaký mechanismus odstraňuje řádky z tabulky spatial_query_idx?) Výhody vs. nevýhody GRID metody. + - velmi snadná implementace v prostředí RDBMS - snadné rozšíření na více dimenzí (?) - relativně snadná (resp. řešitelná implementace neobdélníkových dotazů) - netriviální odhad velikosti GRIDových čtverců, špatná volba má dramatické důsledky - nepravidelné chování při řádově rozdílné velikosti geometrických objektů Fl MUNI, Drášil 2011 60 Úvod do GIS I 4.3. Modifikace binárních stromů pro prostorové vyhledávání, k-d stromy Definice - Binární strom: - Nechť (u,<,) je úplně uspořádaná množina, v c u a I v\ nod.Key, pokračujeme krokem 1 pro nod.Right Algoritmus - Vkládání klíče do binárního stromu: 1. Vstup: klíč key 2. Procházíme strom, jako bychom hledali klíč k, dokud nenarazíme na volnou pozici, tedy končíme bodem 2 předešlého algoritmu. 3. Do volné pozice vložíme klíč key. Algoritmus - Rozsahové vyhledání v binárním stromu: 1. Vstup: interval [min,max], kořen stromu nod. 2. Je-li nod=nuii (strom je prázdný), potom konec. 3. Patří-li nod. Key do intervalu [min,max], pošleme jej na výstup a aplikujeme algoritmus na nod. Left a nod.Right. 4. Je-li maxnod.Key aplikujeme algoritmus na nod.Right. Fl MUNI, Drášil 2011 62 Úvod do GIS I Zlepšení časové složitosti spočívá v tom, že v určitých fázích algoritmů jsme schopni rozhodnout, kterou větev stromu můžeme bez rizika vynechat. Potíže způsobuje skutečnost, že v jistých případech může být strom degenerovaný (např. nod. Left=null pro všechny uzly). Degenerace nastává tehdy, když jednotlivé prvky vstupují do stromu v nevhodném pořadí Qsou uspořádány). V případě statické verze vyhledávacích problémů lze vybudovat tzv. optimální binární strom (na vstupu procedury bulld známe celou množinu v). Definice - Optimální strom: Strom nazveme optimální, liší-li se počty uzlů v podstromech \nod.Left\ a \nod.Right\ maximálně o 1 pro jeho každý uzel nod.. Poznámka: Hloubka optimálního stromu obsahujícího | v\ klíčů je: log( | v\) Algoritmus - Vybudování optimálního binárního stromu: 1. Vstup: množina klíčů v, kořen stromu nod. 2. Je-li v = nuli, skonči. 3. Rozděl množinu vna po dvou disjunktní množiny v1;{med(v) ;,v2tak, žemed(v) je medián množiny v, klíče z v2 jsou menší než med(v) a klíče z v2 jsou větší než med (V). 4. Definuj kořen stromu jako med(v). 5. Aplikuj algoritmus na množinu v2 pro levý podstrom nod. Left. 6. Aplikuj algoritmus na množinu v2 pro pravý podstrom nod.Rlght. Fl MUNI, Drášil 2011 63 Úvod do GIS I Definice - Vyvážené stromy: Binární strom nazveme vyvážený, liší-li se hloubky nod.Left a nod.Ríght maximálně o 1 pro jeho každý uzel nod (hloubkou stromu rozumíme maximální délku cesty od kořene k listu). Poznámka - Rotace ve vyvážených stromech: Podmínku vyvážení lze udržovat dynamicky pomocí tzv. rotací (AVL stromy). Každý uzel si může zapamatovat hloubku levého a pravého podstromu. Při vložení nového klíče se strom v těch uzlech, ve kterých došlo k porušení podmínky vyvážení přeorganizuje, např: Počet uzlů v podstromu s kořenem nod označíme \nod\. Definice - bb[oc] stromy: Buď 0 < a< 1/2. Binární strom patří do třídy bb[oc] stromů, platí-li pro jeho každý uzel nod a < | nod.Left \ / (\nod\ ) < 1-a Fl MUNI, Drášil 2011 64 Uvod do GIS I Poznámka - smysl bb[cc] : Pokud byl v nějakém okamžiku podstrom definovaný uzlem nod optimální, pak k porušení podmínky z definice bb[oc] stromů musí dojít k minimálně c*\nod\ vložení/mazání uzlů do/z příslušného podstromu (cje konstanta závislá pouze na parametru a). Definice k-D strom: Úrovní íevei(nod) uzlu nod binárního stromu rozumíme délku cesty k tomuto uzlu od kořene stromu. Buď (s, <) uspořádaná množina, k>o, x=(x0f . . rxír . . /xk-1) fy=(Yof • • fYíf • • rYk-i) Říkáme, že x < i y, jestliže x± < y± k-D stromem nad S nazveme binární strom, jehož uzly jsou k-tice z^a kde pro každý uzel nod, jeho levý podstrom nod. Left a všechny uzly tohoto podstromu nodL platí: nodl ^ i nod kde i = level (nod) mod k Analogická podmínka musí být splněna i pro pravý podstrom nod.Rlght. Algoritmus - Vyhledání bodu ve 2-d stromu: Analogicky k binárním stromům, s tím rozdílem že na každé úrovni použijeme jinou srovnávací metodu (<, ±). Fl MUNI, Drášil 2011 65 Úvod do GIS I Algoritmus - Vložení bodu do 2-d stromu: Analogicky k binárním stromům, hledáme ve stromu „bod" dokud nenarazíme na volnou pozici. Do ní vložíme nový klíč." Geometrická interpretace 2-d stromu, každý vložený bod dělí, jistou část roviny na dvě „poloroviny". — 3 Algoritmus - Rozsahový dotaz pro body ve 2-d stromu: 1. Vstup: Kořen nod a obdélník q=[ xmin,ymin,xmax,ymax]. 2. Je-li nod=nuii,konec. 3. Je-li nod.Key (tj. bod ve 2D prostoru) dotazovém obdélníku, pošli jej na výstup a aplikuj algoritmus na oba dva syny. 4. Vyber syny, pro které budeš aplikovat algoritmus a to podle úrovně ve které se nachází uzel nod, například je-li: level(nod) mod 2=0 A nod.Key.x > xmax potom aplikuj algoritmus jen na větev nod.Left, analogicky pro další možné případy. Fl MUNI, Drášil 2011 66 Úvod do GIS I Vyvažování multidimensionálních stromů je komplikované. Nedají se totiž provádět rotace jako v klasických binárních stromech, protože v každém patře stromu měníme srovnávací kritérium, např. (obrázek rotace) z B. Key. x>A. Key. x a D . Key. yA.key.y Pomocí bb[a] techniky lze však k-D stromy udržovat vyvážené pomocí částečné reorganizace, tedy „hlídat" v každém uzlu k-D stromu poměr počtu uzlů v jeho levém a pravém podstromu a v případě porušení podmínky bb[a] nahradit vybudovat optimální strom. Algoritmus -Vybudování optimálního 2-d stromu: 1. Vstup: množina bodů v, kořen stromu nod, úroveň uzlu le{ 'y') 2. Je-li v = nuii, skonči. 3. Rozděl množinu v na po dvou disjunktní množiny vx, {medj, (v) },v2 tak, že medj, (v) je takový bod, že jeho i-ová souřadnice je medián množiny i-ových souřadnic z v, i-ové souřadnice z vx jsou menší než medi(v) a i-ové z v2 jsou Větší než med2 (V) . 4. Definuj kořen stromu jako med2 (v). 5. Je-li i rovno x'potom přiřaď i='y' jinak i='x' 6. Aplikuj algoritmus na množinu vx pro levý podstrom nod.Left. 7. Aplikuj algoritmus na množinu v2 pro pravý podstrom nod.Rlght. Fl MUNI, Drášil 2011 67 Úvod do GIS I Poznámka: Rozdělení množiny z kroku 3. lze realizovat modifikaci metody QuickSort. Metodu k-D stromů lze použít i na obdélníky, které můžeme považovat Za 4D body [xmin,ymin,xmax,ymax]. Použijeme tedy 4-D strom. Algoritmus - Rozsahový výběr pro obdélníky ve 4-d stromu: 1. Vstup: kořen stromu nod, dotazový obdélník q= [xmin, ymin, xmax ,ymax]. 2. Je-li nod = nuii, skonči. 3-Jsou-li obdélníky q a nod.Key incidentní, pošli nod na výstup a aplikuj algoritmus na nod.Left a nod.Right. 4.Podle úrovně, ve které se nacházíš ve stromu, se rozhodni, zda můžeš vynechat nějakou větev, např. Je-li: level(nod) mod 4=0 a nod.Key.xmin > q.xmax aplikuj algoritmus pouze pro nod.Left. Analogicky pro další úrovně, v každé se dá za jistých podmínek jedna větev vynechat. Fl MUNI, Drášil 2011 68 Úvod do GIS I 4.4. Quad Tree - Kvadrantové stromy Kvadrantové stromy jsou prostorové vyhledávací struktury založené na pravidelném dělení části 2D prostoru (většinou čtverce) na čtyři stejné části. V základní verzi mohou přímo definovat polygonální geometrii. Fl MUNI, Drášil 2011 69 Úvod do GIS I Definice - kvadrantový strom: Kvadrantový strom hloubky h je kvartérní strom (tj. každý uzel má maximálně 4 následníky) s těmito vlastnostmi: - Uzel je tVOřen Obdélníkem R=[xmin,ymin,xmax,ymax]a příznakem contente {empty, f ull, half}. - List má příznak contente {empty, f ull}. - Nelistový uzel má čtyři následníky a příznak content=half. - Následníci uzlu dělí obdélník rodičovského uzlu na čtyři „stejné" části (podle středu). - Maximální délka od kořene k listu je n. Podle toho, jakou část rodičovského obdélníku reprezentuje uzel, označíme jej tl, tr, bl, br (top/bottom left/right). Poznámka: Struktura je velmi dobře použitelná v těch případech, kdy je prostor pevně rozdělen na „dlaždice", například pro služby typu WMTS (viz datové sklady GIS). Každá úroveň podrobnosti n je reprezentována maticí dlaždic 2nx2n.Struktura potom odpovídá na dotaz, zdaje dlaždice obsazená Qe na ní mapa/jev). Strukturu lze implementovat jednoduchým objektem: public class QtreeNode { public QtreeNode TopLeft; public QtreeNode TopRight; public QtreeNode BottomLeft; public QtreeNode BottomRight; public QtreeContent Content; } Fl MUNI, Drášil 2011 70 Úvod do GIS I Struktura neobsahuje souřadnice čtverce/obdélníku, který reprezentuje, stačí si pamatovat nultý čtverec/obdélník kořene stromu. Souřadnice ostatních uzlů jsou potom definovány cestou od kořene. Algoritmus - vyhledání dlaždice v QuadTree: 1. Vstup sloupec coi, řádek row, podrobnost zoom a kořen node. 2. i=zoom 3. Je-li node . Content^half vrať node . Content a konec. 4. Je-li i==o vrať node.content a konec. 5. Nechť coii je i-tá binární cifra čísla coi zprava, rowi je i-tá binární cifra čísla row zprava. 6. Je-li coii=o pokračuj nahoru, je-li coii=i pokračuj dolů, Je-li row, =U pokračuj doleva, je -II row,=I pokračuj doprava. Přiřaď uzlu node= node .„pokračování", i=i-i a pokračuj 3. Na struktuře lze velmi snadno a elegantně provádět množinové operace. Stačí implementovat operaci inverze a např. průniku, ostatní množinové operace lze provést pomocí těchto dvou. Fl MUNI, Drášil 2011 71 Úvod do GIS I Algoritmus - inverze QuaoTree 1. Vstup kořen node. 2. Je-li node . Content==f ull potom node. Content=empty a návrat. 3. Je-li node . Content==empty potom node . Content=f ull a návrat. 4. Je-li node. content==haif potom proveď kroky 2. a 3. pro všechny následníky. Algoritmus - průnik QuadTree: 1. Vstup kořeno dvOU Stromů nodel a node2 . 2. Je-li nodel. Content==empty nebo node2 . Content==empty vrať UZel node S Obsahem node.Content= empty. 3. Je-li nodel. Content==f ull a node2 . Content==f ull vrať UZel node S OPSahem node. Content=f ull. 4. Je-li nodel. Content==half a node2 . Content==f ull vrať nodel. 5. Je-li node2 . Content==half a nodel. Content==f ull vrať node2. 6. Jinak vytvoř nový uzel node a následníkům přiřaď uzly opakováním kroků 2. - 6. pro odpovídající dvojice následníků UZlŮ nodel a node2. Vrať nový UZel node. Fl MUNI, Drášil 2011 72 Úvod do GIS I Pevný kvartérní strom (non-pointer Quad Tree) Zájmové území je postupně děleno na obdélníkové části a podle nich je jim přidělován „klíč" 1000 2000 3000 4100 4200 4300 4400 Obr. - Číslování obdélníků-dlaždic v non-pointer Quad Tree. Obdélník bude mít index takové dlaždice „pevné struktury" která je jeho nadmnožinou a je nejmenší s touto vlastností. - Pro libovolný obdélník r označme q (r) jeho klíč v non-pointer QuadTree. - Pro libovolný klíč k označme jeho „nenulovou" část, tedy levý podřetězec symbolem nz (k) . - Délku znakového řetězce k označme len (k) . - Podřetězec řetězce k z levé strany délky i označme substr (K, 1) . Fl MUNI, Drášil 2011 73 Úvod do GIS I Tvrzení - incidence obdélníků n non-pointer QuaoTree: Buďte a, b libovolné obdélníky, jejichž strany jsou rovnoběžné s osami souřadného systému. Nechť dále a n b * 0. Označíme-li, l=min{len(NZ (Q (a) )) ,len(NZ(Q(b))) } potom: substr(Q(a),1)=substr(Q(b),1) Algoritmus - Vyhledání obdélníků v non-pointer QuadTree: 1. Vstup — Obdélník S= [xmin,ymin,xmax,ymax] . 2. Pošli na výstup všechny obdélníky a, pro které: substr(Q(a),len(NZ(Q(S))))= NZ(Q(S)) a Ans^0 3. Pošli na výstup všechny obdélníky a, pro které: q(a)=p a Ans^0 kde p jsou všechny klíče, které jsou na cestě od q(s) ke kořenu, tj. v q(s) zprava postupně nahrazujeme nenulové číslice nulami. Tento postup má jednu nevýhodu, v případě, že dotaz inciduje se středem území, potom procházíme v bodě 2 všechno. Této nevýhodě se vyhneme dekomponování dotazu. Fl MUNI, Drášil 2011 74 Úvod do GIS I Algoritmus - Dekompozice dotazu v non-pointer QuaoTree: 1. Vstup - dotazový obdélník s. 2. Rozděl obdélník s na obdélníky s1 a s2 (Si u s2 = s) podle takové souřadnice x resp. y, která způsobila klíčování v non-pointer quadTree, tj. takovou, která ohraničuje nějaký čtverec v non-pointer quadTree a prochází dotazovým obdélníkem s. V případě, že taková souřadnice neexistuje potom obdélník s neděl a konec. 3. Aplikuj krok 2. na čtverce s2 a s2 podle druhé souřadnice. Tímto postupem získáme maximálně 4 obdélníky na které aplikujeme algoritmus vyhledání obdélníků Výhody této metody: - Velmi snadná implementace v prostředí SQL - tedy relačních databází, například norma WKB nepředepisuje metodu efektivního výběru, tímto způsobem ji můžeme doplnit. - „jeden objekť"=„jeden klíč", znamená, že prostorová indexace je zabezpečena přímo v geometrické tabulce. Prostorový výběr nevyžaduje součin, či spojení s dalšími tabulkami. Fl MUNI, Drášil 2011 75 Úvod do GIS I Dekompozice dotazu - 4 obdélníky sklíči: 2330000000,2343000000,4110000000,4120000000 SELECT ID FROM KM_ALL WHERE ( (SPAT_KEY BETWEEN '2330000000' AND '2335000000') OR (SPAT_KEY BETWEEN '2343000000' AND '2343500000') OR (SPAT_KEY BETWEEN '4110000000' AND '4115000000') OR (SPAT_KEY BETWEEN '4120000000' AND '4125000000') ) OR SPAT_KEY IN ('0000000000', '2000000000', '2300000000', '2340000000', '4000000000', '4100000000' ) AND (xmax>=-642646042) AND (ymax>=-1114990337) AND (xmin<=-569087654) AND (ymin<=-1070777051) Fl MUNI, Drášil 2011 76 Úvod do GIS I 4.5. SB+stromy Definice - B+-stromv: B-strom řádu m je strom s těmito vlastnostmi: - každý uzel má maximálně m synů - každý uzel, s výjimkou kořene a listů, má minimálně m/2 synů - kořen má minimálně 2 syny, pokud není list - všechny listy jsou na stejné úrovni - nelistový uzel s k syny obsahuje k-i klíčů - pro klíče v uzlu keyi,.. ,keyk jsou vzestupně uspořádány - ukazatel p± ukazuje na uzel, jehož všechny klíče jsou v intervalu [keyi,keyi+1] (formálně předpokládáme, že key0=-oo a keyk+i=oo). Uzly B+ stromu mají tedy tvar p0keyipi...pk_ikeykpk. Algoritmus vložení klíče do B+ stromu: 1. Vstup klíč key a kořen B+ stromu. 2. Není-li uzel list vyber dvojici klíčů keyi,keyi+i s vlastností keyi_im, rozděl uzel. Fl MUNI, Drášil 2011 77 Úvod do GIS I Algoritmus dělení uzlů v B+ stromu řádu m : 1. Vstup uzel s m+i klíči. 2. Nechť k=m/2+i, vytvoř dva nové uzly: PokeyiPi...pk-2keyk-ipk-i a pkkeyk+ipk+i...pmkeym+ipm+i a ukazatele na ně q resp. r 3. Je-li uzel kořen, vytvoř nový prázdný kořen: q keyk r jinak nechť pL je ukazatel z otcovského uzlu. Vlož klíč keyk do otcovského uzlu na pozici: . . keyi pí keyi+i. . -> keyi q keyk r keyk+i 4. Má-li otcovský uzel m+i klíčů, opakuj pro něj kroky 1.-3. Na základě struktury B+ byl definován SB+strom: SB+ strom je B+strom z počátečních a koncových bodů intervalů a navíc: - V SB+ stromech jsou k listům přidány seznamy identifikátorů intervalů, které jsou incidentní s klíčem v listu (tj. nějakým počátkem resp. koncem nějakého intervalu). - S každým identifikátorem je pamatován příznak, který označuje zda v se jedná o počáteční hodnotu intervalu, koncovou hodnotu intervalu, popřípadě zda interval touto hodnotou prochází. Fl MUNI, Drášil 2011 78 Úvod do GIS I 8 6 4 2 Rl R2 S2 SI S3 8 10 12 14 16 Rlb Rl c R2b Rl c Rl e R2c R2e SI b SI c S2b S2c SI e S2c 10 S2e S3b 12 16 1 12 14 R3b S3c R3c S3e 16 T R3e Fl MUNI, Drášil 2011 79 Úvod do GIS I Algoritmus - Incidence intervalů v SB+ stromech: 1. Vstup dotazový interval [xmin,xmax]. Existující SB+ strom s. 2. Najdi ve stromu takový list, že pro bod ip který reprezentuje tento list platí: ip=min{i; i 6 S, i>xmin} 3. Pro všechna i s vlastností: ip < i< xmax 4. Pošli na výstup identifikace intervalů ze seznamu listu reprezentovaným bodem i (identifikace se mohou opakovat, posíláme jen jednou). Fl MUNI, Drášil 2011 80 Úvod do GIS I Algoritmus - Vkládání intervalů do SB+stromu: 1. Vstupní interval [xmin,xmax], jeho identifikace i. 2. Najdi ve stromu takový list, že pro bod ip který reprezentuje tento list platí ip=xmin. 3. Jestliže v kroku 2. jsme takový list nenašli, potom: 3.1. Vlož do stromu bod xmin standardní metodou pro B+ stromy 3.2. Nechť pip je bezprostřední předchůdce xmin, nip bezprostřední následník xmin v sb+ stromu. 3.3. Polož: xmin. seznam = pip. seznam n nip. seznam bez ohledu na příznak typu incidence. 3.4. Polož příznak typu incidence ='c' pro všechny intervaly z xmin. seznam. 4. Kroky 2.-3. pro xmax. 5. Pro všechny listy SB+ stromu takové, že pro jejich body ip platí xmin < ip < xmax: 5.1. Je-li ip=xmin potom přidej do ip. seznam identifikaci i a příznak typu incidence 'b'. 5.2. Je-li ip=xmax potom přidej do ip. seznam identifikaci i a příznak typu incidence 'e'. 5.3. Je-li xmin 0 hodnota 255 Obr. 18 - Histogram obrazu Fl MUNI, Drášil 2011 100 Úvod do GIS I Definice - Matice sousednosti: Nechť f je polotónový obraz barev 1..M. Jeho maticí sousednosti rozumíme čtvercovou MxM matici CM(f)={cnrijj}, kde, c/77,yje počet (přímo) sousedících pixelů o barvě i a j.u 6.2. Operace nad obrazy Lineární filtrace: Buď f polotónový obraz, M > 0. Položme g(x,y)= H(M,x,y) kde h je libovolná funkce, která v konstantním čase počítá novou hodnotu pixelu g(x,y) z okolí pixelu (x,y) o rozměru m. Funkce h bývá někdy vyjádřena váženým průměrem pixelů a lze ji vyjádřit: H(M,x,y)=Zi=_M,M Sj=-M,M h (i, j) *f (x+i,y+j) Fl MUNI, Drášil 2011 101 Úvod do GIS I Zhlazuiící filtrv: Fl MUNI, Drášil 2011 102 Úvod do GIS I Zostřující filtry: Fl MUNI, Drášil 2011 103 Úvod do GIS I Detektory hran: Základním filtr této třídy přiřadí novému pixelu největší absolutní hodnotu ze dvou výsledků: 1 2 1 1 0 -1 0 0 0 2 0 -2 -1 -2 -1 1 0 -1 Fl MUNI, Drášil 2011 104 Úvod do GIS I Původní obraz Zostřující filtr: Detektor hran: Fl MUNI, Drášil 2011 105 Úvod do GIS I Kontura (hranice) oblasti v binárním obrazu: Nechť Oje libovolná oblast (množina složená z jedniček) v binárním obrazu, Konturou (hranicí) oblasti O rozumíme všechny pixely patřící této oblasti, které mají nulového d-souseda. O O O O ^ vektorově * rastrově Fl MUNI, Drášil 2011 106 Uvod do GIS I 6.3. Transformace rastrových dat Velmi častá úloha, zejména pro umisťování obrazu do dané kartografické projekce. 1. Určíme bodové objekty ve zdrojovém obrazu, jejichž (kartografické) souřadnice jsou známé. Například přesně odečtené z mapy, geodeticky zaměřené apod. 2. Určíme transformační funkce z nového do starého obrazu komerční produkty většinou poskytují polynomiální transformaci založené na metodě nejmenších čtverců, je však možné použít i přesnou kartografickou transformaci. kde (i, j) značí souřadný systém originálního obrazu, (x,y) souřadný systém obrazu nového. 3. V této fázi procházíme cílový obraz, pomocí transformačních funkcí f a g se „díváme" do originálu a počítáme hodnotu pixelu. Podle toho, z jakého okolí zdrojového pixelu určujeme výslednou hodnotu pixelu nového, se hovoří o metodách: -nejbližší soused -bilineární transformace -konvoluce okolí mxm i = f (x,y) j = G(x,y) Fl MUNI, Drášil 2011 107 Úvod do GIS I První případ prostě přenese hodnotu pixelu do nového obrazu, v dalších případech se výsledná hodnota se počítá z jistého okolí pixelu v originálním obrazu. Velmi často se setkáváme s následující situací (například v klientech WMS služby). - Známe omezující obdélník cílové kartografické projekce a rozměr obrazu v pixelech - Známe sadu projekcí, které poskytuje (WMS) server - Potřebujeme dostat mapovou kompozici do "okna" na klientskou stanici. V tomto případě postupujeme takto: 1. Vybereme vhodnou serverovou projekci (např. wgs84, tu poskytuje každý WMS server). 2. Transformujeme dotazový obdélník do serverové projekce, upravíme pixelový rozměr obrazu. K tomuto účelu použijeme "přesný" převod souřadnic (rovina_i—► eiipsoid_i-> centr_l—> centr_2 —> elipsoid_2—> rovina_2, VÍZ. transformace souřadných systémů). 3. Provedeme dotaz, získáme obraz v souřadnicích (i,j). 4. Vybereme sadu zdrojových pixelových souřadnic (většinou pravidelná mřížka nxn, nebo rohy obrazu). Tyto převedeme do zdrojových souřadnic, poté "přesnou" kartografickou transformací do souřadnic cílové projekce a cílových souřadnic pixelových (x,y). Takto získáme sadu dvojic "odpovídajících si" pixelů, kterou použijeme pro získání parametrů polynomiální transformace obrazu. Fl MUNI, Drášil 2011 108 Úvod do GIS I Tento postup "šetří" výpočtovou náročnost tím, že nahradí náročné přepočty kartografických souřadnic polynomiální transformací. Skelet binárního obrazu: Definice - Skelet: Nechť r je množina pixelů, b její hranice (kontura), p bod v r. N ej b Užší soused bodu p na hranici b je bod m z b takový, že pro každý bod m' z b je vzdálenost pm' větší nebo rovna vzdálenosti pm. Má-li bod p více než jednoho nejbližšího souseda, nazývá se bodem skeletu množiny r. Sjednocení všech bodů skeletu tvoří skelet množiny r. Fl MUNI, Drášil 2011 109 Úvod do GIS I Algoritmus - Určení skeletu: "I.Urči hranici (konturu) B(R) množiny R. 2. Urči množinu násobných pixelů M(R) v hranici B(R) 3. Je-li B(R) = M(R), skonči. 4. Polož R = R - (B(R) - M(R)) a pokračuj krokem 1. (a) (b) (c) A A A A A A A A C 0 P 0 A P 0 0 P 2+ B B B A 0 2 B B C Pixel označený 2 je hraniční pixel, pixel označený 2+ je hraniční nebo násobný pixel. (a), (b): Alespoň jeden pixel ze skupiny pixelů A, B je nenulový (c): Alespoň jeden pixel ze skupiny C musí být nenulový. Pokud jsou oba nenulové, pak může být hodnota pixelů ve skupinách A i B libovolná. Pokud je jeden pixel skupiny C nulový, musí být alespoň jeden pixel skupiny A i skupiny B nenulový. Fl MUNI, Drášil 2011 110 Úvod do GIS I 7. Topologické úlohy v GIS Byly efektivně řešeny před tím, než byly vůbec GIS technologie vymezeny, přesto je můžeme považovat za součást analytického jádra topologicky orientovaných GIS. Základní datová struktura síťového grafu: Hrana Vedeni Připoj ka zacina Uzel Odběrné mi s to konči Základní datová struktura areálového grafu: Hrana Hr. obce Hr. katas 1.areál Areál Obec 2.areál Nejčastější úlohy: Trasování grafu: Vyber všechny uzly/hrany, které jsou "napájeny" z daného uzlu, hodně používaná úloha pro dispečery sítí, modelování situací „co se stane, když?". Fl MUNI, Drášil 2011 111 Úvod do GIS I Neikratší cesta z uzlu do uzlu: Používá se klasický Dijkstrův algoritmus. Lze výhodně využít vlastnosti, že uzly grafu jsou prostorově lokalizovány. Algoritmus „Minimální cesta (Best search): Nechť (u,H) je graf s nezáporně ohodnocenými hranami, váhu libovolné hrany heH označme w(h). Nechť dále každý uzel u±eu má 2D souřadnice (x± ,y±). Pro libovolné uzly u,v označme d(u,v) jejich vzdálenost v e2. Pro libovolnou hranu hi=(Ui,Vi) nechť dále je d(Ui,v±)^w(h) - platí trojúhelníková nerovnost metrického prostoru e2. Potom pro libovolné uzly u0,veu, následující postup vede k nalezení minimální cesty z u0 do v. 1. Inicializace: Pro každý uzel u±eu, položme d_pathi=oo, d_patho=0, a položme každý uzel u±eu c_pa th±=NULL. 2. Výběr pivota: Položme c_pathi=d_pathi pro takový u±J pro který je c_pathi=NULL, d_path±