Pojmy související s GIS Matematická kartografie - disciplína zabývající se převodem zemského povrchu do roviny. Ekvidistantní zobrazení - nezkresluje délky určité soustavy. Zpravidla touto soustavou bývají zeměpisné poledníky nebo rovnoběžky. Nelze definovat ekvidistantní zobrazení, které by nezkreslovalo žádné délky. Ekvivalentní zobrazení - nezkresluje plochy, zkreslení úhlů je však zde poměrně značné, což se projevuje zejména ve tvarech ploch. Konformní zobrazení - ponechává nezkreslené úhly, značně jsou však zde zkreslovány plochy. Zemsky povrch - geometricky složitý útvar geoid, proto je modelován rotačním elipsoidem, který je určen hlavní a vedlejší poloosou. Pro různá kartografická zobrazení je jsou používány různé elipsoidy, v poslední době je snaha používat elipsoid WGS84. Bessel Hayford Krasovskij IAG 1967 WGS-84 rok 1841 1909 1940 1967 1984 a [m] 6377397.155 6378388 6378245 6378160 6378137 b[m] 6356078.963 6356911.946 6356863.019 6356774.516 6356752.314 1 Geodetické datum: model zemského tělesa (koule, elipsoid..), jeho umístění (orientace) vůči zemskému tělesu a datum určení. Geografické souřadnice - určení polohy bodu na ploše elipsoidu pomocí zeměpisné šířky cp a zeměpisné délky Á. Šířka cp je definována jako úhel mezi normálou k ploše elipsoidu a rovinou rovníku (-90Q, 90Q) k severnímu a jižnímu pólu. Délka Á je úhel mezi rovinou základního poledníku (meridiánu) a poledníku daného bodu (0B,360*) nebo {-180g,180 g). Geocentrické souřadnice X, Y,Z - prostorový souřadný systém s počátkem ve středu elipsoidu, osa Xje vložena do průsečíku rovníku a roviny základního (nultého) poledníku, osa Z spojuje střed elipsoidu a severní pól a osa Y leží v rovině rovníku otočena o 90-proti směru hodinových ručiček od osy X. Rovinné souřadnice - určení polohy v rovině pomocí dvojice rovinných souřadnicX,Y'v ortogonálním souřadném systému. V některých zobrazeních (zobrazení UTM) se používá symbolika E,N (Easting, Northing) tj. rovinné souřadnice narůstající k východu resp. k severu. Základní typy převodu geografických do rovinných souřadnic: Si V .P' IX i i D Válcové zobrazení 2 Kuželové zobrazení Azimutální zobrazení 3 Souřadný systém -je soubor těchto údajů : - Geodetické datum (elipsoid, referenční bod, datum určení) - Souřadný systém geografických souřadnic q>, Ä, (včetně volba základního poledníku) - Zobrazovací rovnice do rovinných souřadnic - Souřadný systém rovinných souřadnic X,Y Příklad '. (http://gis.zcu.cz/kartografie/konference2001/sbornik/veverka/veverka-referat.htm) 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 ferrskeho 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, vložení osy Xvždy do obrazu středového poledníku příslušného pásu, s úpravou souřadnice V přičtením konstanty 500 km a dále předřazení čísla pásu (3 nebo 4) před posunutou souřadnici Y. Od r. 2005 je nahrazen WGS84 - zobrazení UTM (Universal Transversal Mercator) Souřadný systém WGS 84 - Word Geodetic System 1984 je globální geocentrický geodetický systém pevně spojený se zemským tělesem. Počátek a orientace jeho os X,Y,Z\sou realizovány pomocí 12 pozemských stanic se známými přesnými souřadnicemi, které nepřetržitě monitorují dráhy družic systému GPS-NAVSTAR. Systém byl původně definován Ministerstvem obrany USA pro obranné účely, dnes je celosvětově používanou technologií prostorové lokalizace. 4 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á). Transformace souřadných systémů: Postup 1: - Zdrojové souřadnice [X',Y'] převedeme na geografické souřadnice zdrojového systému [cp,Á] - [cp,Á] korigujeme do cílových geografických souřadnic [\l převedeme do cílového rovinného zobrazení Postup 2: - Ze znalosti identických bodů ve zdrojovém a cílovém rovinném zobrazení [Xí,Yí]—► [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) 5 - Mapování - vytváření map měřením nebo fotogrammetrickým mapováním pomocí geodetických základů - bodů geodetických sítí. - Pálkovy 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..) - Měřítko mapy a úroveň územní podrobnosti obsahu geografického informačního systému - 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. 6 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 - mapu vedenou digitálně postupně 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). Tento stav je způsoben programovým rušením vlastnických vztahů v minulosti a několika (neúspěšnými) pokusy geodetů mapové dílo sjednotit. 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:20000 s obsahem topografické mapy - Topografická mapa GŠ ČSA, měřítko 1:25000 (v některém území i 1:10000) 7 Příklad 1 - Informační systém o nemovitostech VNITRNÍ KRESBA MAPY # ID o GEOMETRIE W náleží má obraz PARCELA # ID o PODDĚLENÍPARCELY o TYP PARCELY o ČÍSLO KÚ o ČÍSLO PARCELY má obraz v mapě náleží OBRAZ PARCELY je omezema je omezena Tje na LV obsahuje LIST VLASTNICTVÍ je vlastněn dělí 1. parceljj; dělí 2. parcelu HRANICE PARCELY vlastní OPRÁVNĚNY SUBJEKT # ID o IČO o RODNÉ ČÍSLO 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 ...? 8 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 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.) - prostorovou lokalizaci ve vztahu ke zvolenému souřadnému systému (polární souřadnice, souřadnice ve zvoleném systému kartografického zobrazení) 9 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 (jednotném) prostoru. - V posledních letech toto dělení ztrácí smysl po geoinformačních systémech je požadována komplexní funkcionalita. Prostorová data Geometrie Topologie ^^^ ^^ ^^ ^S^ \^ Vektorová Rastrová uzel-hrana areály příslušnost -'"" "~\^ bod linie areál 10 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í. 11 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ů. Jak reprezentovat prostorovou složku dat v GISech? Povšimněme si objektů na obr. 1. Je vidět, že fragment mapy obsahuje prostorové informace těchto typů. - bod - lomená čára (linie) - oblast (areál) (Texty a značky budeme považovat také za bodové mají svůj referenční bod a velikost textu/značky je stále stejná, nemění se s měřítkem). 12 typedef struct { long x; long y; } pointT; Pevná řádová čárka je výhodná, vyhneme se problémům typu „dva různé body mají nulovou vzdálenost", ale na druhé straně nelze počítat jen v celočíselné aritmetice. double pointDist ( pointT *pl, pointT *p2 ) { double r; r=sqrt((p2->x-pl->x)*(p2->x-pl->x)+ (p2->y-pl->y)*(p2->y-pl->y)); return(r); } Špatně!!! typedef struct { long double; long double; } DPointT; double DPointDist ( DPointT *pl, DPointT *p2 ) ... 13 Datové sklady prostorových GIS 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. 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í podporované geometrické primitivy: Point bod MultiPoint body MultiLine lomené čáry Polygon Areál Vše 2D a 3D varianty. Definice neobsahuje symbologii (barva, síla, styl linií, výplň polygonu). Tu obsluhuje aplikace na základě popisných informací. 14 DGN file, norma IGDS (Intergraph, Bentlev) Geometrická informace je obsažena v souboru *.DGN, soubor sám o sobě nenese popisnou informaci, ta je uložena v relační databázi (nebo *.dfb souboru), DGN soubor obsahuje pouze tzv. „link" = identifikace 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ů). Definice obsahuje symbologii geometrických primitiv. Typ cell může opět obsahovat buňku. Podobné vlastnosti mají i ostatní CAD formáty (DXF, DWG..) 15 ORACLE 7.x (Spatial Data Option) Geometrie je reprezentována čtyřmi tabulkami: SDOLAYER SDODIM SDOGEOM SDOINDEX - obsahuje služební údaje pro prostorovou indexaci - obsahuje rozsah pro jednotlivé dimenze geometrie - obsahuje vlastní geometrii - obsahuje prostorové indexy objektů v SDOGEOM 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. ORACLE 8x, 9x - datový typ SDO_GEOMETRY dále rozlišitelný podle typu na: UNKNOWN_GEOMETRY POINT LINESTRING POLYGON COLLECTION MULTIPOINT MULTILINESTRING MUTIPOLYGON neznámá geometrie bod lomená čára areál (oblast) kolekce geometrií body více linií 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. 16 Pokus o standardizaci uložení prostorové složky: Open GIS Consortium, Inc. - sdružení soukromých, veřejných organizací (universit..) se zájmem vybudování „standardu" struktur a služeb v prostorových datech. 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._______________ OpenGIS® Simple Features Specification For SQL 17 GSCMIIRMXIUME -F_TSÍiB[E_C3flSVI0G ■ F_TBB[E_SCHEMV -F_TBB[E_NBMS ■ FJMlEIK£_CCnMJ G_TSELE_C2I12iLCG~~ G_TBB[E_SCHEMA.------- G_TOB[E_N5MS —■"~— STCRMET5ÉEE----------- HTM«! I WV_TVPR CDCEDDMNSXCN MGCJER SKED---------------------- FeatireTableA/íew ■Gm (QBometiyCdirrri)- fPMTOT.j*i«i«M«N'i«^fiv.tjifcMS SKED ÄHH_SOD SQEScr GSCMHRf CXUME "GID ESBQ ETCEE SBQ XL Yl X Y or GSCMHKf CXUME rem »UN »*GÍ 18 // 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, wkbNDR = 1 Endian }; // Big Endian // Little 19 WKBI Point { byte byteOrder; uint32 wkbType; }; Point point; WKB] [jineString byte { byteOrder; uint32 wkbType; uint32 numPoints; Point points[numPoints]; // 1 // 2 }; WKBPolygon { byte byteOrder; uint32 wkbType; // 3 uint32 numRings; LinearRing rings[numRings]; }; 20 WKBMultiPoint { byte byteOrder; uint32 wkbType; // 4 uint32 num_wkbPoints; WKBPoint WKBPoints[num_wkbPoints] ; }; WKBMultiLineString { byte byteOrder; uint32 wkbType; // 5 uint32 num_wkbLineStrings; WKBLineString WKBLineStrings[num_wkbLnStrgs]; }; wkbMultiPolygon { byte byteOrder; uint32 wkbType; // 6 uint32 num_wkbPolygons; WKBPolygon wkbPolygons[num_wkbPolygons]; } 21 WKBGeometry { union { WKBPoint point; WKBLineString linestring; WKBPolygon polygon; WKBGeometryCollection collection; WKBMultiPoint mpoint; WKBMultiLineString mlinestring; WKBMultiPolygon mpolygon; } }; WKBGeometryCollection { Byt e byt e_o rde r; uint32 wkbType; // 7 u i nt 3 2 num_wkbGe omet rieš; WKBGe omet ry wkbGe omet r i e s[num_wkbGeoms]; } Základní datové typy WKB neumožňují vykreslit mapu - symbologie geometrických elementů - reprezentace bodových prvků - texty (velikost, rotace, font...) Rekurzivní definice WKBGeometry je nutná a vyžaduje tento fakt zohlednit při vývoji aplikací!! 22 Příklad - rekurzivní zpracování geometrie int processWKGB(byte *ge) { int i, j,nP; int newPos,size; byte *pg; pg=(byte *)ge; switch (getWKbType(ge)) // rozskok podle typu { case wkbPoint: case wkbLineString: doSomethingWithLineString(pg); size=sizeofWKBLstr(pg); break; ... case wkbGeometryCollection: newPos=sizeof(byte)+sizeof(uint32)*2; size=newPos; nP=pg->num_wkbGeometries; for (i=0;i 10225914 2 715 2 7 < / L_P ARAM> -595427397,-1075666207 -595438694,-1075937499 10239989 671864 -594758645,-1075683985 -595382726,-1075607457 -595425487,-1075601997 24 -/_ i Trn*.- .ii t Stred x * .260367. Ubuvi^ / x Luďnl la ° 260365 o NemocnIce 260345 Po I i k I i n i ka 260835 Vinařská šk„ ° 260277 Rousovice I I 260283 Tě I ocv í čna Úh Rousov i ce k 260275 260350 Sportovní I.% 9mQ/l? V 33T CTR NELAHOZEVES A Sportpvn í r ' (konečná množina bodů euklidovského 2D prostoru). Typem Tj je tedy typ „bod ve dvourozměrném prostoru". Buď dále T2= Ti takový typ, že pro každé x=[xmin,ymin,xmax,ymax] typu T2, je xmin xminxminQ Indexovací metoda, která podporuje „první zásah" nám nepomůže, neboť nejhorší případ dotazu vede prohledání celého souboru. 30 Problémy vyhledávání rozdělíme na dvě hlavní třídy: - problém statický - problém dynamický Statický: - build(V) vybuduje podpůrné struktury pro množinu V - search(q,V) odpoví na vyhledávací dotaz Dynamický: - 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 Statický problém lze řešit podobně jako dynamický problém opakovaným použitím funkce insert. D Funkce search býva většinou rozdělena na dvě časti, 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); }□ 31 Poznámka 1 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(jVj). Uvádění jiných metod má tedy smysl pouze v případě, že tento základní odhad nějak zlepšíme. D 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. Algoritmus 1 - Vyhledání klíče v binárním stromu 1.Vstup: kořen stromu nod, klíč k. 2. Je-li strom prázdný, potom končíme vyhledávání "neúspěchem". 3. Je-li key(nod) = k, potom končíme "úspěchem". 4. Je-li k key(nod), pokračujeme krokem 1 pro rSon(nod). Algoritmus 2 - Vkládání klíče do binárního stromu 1.Vstup: klíč k. 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íč k. 32 Algoritmus 3 - Rozsahové vyhledání v binárním stromu 1.Vstup: interval [min,max], kořen stromu nod. 2. Patŕi-li key(nod)6o intervalu [min,max], pošleme jej na výstup a aplikujeme algoritmus na ISon(nod) a rSon(nod). 3. Je-li max < key(nod), aplikujeme algoritmus na ISon(nod). 4. Je-li min > key(nod), aplikujeme algoritmus na rSon(nod). 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ř. ISon(nod)=0pro všechny uzly nod). Degenerace nastává tehdy, když jednotlivé prvky vstupují do stromu v nevhodném pořadí. V případě statické verze vyhledávacích problémů lze vybudovat tzv. optimální binární strom (na vstupu procedury build známe celou množinu V). 33 Definice 2 - Optimální strom Strom nazveme optimální, liší-li se počty uzlů v podstromech ISon(nod) a rSon(nod) maximálně o 1 pro jeho každý uzel nod. D Poznámka 2 - Hloubka optimálního stromu obsahujícího \V\ klíčů je logflVI). Algoritmus 4 - Vybudování optimálního binárního stromu 1.Vstup: množina klíčů V, kořen stromu nod. 2. Je-li V=0, skonči. 3. Rozděl množinu V na po dvou disjunktní množiny V1}{med(V)},V2\aK že med(V)'\e medián množiny V, klíče z V1 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 V1 pro levý podstrom ISon(nod). 6. Aplikuj algoritmus na množinu V2 pro pravý podstrom rSon(nod)n 34 Definice 3 - Vyvážené stromy Binární strom nazveme vyvážený, liší-li se hloubky ISon(nod) a rSon(nod) maximálně o 1 pro jeho každý uzel nod (hloubkou stromu rozumíme maximální délku cesty od kořene k listu). D h\ h+l\ h\ h Poznámka 3 - Hloubka vyváženého stromu obsahujícího \V\ klíčů je ~logflVI). Definice 4 - B B ľa] stromy Buď 0 < a< 1/2. Binární strom T patří do třídy BB[a] stromů, platí-li pro jeho každý uzel nod, podstrom Tree(nod) s kořenem nod, levý podstrom ISon(nod) a < IISon(nod)l/ITree(nod)l <1-a. D pokud byl v nějakém okamžiku podstrom definovaný uzlem nod optimální, pak k porušení podmínky z definice BB[a] stromů musí dojít k minimálně c./Tree(nod)l vložení/mazání uzlů do/z příslušného podstromu (c je konstanta závislá pouze na parametru a). 35 Definice 5 - B+-stromy B-strom řádu m je strom s těmito vlastnostmi: - každý uzel má < m synů - každý uzel, s výjimkou kořene a listů, má > 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-1 klíčů D Hlavní myšlenka spočívá ve tvaru uzlů: Po key1 pr... Pfr-r keyk pk kde p, je ukazatel na uzel pro s všechny klíči keys vlastností: key m < key < key i 36 Metoda „GRID" 4 . l .5 .4 3 r .6 2 íl .7 .3 1 12 3 4 5 6 7 5 ". 1 .5 .4 / 4 3 .6 / \ 2 jl .7 .3 / 1 Dotazový obdélník 12 3 4 5 6 7 Prostorový dotaz v GRIDu, prohledáváme pouze čtverce (4,2) a (5,2), pro efektivní přístup ke čtvercům použijeme libovolnou vyhledávací metodu (strukturu). 37 Realizace GRID metody v prostředí SQL create table GTABLE ( GID number, XMIN number, YMIN number, XMAX number, YMAX number, WKB_GEOMETRY blob, constraint GTABLE_PK primary KEY (GID) ); create table GTABLE_IDX ( GID number, GRID_X number, GRID_Y number ); 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(grld_x, gr±d_y) ; 38 create trigger gtable_spatial before insert or update of x,y on GTABLE for each row begin xfrom xto yfrom yto =GET_GRID_X( =GET_GRID_X( =GET_GRID_Y( =GET_GRID_Y( NEW.XMIN); NEW.XMAX); NEW.YMIN); 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) Create table SPATIAL_QUERY ( id int, xmin int, ymin int, xmax int, ymax int, constraint SPATIAL_QUERY_PK primary key (id) ); 39 CREATE TABLE SPATIAL_QUERY_IDX ( query_id int, grid_x int, grid_y int, constraint SPATIAL_QUERY_IDX_PK primary key (query_id,grid_x, grid_y), constraint SPATIAL_QUERY_IDX_FK foreign key query_id references SPATIAL_QUERY(ID) on delete cascade ); create trigger SPATIAL_QUERY_SPATIAL before insert of id on SPATIAL_QUERY for each row xfrom,xto,yfrom,yto,i, j int; BEGIN xfrom:=GET_GRID_X(:NEW.XMIN); xto:=GET_GRID_X(:NEW.XMAX); yfrom:=GET_GRID_Y(:NEW.YMIN); yto:=GET_GRID_Y(:NEW.YMAX); pro xfrom<=i<=xto a yfrom<=j<=yto BEGIN INSERT INTO SPATIAL_QUERY_IDX VALUES (:NEW.ID,i,j); END; END; / 40 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, například ze sekvence select query. nextval from query_sequence. 2) Inicializace dotazu: insert into spatial_query values (id,xmin,ymin,xmax,ymax), tím se vlivem triggeru spatial_query_spatial automaticky vloží identifikace gridových čtverců to tabulky spatial_query_idx 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; 4) Ukončení prostorového dotazu: delete from spatial_query where id=id; Jaký mechanismus odstraňuje řádky z tabulky spatial_query_idx? 41 Exekuční plán prostorového dotazu GRID TOAD - [DRASIL@DATA_BRNO/INDEX GTABLEJDXJ1 HHZ] ile Edit Grid SQL-Window Database Create View Tuning Window Help j-JSj _x] f& soi. m m \m m -i - ** Gá u i sB ü GRID Y NUMBER GID: = GID \ ' GTABLE GID NUMBER XMIN NUMBER YMIN NUMBER XMAX NUMBER YMAX NUMBER WKB GEOMETRY BLOB SPATIAL_QUERY_IDX ID NUMBER GRID X NUMBER GRID Y NUMBER ID ID SPATIAL_QUERY ID NUMBER XMIN NUMBER YMIN NUMBER XMAX NUMBER YMAX NUMBER 42 Výhody vs. nevýhody GRID metody. B - 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ů) i - 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ů 43 Quad Tree - kvartérní strom - urSon(nod) - klíče tohoto podstromu jsou „vpravo nahoře" od bodu key(nod) - ulSon(nod) - klíče tohoto podstromu jsou „vlevo nahoře" od bodu key(nod) - IrSon(nod) - klíče tohoto podstromu jsou „vpravo dole" od bodu key(nod) - HSon(nod) - klíče tohoto podstromu jsou „vlevo dole" od bodu key(nod) Obr. 8 - Quad Tree - Kvartérní strom dotazový obdélník Obr. 9 - Rozsahový dotaz v Quad-Tree pro body. Podstrom „4" neprohledáváme. 44 Algoritmus - Vkládání do Quad-Tree Vkládání je stejné, jako v případě obyčejných binárních stromů. Hledáme tedy bod v kvartérním stromu, dokud nenajdeme volnou pozici. Do ní vložíme nový klíč. Algoritmus - Rozsahový dotaz v Quad-Tree pro body 7. Vstup: kořen stromu nod a obdélník q=[xmin,ymin,xmax,ymax]. 2. Je-li Tree(nod)=0, skonči." 3. Je-li key(nod) v dotazovém obdélníku q, pošli jej na výstup a aplikuj algoritmus na všechny jeho čtyři podstromy. 4. Vyber podstromy, pro které budeš aplikovat algoritmus (x(,) značí x-ovou souřadnici klíče): - je-li x(key(nod)) > xmax a y (key(nod)) > y max, potom aplikuj algoritmus na větev llSon(nod), - je-li x(keyfnod)) > xmax, potom aplikuj algoritmus pouze na větev llSon(nod) a ulSon(nod), - a analogicky pro ostatní případy. 45 Definice 6 - k-D strom Úrovní level(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>0, x=(x0,..,xi,..,xk.1), y=(y0,..,yi,..,yk.1)e Sr Říkáme, že x xmax, potom aplikuj algoritmus na větev ISon(nod), - analogicky pro další možné případy. 47 Dotazový obdélník Obr. 11 - Rozsahový dotaz v 2-d-stromu pro body. Podstrom „2" neprohledáváme. Vyvažování multidimensionálních stromů je komplikované. Nedají se totiž provádět rotace jako v klasických binárních stromech (srovnej s obr. 5), protože v každém patře stromu měníme srovnávací kritérium. Pomocí BB[a] techniky lze však k-D stromy udržovat vyvážené pomocí částečné reorganizace. K tomu potřebujeme techniku pro budování optimálního 2-D stromu. Algoritmus -Vybudování optimálního 2-D stromu 1. Vstup: množina bodů V, kořen stromu nod a le{x,y} 2. Je-li V=0, skonči. 3. Rozděl množinu V na po dvou disjunktní množiny V1}{medi(V)},V2tak, že medi(V) je takový bod, že jeho x-ová souřadnice je medián množiny /-ových souřadnic z V, /-ové souřadnice z V1 jsou menší než medi(V) a /-ové z V2 jsou větší než medi(V). 4. Definuj kořen stromu jako medi(V). 5. Je-li /rovno x potom přiřaď l=y jinak l=x 6. Aplikuj algoritmus na množinu V1 pro levý podstrom ISon(nod). 7. Aplikuj algoritmus na množinu V2 pro pravý podstrom rSon(nod)n 48 Metodu k-D stromů lze použít i na obdélníky, které můžeme považovat za 4D body. Použijeme tedy 4-D strom. Algoritmus 7 - 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 Tree(nod)=0, skonči. 3.ÜSOU-M obdélníky q a key(nod) incidentní, pošli id(nod) na výstup a aplikuj algoritmus na ISon(nod) a rSon(nod). 4. Podle úrovně, ve které se nacházíš ve stromu, se rozhodni, zda můžeš vynechat nějakou větev, napr.: Je-li level(nod) mod 4 = 0 a xmin(nod(key)) > xmax(q) aplikuj algoritmus pouze pro ISon(nod). Analogicky pro další úrovně, v každé se dá za jistých podmínek jedna větev vynechat. 49 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. 12 - Čí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 strlen(K). - Podřetězec řetězce K z levé strany délky /označme lsubstr(K,l). 50 Tvrzení 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=mln{strlen(NZ(Q(A))),strlen(NZ(Q(B)))}, potom: lsubstr(Q(A),l)=lsubstr(Q(B),l) D. 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é: lsubstr(Q(A),strlen(NZ(Q(S))))= NZ(Q(S)) aAdS^0 3. Pošli na výstup všechny obdélníky A, pro které: Q(A)=PaAdS*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. 51 Algoritmus Dekompozice dotazu v non-pointer QuadTree 1. Vstup - dotazový obdélník S. 2. Rozděl obdélník S na obdélníky S7 a S2 (S7 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 S1 a S2 podle druhé souřadnice. Následuje příklad, na kterém demonstrujeme hlavní výhody této metody: - Velmi snadná implementace v prostředí SQL - tedy relačních databází - „jeden objekt" =„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. 52 Dekompozice dotazu - 4 obdélníky s klíč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) 53 Intervalové stromy Za zaměstnance podniku máme data v tabulce: Identifikace Počátek_prac_poměru Konec_prac_poměru a potřebujeme řešit dotazy typu "kdo všechno byl zaměstnán v daném období ?". D Definice 7 - Intervalový strom Intervalový strom pro množinu V={[Xi ,x2],..., [x2n-i ,X2n]} je tvořen: - binárním vyhledávacím stromem pro 2n počátečních a koncových bodů - každý uzel nod (definovaný bodem x(nod)) navíc obsahuje seznam intervalů l(nod) ^ V takový, že x(nod) je bodem každého intervalu l(nod) - levý (pravý) podstrom uzlu nod je intervalový strom pro intervaly, jejichž pravé (levé) koncové body jsou menší (větší) než x(nod) D Již z definice intervalového stromu je zřejmé, že je nutné jej budovat postupně. Algoritmus 9 - Budování intervalového stromu 1.Vstup: množina intervalů V. 2. Vybuduj binární strom T pro počáteční a koncové body z V. 3.Zařazujeme postupně všechny intervaly co nejvýše do stromu T. 54 Poznámka 6 Každý uzel nod dělí množinu Vóo tří skupin. Jednak jsou to intervaly ležící vlevo od x(nod), jednak intervaly ležící vpravo od x(nod) a konečně intervaly které bod x(nod) obsahují. Algoritmus - Vyhledání intervalů v intervalovém stromu 1.Vstup: interval dotazu q=[xminQ,xmaxQ], kořen stromu nod 2. Je-li nod list, potom skonči. 3. Je-li x(nod) v intervalu q, potom - 3.1. I(nod) na výstup - 3.2. Aplikuj algoritmus pro ISon(nod) a rSon(nod) 4. Je-li maxQ < x(nod) potom: - 4.1. Projdi seznam l(nod) a na výstup pošli ty intervaly z l(nod), které incidují s q. - 4.2. Aplikuj algoritmus na ISon(nod) 5.Je-li minQ > x(nod) potom: - 5.1. Projdi seznam l(nod) a na výstup pošli ty intervaly z l(nod), které incidují s q. - 5.2. Aplikuj algoritmus na rSon(nod). Poznámka 7 Seznam l(nod) lze reprezentovat dvěma provázanými seznamy L(nod) a R(nod), ve kterých jsou levé a pravé koncové body. L(nod)\e uspořádán vzestupně, R(nod)\e uspořádán sestupně. Toho lze využít v krocích 4.1. a 5.1. tak, že procházení seznamu lze ukončit prvním neúspěchem.D 55 Intervalové stromy pro obdélníky Pro jednu osu (třeba x) vybudujeme intervalový strom s tím rozdílem, že seznamy l(nod) budou 2D intervaly, tedy obdélníky. Tím dostaneme primární strukturu pro 2D variantu intervalového stromu. Sekundární struktura bude tvořena intervalovými stromy pro druhou (y-ovou) osu v každém uzlu nod primárního intervalového stromu pro y-ové intervaly ze seznamu l(nod). Rozsahový výběr v takto vybudované struktuře potom probíhá stejně, jako v 1D variantě s následujícím rozdílem: - 3.1. Použije se sekundární struktura pro výběr podle y- interval - 4.1. Zohlední se y- intervaly při posílání na výstup" - 5.1. Zohlední se y- intervaly při posílání na výstup 56 SB+stromy Jsou modifikací B+ 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í. Listy SB+ stromech jsou tedy tvořeny strukturami, které můžeme popsat následujícím způsobem: typedef struct // seznam intervalů { long idlnterval; // identifikace intervalu char incidType; // 'b'-počátek, } // 'c'průchozí, 'e' konec sbListT; typedef struct // list SB+ stromu { long point; // hodnota bodu sbListT list[l]; // seznam incid.intervalů } sbLeafT; 57 SB+ strom 8 6 4 2 R 1 R 2 S 2 S 3 R 3 S 1 i i i i r 10 12 14 16 8 4 s\ V \ ^ 5i 10 12 I 16 12 14 ř 5T HF ^* 16 Rl b Rl c R2b Rl c R2c SI b S2b Rl e R2e SI c S2c SI e S2c S2e S3 b R3b S3 c R3 c S3 e R3 e 58 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 e S, i>xmin} 3. Pro ip < i < xmax pošli na výstup identifikace intervalů ze seznamu listu reprezentovaným bodem /(identifikace se mohou opakovat, posíláme jen jednou). 59 Algoritmus - Vkládání intervalů do SB+ stromu 1. Vstupní interval [xmin,xmax], jeho identifikace /. 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 ='ď 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 0 (0,0) 71 Distance(gl Geometry, g2 Geometry) Precision Vzdálenost dvou geometrických objektů Poloha bodu vůči úsečce: : Double + (0,0) + Rotace bodu za účelem určení jeho polohy vzhledem k úsečce x' =x. cos (g>) -y. sin (g>) y'=x. sin (q>) +y. cos (q>) 72 Poloha bodu vůči polygonu: Úniková polopřímka z polygonu 73 Algoritmus - Bod v polygonu 7.Najdi v bodech polygonu bod, jehož y-ová souřadnice je různá od souřadnice bodu, který testujeme. Jestliže neexistuje, ukonči proceduru s výsledkem LEŽÍ_NAJHRANICI. Nechť pp je polopřímka vycházející z testovaného bodu rovnoběžná s osou x v kladném směru. 2. nPrus:=0 3.Od vybraného bodu postupně procházej všechny úsečky a proveď body 4-7. 4.Leží-li testovaný bod na úsečce, ukonči proceduru s výsledkem LEŽI_NA_HRANICI. 5.Má-li úsečka vlastní průsečík s polopřímkou pp, potom nPrus:=nPrus+1 6.Končí-li úsečka na polopřímce a začíná-li mimo polopřímku, stanov podle počátku úsečky odkud:=POD nebo odkud:=NAD 7.Začíná-li úsečka na polopřímce a končí-li mimo polopřímku a pokračuje-li do jiné poloroviny, než je stav proměnné odkud, potom nPrus:= nPrus+1. 8. Je-li nPrus sudý, ukonči proceduru s výsledkem VNĚ. 9. Je-li nPrus lichý, ukonči proceduru s výsledkem UVNITŘ 74 Množinové operace Intersection (gl Geometry, g2 Geometry) Geometry Difference (gl Geometry, g2 Geometry) Geometry Union (gl Geometry, g2 Geometry) Geometry SymDifference(gl Geometry, g2 Geometry) Geometry Buffer (gl Geometry, d Double Precision): Geometry ConvexHull(gl Geometry) Geometry 75 Bod - bod Triviání operace. Pozor, pro příslušnost bodu k množině je nutné použít vhodnou přístupovou metodu k prostorovým datům. Bod - lomená čára Vzájemná poloha úsečka X bod. Bod - oblast Poloha bodu vůči polygonu Lomená čára - lomená čára Poloha dvou úseček Lomená čára - oblast Algoritmus 13 - Průnik lomené čáry s oblastí. 1. Vstup: oblast a lomená čára. 2. Ze vstupní lomené čáry vytvoř seznam P segmentů lomené čáry takových, které buď neprotínají hranice oblasti, nebo jsou celé tečné. 3. Ze seznamu P vytvoř seznam ScP takový, že libovolný vnitřní bod každého segmentu z S leží uvnitř oblasti. 4. Zřetěz segmenty z S do "co nejdelších" lomených čar, a výsledek pošli na výstup 76 Oblast - oblast Průnik dvou oblastí A é ŕ-------------- r B Á AnB k ^ r ------------------------► w Průnik oblastí s tečnými hranicemi 77 Algoritmus 15 - Průnik dvou oblastí 1. Vstup: dvě orientované oblasti. 2. Všechny hrany hranic oblastí modifikuj tak, aby se vzájemně neprotínaly, mohou však splývat s hranami hranic z druhé oblasti. Potom mají tyto vlastnosti - hrana splývá s jinou z druhé oblasti - hrana leží celá uvnitř druhé oblasti - hrana leží celá vně oblasti 3. Do seznamu zařaď ty hrany, které buď, leží celé v druhé oblasti, nebo splývají s nějakou hranou z druhé oblasti, se kterou mají stejnou orientaci, (totožné hrany jen jednou). 4. Z vybudovaného seznamu zřetěz hranice výsledné oblasti a výsledek pošli na výstup. Nástin důkazu, že 4. Je uskutečnitelný... 78 Příklad (systém GeoStore - GEOVAP): V GIS systému máme (mimo jiné ...) vrstvu lesů reprezentované jako areály a vrstvu venkovních úseků vysokého napětí. Zajímá nás, kde lesy zasahují do bezpečnostního pásma 10 metrů kolem úseků vysokého napětí, a to jen pro určitý výřez území. Obři Zvolíme úlohu „Zóny", vyplníme vstupní argumenty úlohu - tabulka VN_USK (úseky) a poloměr 10000 mm. Po stisknutí tlačítka „Proveď" jsou liniové prvky z tabulky VN_USK „obaleny" zónami o zvoleném poloměru. Výstup bude mít nastavenu tabulku BUFFER. (Obr. 2). 79 Obr. 2 Zvolíme úlohu „Průnik", první argument bude tabulka, ve které jsou lesy, druhým argumentem bude tabulka BUFFER (po proběhnutí 1) je nastavena tato tabulka na zónách). Volitelně můžeme zvolit možnost vyplnění výsledných areálů. Po provedení dostaneme kýžený výsledek (Obr. 3). 80 ■tří / isracm HjE] Nápověda Zdroj Výsledek Zpracovat Výkres Výkres jen okno \j 1. Argument Operace 2. Argument 5_LESY_P0L Průnik 1 BUFFER V 1 Výsledek Ref. sloupec fy Vyplnit v>_ PRŮSEKY 1 1 sledné plochy . Proveď | Obr. 3. 81 Transformace souřadných systémů: Vstup: Dva seznamy bodů, které si „odpovídají" {[xi,yi] • • [xn,yn] } { [UirVj . . [un,vn] } ' (Transformujeme [u,v] do [x,y] s co nejmenší chybou) Výstup: Parametry transformačních rovnic 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í... Podmínka: £ dist2( [Xi.Yi] , [f (Ui,Vi) ,g(Ui,Vi) ] ) =min kde dist2( [xi, yi] , [x2f y2] ) = (xi-x2) 2+ (yi-y2) 2 82 Lineární regrese: Příklad pro lineární transformaci £ (aiUi+biVi+ci-Xi) 2+ (a2Ui+b2Vi+C2-yi) 2 = min dT/dai = £2 (aiUi + biv± + ci - x±) .u± = 0 dT/dbi = £2 (aiUi + biv± + Ci - x±) . v± = 0 dT/dci = £2 (aiUi + biv± + Ci - x±) =0 Soustava normálních rovnic (pro g(u,v) analogicky): ai Euí + bi EuiVi + ci Euí = ExiUi ai EuiVi + bi Zvi + Ci Zvi = Ex^vi ai Euí + bi Zvi + ci .n = Exi 83 Rastrová data v GIS í/l' . Typy rastrových dat používaných pro GIS technologie jsou stejná jako v počítačové grafice: - binární - polotónová - víceúrovňová 84 Pro další práci očíslujeme sousedy pixelu P následujícím způsobem: 3 2 1 4 P 0 5 6 7 Sousedé 0,2,4,6 se nazývají přímí (d-) sousedé pixelu p. Sousedé 1,3,5,7 se nazývají nepřímí (\-) sousedé pixelu p. Definice - Histogram obrazu. Nechť f je polotónový obraz barev 1..M. Jeho histogramem rozumíme konečnou posloupnost Aiß}=fAif..AiM}, kde, ft, je počet pixelu s barvou /'. D /N počet -> 0 hodnota 255 Obr. 18 - Histogram obrazu Definice - Matice sousednosti Nechť f je polotónový obraz barev 1..M. Jeho maticí sousednosti rozumíme čtvercovou MxM matici CM(f)={cmjj}, kde, c/T7,yje počet (přímo) sousedících pixelu o barvě /a/.D 85 Lineární filtrace Buď f polotónový obraz, M > 0. Položme g(x,y)= H(M,x,y) kde H\e libovolná funkce, která v konstantním čase počítá novou hodnotu pixelu g(x,y)z okolí pixelu (x,y) o rozměru Mn Funkce H bývá někdy váženým průměrem pixelu a lze ji vyjádřit: H(M,x,y)=Zl=.MM £j=MM h(i,j)*f(x+i,y+j) 86 a) Filtry zhiazujici filtry a) b) 1 1 1 1 1 1 1 1 1 1 2 1 2 4 2 1 2 1 ■J* r * * m f iff í/i "f A ^ i^J ^^^ T J í 87 b) Filtry, které se snaží „zostřit" obraz -1 -1 -1 -1 n -1 -1 -1 -1 " ^■•.-!./-V."--" -._:ä:__-\ -.rJri 88 c) 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 89 Původní obraz Zhlazovací filtr: Zostřující filtr: Detektor hran: 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.D 90 ......°..„.....i 1 1 1 1 0 lÜ 1 1 I * s »___1 0 1 ° v ! , 1 ! 0 | 0 0 o 1 > vektorově —► rastrově Transformace obrazu [ij] 4. 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. 5. 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ů). / = F(x,y) j = G(x,y) kde (ij) značí souřadný systém originálního obrazu, (x,y) souřadný systém obrazu nového. 6. fázi procházíme cílový obraz, pomocí transformačních funkcí Fa 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árni transformace - konvoluce okolí MxM 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. 92 .*.*.. .*.*. ..*.. ..*.. ..*.. * * * * Obr. 20 - Skelet binárního obrazu: binární obraz je reprezentován znaky., jeho skelet znaky *. Definice 12 - Skelet Nechť R je množina pixelů, B její hranice (kontura), P bod v R. Nejbližší soused bodu P na hranici B je bod M z B takový, že pro každý bod M z B , M je různý od M 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 Rn 93 Algoritmus 16- 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 0 P 0 B B B A A C 0 P 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ý. 94 Topologické úlohy: 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: N zacma s~ Hrana \ Uzel *" ' *■ Vedení Uzávěr .. f N \ Přípojka Odběrné místo „ , »^ L ^ J } Základní datová struktura areálového grafu: 1.areál Hrana Hr. obce Hr. katas Areál Obec Katastr 2.areál 95 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ž?". - Nejkratší 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 /?eH označme w(h). Nechť dále každý uzel u,eU má 2D souřadnice (x,,yj). Pro libovolné uzly u,v označme d(u,v) jejich vzdálenost v E2. Pro libovolnou hranu hj=(Ui,Vj) nechť dále je d(Uj,Vj)