Pojmy související s GIS Matematická kartografie - disciplína zabývající se převodem zemského povrchu (modelovaného elipsoidem) do roviny. Volí vhodná kartografická zobrazení, tedy funkce zobrazující elipsoid do roviny. ijt/ \ x/v' \l —\ \ \X I V .P' IX i i —y rovník D Válcové zobrazení Kuželové zobrazení Azimutální zobrazení 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. - V textu se těmito pojmy dále nezabýváme, budeme předpokládat, že prostorová data jsou lokalizována ve vhodném souřadném systému. - 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. 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 i 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. Technické mapy měřítka 1:500 (a větších měřítek) jsou vytvářeny v systému JTSK s obsahem: polohopis, sítě, čísla popisná, podle konkrétního území a záměru autora a uživatele 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:20000 s obsahem topografické mapy - Topografická mapa GŠ ČSA, měřítko 1:25000 (v některém území i 1:10000) Příklad 1 - Informační systém o nemovitostech VNITRNÍ KRESBA MAPY # ID o GEOMETRIE ' naleží má obraz PARCELA # ID o PODDĚLENÍPARCELY o TYP PARCELY o ČfSLOKÚ o ČÍSLO PARCELY má obraz v mapě náleží OBRAZ PARCELY je omezema je omezena 'je na LV obsahuje dělí 1. parcel LIST VLASTNICTVÍ je vlastněn dělí 2. parcelu 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...? 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í) 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 ^^^ ""'- \^ Vektorová Rastrová uzel-hrana areály příslušnost ■"-"" | "\^ bod linie areál 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ů. 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). 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 ) -. 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í. 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..) 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 MÜTIPOLYGON 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. 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 GEa€nKY_03IIM«S ■FJHBĽE_CKIKĽOG ■ FJHBĽE_3CHEMA -F_TOBCE_NfiME ■ F_GEĽMFJKf_CCíUMí GJHBU2_CATOI0G^— GJHBĽEJäCHEMA-~ G torte1, NSME- SrCE5CE_TXEE------ GKMHKYTÍEE CXXHLPIMENSICN M*X_EPR SRID FeafcreTade'Víew •ged (QBometryCdlirm)- SER[ĽD^_REFEBE10LSYSIEMS SRID ÄHHJWC ATJIH_SRID SKEXT (XOEnCUXJIMíE 'GH) ESEQ ETXEE SEQ XL Yl X<řffiX_EER> Y<řffiXEER> or GEĽMFJKf_CX3XMíS GH) »UN YMIN »«X YM« WKB_GKMFJKY // 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 WKBPoint { byte byteOrder; uint32 wkbType; Point }; point; WKBLineString { byte byteOrder; uint32 wkbType; uint32 numPoints; Point }; points[numPoints] ; WKBPolygon { byte byteOrder; uint32 wkbType; uint32 numRings; // 1 // 2 // 3 LinearRing rings[numRings]; }; 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]; } WKBGeometry { union { WKBPoint WKBLineSt ring WKBPolygon WKBGeomet ryCollect ion WKBMultiPoint WKBMult iLineSt ring WKBMultiPolygon point; linestring; polygon; collection; mpoint; mlinestring; mpolygon; } }; WKBGeometryCollection { Byte uint32 uint32 WKBGeometry byte_order; wkbType; // 7 num_wkbGeometries; wkbGeometries[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í!! 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 -595427397,-1075666207 -595438694,-1075937499 10239989 671864 -594758645,-1075683985 -595382726,-1075607457 -595425487,-1075601997 Lijďnl la 260365 Stred 260367n :bu^i4 V 337 CTR NELAHOZEVES A NemoeO i ce 260345 Po I í k I í n i ka> 260835 °o Vinařská šk. í ^ 260277 Rousovice I I 260283 e Iocvicna 260275 ■Oportovn í r f): TA O ° Rousovice 260350 Sportovní í I 002 nonn/io oi \ ce AEA15 AEA13 AEA16 AEA14 Dokumentační systémy správců sítí jsou často založeny na CAD prostředcích: - bohatší repertoár vyjadřovacích prostředků - ověřené prostředky pro pořizování dat - součástí geometrie je i její symbologie (grafická reprezentace Geometrické elementy v CAD systému (část normy IGDS - Bentley Systems, Intergraph) IGDS WKB CELL_HEADER_ELM WKBGeomet ryCollect ion LINE_ELM WKBLineSt ring LINE_STRING_ELM WKBLineSt ring SHAPE_ELM WKBPolygon TEXT_ELM WKBPoint TEXT_NODE WKBPoint CURVE_ELM WKBLineSt ring CMPLX_STRING_ELM WKBLineSt ring CMPLX_SHAPE_ELM WKBPolygon ELLIPSE_ELM WKBPolygon ARC_ELM WKBLineSt ring POINT_STRING_ELM WKBMultiPoint BSPLINE_ELM WKBLineSt ring DIMENSION_ELM WKBGeomet ryCollect ion MULTILINE_ELM WKBMultiLineString Definice 1 - Problém vyhledání Buď V konečná množina objektů typu Th q objekt typu T2. Problém vyhledání je funkce search(q,V), která vrací odpověď typu T3. D Příklad 2 - Problém příslušnosti prvku k množině Položme Ti = T2, aT3 = {T,F}. Vrací-li funkce search(q,V) hodnotu 7 v případě, že q e V a hodnotu F v případě q č V, potom říkáme, že funkce search řeší problém příslušnosti pro množinu V. D Příklad 3 - Rozsahový dotaz na uspořádané množině Nechť (V,<) je úplně uspořádaná množina, T2= Ti*Ti, T3 = expfTi). Je-li q = [low,high] a vrací-li funkce search takovou množinu RcV, že pro všechna xeR platí low xminxminQ Indexovací metoda, která podporuje „první zásah" nám nepomůže, neboť nejhorší případ dotazu vede prohledání celého souboru. 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 y 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ý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); }□ 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. Algoritmus 3 - Rozsahové vyhledání v binárním stromu 1.Vstup: interval [min,max], kořen stromu nod. 2.Patří-li key(nod) do 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). 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 log(IVI). 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 l/na po dvou disjunktní množiny V1,{med(V)},V2tBk, ž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 16 pro pravý podstrom rSon(nod)n 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 ~log(IVI). Definice 4 - BBÍal 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<'\-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ě clTree(nod)l vložení/mazání uzlů do/z příslušného podstromu (c je konstanta závislá pouze na parametru a). 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 /c syny obsahuje k -1 klíčů D Hlavní myšlenka spočívá ve tvaru uzlů: Po keyi p,... p/r-í keyk pk kde p, je ukazatel na uzel pro s všechny klíči keys vlastností: keyi.i< key < key i Metoda „GRID" 4 .1 .5 .4 3 .6 2 l\ l\ 1 ^ .7 l l l .3 1 1 l . I 3 4 5 5 4 ~. l .5 .4 / '------- 3 r .6 / 2 i .7 1 1 1 .3 ' 1 '— „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). 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(grid_x, grid_y); 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 : =GET_GRID_X ( : NEW. XMAX) ; yf rom: =GET_GRID_Y ( : NEW. YMIN) ; yto : =GET_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) Create table SPATIAL_QUERY ( id int, xmin int, ymin int, xmax int, ymax int, constraint SPATIAL_QUERY_PK primary key (id) ); 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; / 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? Exekuční plán prostorového dotazu GRID 'TOAD - [DRASIL@DATA_BRNO/INDEX GTABLEJDXJ1 ma £g File Edit Grid SQL-Window Database Create View üebug Tuning Window Help - |fl | x[ SGL &j Z? SGL l~ri <\V ^ P» F1! • EH Dá Ü *VE VE ^* m & ID> O C* select /*+ru2e*/ A.grid from gtable A, cjt.afcile_idx B, spatial_o;uery_idx C where A.GID=B.GID B . grid_x=C . gr id_x B . gr id_y=C . gr id_y C.id=0; AND AND AND jd i_j_l. Explain Plan ] Auto Trace j DBMS Output - SELECT STATEMENT Optimizer=HINT: RULE B-NESTED LOOPS ■3-NESTED LOOPS ;■■■■ INDEX (RANGE SCAN] OF SPATIAL_QUERY_IDX_PK (UNIQUE) B- TABLE ACCESS (BY INDEX ROWID) OF GTABLEJDX !■- INDEX (RANGE SCAN) OF GTABLEJDXJ1 (NON-UNIQUE) INDEX (UNIQUE SCAN) OF GTABLE_PK (UNIQUE) :-1 |DRASIL@DATA_BRNO iComrnit is OFF GTABLEJDX GID NUMBER GRID X NUMBER 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 r SPATIAL QUERY IE XMIN YMIN NUMBER Dk> NUMBER NUMBER XMAX NUMBER YMAX NUMBER 88 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ů Quad Tree - kvartem í 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" neprohledavame. 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ér n í 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(key(nod)) > xmax, potom aplikuj algoritmus pouze na větev llSon(nod) a ulSon(nod), - a analogicky pro ostatní případy. 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=(xo,..,Xj,..,xk.i), y=(yo,-,yb-,yk-i)E $> Říkáme, že x xmax, potom aplikuj algoritmus na větev ISon(nod), - analogicky pro další možné případy. 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 I e{x,ý\ 2. Je-li V=0, skonči. 3. Rozděl množinu V na po dvou disjunktní množiny Vh{medi(V)}, V2 tak, ž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 y7 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 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, např.: Je-li level(nod) mod4 = Oaxmln(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. Pevný kvartér n í 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íč AC označme jeho „nenulovou" část, tedy levý podřetězec symbolem NZ(K). - Délku znakového řetězce AC označme strlen(K). - Podřetězec řetězce AC z levé strany délky / označme lsubstr(K,l). 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)=PAAnS*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. 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 S* a S2 (S* 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. 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) 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]}\e 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)c^ y 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. 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) obsah ují. D Algoritmus - Vyhledání intervalů v intervalovém stromu 1.Vstup: interval dotazu q=[xminQ,xmaxQ], kořen stromu nod 2.Je-li noc/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) je uspořádán vzestupně, R(nod) je 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 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 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'pruchozi, 'e' konec sbListT; typedef struct // list SB+ stromu { long point; // hodnota bodu sbListT list[l]; // seznam incid.intervalů } sbLeafT; SB+ strom R 1 R 2 S2 S 1 S 3 R 3 i i r 10 12 14 16 / 7 f 4 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 R3c S3 e R3e 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). 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 ='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 ° (0,0) 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 () +y. cos (q>) Poloha bodu vůči polygonu: Úniková polopřímka z polygonu 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ŽÍNAHRANICI. 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Ř 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 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 S^P 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 Oblast - oblast Průnik dvou oblastí Průnik oblastí s tečnými hranicemi 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ý... 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í. Obr1. 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). 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). **--"*v.\ í'-' 1. Argument |5_LESY_P0L Operace Průnik______I 2. Argument | BUFFER Výstup — Výsledek Ref. sloupec l^ Vyplnit výsledné plochy Obr. 3. Transformace souřadných systémů: Vstup: Dva seznamy bodů, které si „odpovídají" { [xi,yi] . . [xn,yn] } { [Ui,V!] . . [un,vn] } Výstup: Parametry transformačních rovnic Lineárni: f (u,v)=aiu + biv + Ci g(u,v)=a2u + b2v + c2 B i lineární: f (u,v)=aiu + biv + Ciuv + di g(u,v)=a2u + b2v + c2uv + d2 Kvadratická, kubická, obecná polynomiální... Takové, že E dist2( [Xi,yi] , [f (Ui,Vi) , g(Ui,Vi) ] ) =min kde dist2 ([xi, yi] , [x2, y2] ) = (x!-x2) 2+ (yi-y2) 2 Lineární regrese: Příklad pro lineární transformaci E(aiUi+biVi+Ci-Xi) 2+(a2Ui+b2Vi+C2-yi)2 = min dE/dai = E2 (aiUi + biVi + ci - xi) .ui = 0 dE/dbi = E2 (aiUi + biVi + ci - xi) . v± = 0 dE/dci = E2 (aiUi + biVi + ci - x±) =0 Soustava normálních rovnic (pro g(u,v) analogicky): ai Euí + bi EuiVi + ci Eui = ExjUí ai EuiVi + bi Lvi + ci Evi = ExjVí ai Euí + bi Lvi + ci .n = Exi Rastrová data v GIS 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á 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í(i-) sousedé pixelu p. Definice - Histogram obrazu. Nechť f je polotónový obraz barev 1..M. Jeho histogramem rozumíme konečnou posloupnost hfä^h^hd, kde, A?, 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, cm,yje počet (přímo) sousedících pixelu o barvě /ay.D 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.D Funkce H bývá někdy váženým průměrem pixelu a lze ji vyjádřit: H(M,x,y)=Zi=.M,M Zi=.MM h(hj)*f(x+i,y+j) a) Filtry zhiazujici filtry a) b) 1 1 1 1 2 1 1 1 1 2 4 2 1 1 1 1 2 1 b) Filtry, které se snaží „zostřit" obraz -1 -1 -1 -1 n -1 -1 -1 -1 r■ •" ■ í k -v .-i í "^ ■■■■ŕs/lftrr^..Ťi * ■ - ■■■- ■ --ĺ- I■ ■ z ■ .■ 7?^i ■--'. :■■ -.;:j.' ■-£ ?.' mm 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 "^mz áE Ui ■~t'.-f-* 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 o o o o o o 1 o o > 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ů). 1= F(x,y) J=G(x,y) kde (i,j) 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ární 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. * _ * . * . * * _ * . * . . * . . * . . * . . * . . * . . * . * . * . * . * * 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 R.U Algoritmus 16 - Určení skeletu 1. 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ý. 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: Hrana ^ zacma ■ Uzel Uzávěr Vedení Přípojka Odběrné místo \ ^ J } Základní datová struktura areálového grafu: 1. areál Hr. obce Hr. katas 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ž?". - 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 /leH označme w(h). Nechť dále každý uzel i/yell má 2D souřadnice (xhyj). Pro libovolné uzly u,v označme d(u,v) jejich vzdálenost v E2. Pro libovolnou hranu h\=(U\,vi) nechť dále je d(Uj,Vj)