Térinformatikai adatszerkezetek

Speciális algoritmusok

Esszé

Szentkirályi Károly

Térinformatikai adatszerkezetek Bevezetés A térinformatika célja, hogy grafikus, térképi formához kötve mutasson be gazdasági, társadalmi, politikai és egyéb adatokat, elősegítve ezzel az adott terület problémáinak megoldását, feladatainak, eredményeinek bemutatását. Feladata, hogy a földrajzi helyhez kötött adatokat számítógépen tárolja, megjelenítse, analizálja. Ezeknek a feladatoknak a végrehajtása az erre a célra kifejlesztett számítógépi programrendszerben történik, amelyet általános néven térinformatikai rendszernek nevezünk. A köztudatban a térinformatikai rendszerekre meghonosodott a GIS rövidítés, amely az angol Geographical Information System (azaz Földrajzi Információs Rendszer) kifejezésből származik.

Adatok a térinformatikában Vektoros adatmodell A

grafikai

adatokat

formátumban

tároljuk.

vektoros A

és

vektoros

raszteres adatmodell

lényege, hogy az objektumokat alkotó pontok (például

a

egyedülálló

vonalak pontok

csomópontjai) (például

egy

illetve kút

az vagy

villanyoszlop) helyét koordinátákkal írjuk le. Ezzel együtt meg kell adni, milyen irányban vagy sorrendben kötjük össze ezeket a pontokat. Ebből kiindulva

az

(ponttól)

egészen

(poligonok),

egyszerű illetve

a

geometriai

alakzatoktól

bonyolultabb

objektumok

egymás

közti

kapcsolatuk A vektoros adatmodell egyszerűsített alapelve

részletes leírásáig juthatunk el.

1


Esszé


Raszteres adatmodell A

raszteres

adatmodell

alapvető,

kisebb

részekre oszthatatlan elemét egy angol eredetű szóval nevezzük: ez a pixel, amely az angol "picture element" szavakból ered. Magát a modellt úgy kell elképzelnünk, hogy a kiválasztott területet egy óriási négyzethálóval

A raszteres adatmodell egyszerűsített alapelve

fedjük. Egy tereptárgy több kisnégyzetből (pixelból) állhat, ezeket a pixeleket színkódok különböztetik a környezetén levő pixelektől. Ezt az adatmodellt elsősorban a légi és műholdfelvételek

digitális

formátumának

tekinthetjük.

Pixelek egy űrfelvétel nagyított részletén

Fedvények a térképen A digitális térképek fedvényekből (más néven rétegekből) állnak. Ezeket a fedvényeket úgy kell

elképzelnünk,

mintha

egymásra

tett

átlátszó fóliák lennének. Mindegyik fóliára az adott térkép egy-egy elemét rajzoljuk: vízrajz, domborzat,

települések,

úthálózat,

művelt

területek, ipari létesítmények stb. Ezek a fedvények alkotják a digitális alaptérképet. A kidolgozandó tematikától függően ki- vagy bekapcsolhatjuk az alaptérkép fedvényeit. Ilyen módon

csak

szükséges képernyőn,

az

aktuális

információkat és

egyetlen

feladatunkhoz jelenítjük

a

alaptérképből

különböző, egyszerűsített alaptérképet tudunk

2

A fedvények alapelvét ábrázoló vázlat


Esszé


létrehozni. A tematikus információk is különkülön fedvényre kerülnek: ezeket szintén szükség szerint be- és kikapcsolhatjuk. Így egyetlen egy alaptérképpel több tematikus térkepet tudunk készíteni.

Térinformatika és adatbázisok A

térinformatika

működése

adatbáziskezelésen

alapul.

adatok

gyűjteménye,

rendezett

adatokat

Az

az

adatbázisok ezeket

táblázatokban

az

tároljuk.

Leegyszerűsítve, vektoros modell esetén az "ábrázolandó"

terület

(tereptárgyainak)

a

fontosabb

pontjainak

jellemzői,

raszteres

modellben az egyes pixelek az adatbázis soraiban

tárolódnak:

rekordoknak

ezeket

nevezzük.

szakszóval

Az

adatbázis

oszlopaiban találjuk a mezőket, amelyekben tároljuk az egyes rekordok jellemzőit. A rekordokat egy (vagy több) mező alapján rendezhetjük, például abc sorrendben vagy növekvő kiválasztott

mértékben. közös

Az

Vázlat egy adattáblázat szerkezetéről

adatbázisokat

mezőkkel

lehet

összekapcsolni, ezeket kulcsmezőknek szokás nevezni.

3


Esszé


Geokódolás

A térinformatikában az adatbázisokban levő objektumokhoz (rekordokhoz) koordinátakat kell rendelnünk. Enélkül nem tudjuk őket a térben (a térképen) elhelyezni. Ezt a műveletet geokódolásnak nemcsak

nevezzük.

koordinátákkal

A

geokódolás

történik:

nagy

méretarányok esetén irányító számokkal, postai címekkel is elvégezhető. A térinformatikai szoftverek képesek ezt a műveletet egyetlen egy parancs segítségével végrehajtani. Geokódolási menü a MapInfóban

Adatstruktúrák A tér objektumainak illetve pontjainak szervezésére és tárolására különféle adatstruktúrák állnak rendelkezésünkre. A következő szakaszban ezekről fog majd szó esni. Mindegyik adatszerkezeten különféle műveleteket lehet végrehajtani, a leggyakoribb új pont vagy objektum beszúrása illetve törlésre. Gyakran szeretnénk információkhoz jutni az adott pontról, illetve objektumról, tehát lekérdezéseket kell végrehajtani, a legfőbb lekérdezések: Tartozás, Részleges egyezés (pl. az x koordináták egyezzenek meg stb.), Legközelebbi szomszéd illetve a „Hol vagyok én?”.

Grid Az egyik legegyszerűbb térinformatikai adatszerkezet. Osszuk fel a síkot cellákra pl. egyenlő méretű négyzetekre (vagy a teret kockákra) és a pontokat a megfelelő cellákba soroljuk be, általában hasítással. A következő ábrán egy példa látható a gridre.

4


Esszé


Kd fa (k dimenziós fa) A k-d fa egy bináris fa, amelyben a fa minden pontja egy k-dimenziós pontot reprezentál. Tegyük fel, hogy k=2, vagyis egy síkon szeretnénk a pontjainkat besorolni. Először rendezzük sorba az x koordinátái szerint növekvő sorrendben a pontokat, majd válasszuk ki a rendezésnek megfelelően a középső pontot, ez lesz a gyökér. A rendezésnek megfelelően a ponttól kisebb illetve nagyobb x koordinátájú pontok a gyökér bal illetve jobb oldali részfájába fognak kerülni. A jobb és baloldali részfába kerülő elemeket ugyancsak sorba rendezzük külön-külön, de immár az y koordináták szerint és az elemeket szintén bal és jobboldali részfákba osszuk be. Ezt addig csináljuk, amíg az összes pont nem lesz valamelyik részfa gyökere. Minden szintnek megfelel valamelyik dimenzió (felváltva, valamilyen rendszer szerint a dimenziókat cserélgetve), ami alapján rendezünk. Példa:

5


Esszé


Negyedelőfa pont negyedelőfa A pont negyedelőfa = grid + bináris keresőfa, ami egyfajta fa struktúra, nem egységes méretű cellákkal. Minden pont egy csúcson helyezkedik el, és minden csúcs egy rekordtípus, ami hét mezőt tartalmaz, többek között a gyerekekre mutató pointerek.

régió negyedelőfa A régió negyedelőfa a tér egy részét síkban reprezentálja. A régiót négy negyedbe bontja, majd ezt újra és újra ismétli. A régiókra bontás után minden csúcsnak négy gyereke van, vagy nincs egy sem, ekkor a csúcs egy levél. Egy n mélységű régió negyedelőfa jól használható egy 2n×2n pixel méretű bináris kép esetén, ahol minden pixel 0 vagy 1 értékű. A gyökér fejezi ki a teljes kép régiót. Ha egy régióban a pixelek nem csupán 0-k vagy 1-k, akkor azt a régiót tovább kell bontani, negyedelni, mindaddig, amíg minden régió vagy csak 0-k vagy csak 1-k alkotják

6


Esszé


pont-régió negyedelőfa A pont-régió negyedelőfa tulajdonképpen a régió negyedelőfa egy változata pont adatokra vonatkoztatva. A pont-régió negyedelőfa úgy épül fel, mint a „sima” régió negyedelőfa, csak a különbség annyi, hogy a levél csúcsok üresek lehetnek, vagy tartalmaznak egy adatpontot, és annak koordinátáit. Egy negyedben maximum egy adatpont lehet.

R-fa Az R-fa olyan fa, ahol az egymáshoz közeli objektumokat csoportokba szervezi és a minimális bennfoglaló intervallumával (2 dimenziós térben téglalapjával) reprezentálja. Ha a keresett tartomány nem metsz egy intervallumot, akkor az általa reprezentált csúcsok nem lehetnek benne a tartományban. A következő szinteken az egymáshoz közeli intervallumokat is csoportosítjuk, és így tovább. Ez a csoportosítási rendszer egy olyan fát alakít ki, amiben a szülő csúcsok szigorúan tartalmazzák a gyermek csúcsokat, de a gyermek csúcsoknak nem kell diszjunktaknak lennie. Nehézség az R fákkal kapcsolatban az, hogy úgy egyensúlyozzuk ki őket, hogy a fa levelei nagyjából egyforma mélységben legyenek, és az intervallumok ne tartalmazzanak túl sok üres teret, továbbá ne lógjanak túlságosan össze. Ehhez különféle változatok: R*-fa (Az R* fa egyszerre éri el a csomópontjai között az átfedés minimalizálását és a csomópontok területének csökkentését a gyors keresés érdekében), R+-fa (Nem tartalmaznak egymást átfedő intervallumokat. Ehelyett egy objektum több intervallumba is be lehet szúrva, ha szükséges.)

7


Esszé


Indexek Az indexelés szerepe a hagyományos adattípusú oszlopokkal rendelkező táblák esetén a lekérdezések gyorsabb végrehajtása. A térbeli indexek ugyanezt a célt szolgálják.

R-fa index Ez az indexelés a minimális fedő téglalapokon alapul. A minimális fedő téglalap angolul Minimal Bounding Rectangular, rövidítve MBR, ezért a továbbiakban így hivatkozunk rá. A következő ábrán egy alakzat MBR-jét láthatjuk.

Az indexelés úgy történik, hogy képezzük a geometriai alakzatok MBR-jeit, majd néhány ilyen MBR uniójának az MBR-jét, aztán ezen későbbi MBR-ek MBR-jét és így tovább. Végül egyetlen MBR-t kapunk, amely az összes korábbi MBR-nek az MBR-je. Ezeket az MBR-eket egy fa struktúrában tároljuk oly módon, hogy minden nem levél csomópontban levő MBR a gyerek csomópontjaiban levő MBR-eknek az MBR-je. A levelekben levő MBR-ekhez pedig mutatókat is tárolunk, amelyek azokhoz az alakzatokhoz vezetnek, amelyeknek az adott levél MBR-je. Egy ilyen fa felépítését láthatjuk a következő ábrán.

8


Esszé


Az ábrán 1 és 9 közötti számokkal jelöltük a geometriai alakzatokat. Az 1-es és 2-es alakzat MBR-je az a-val jelölt téglalap, az a és b MBR-ek MBR-je az A-val jelölt téglalap, az A és B MBR-ek MBR-je pedig a gyökér névvel jelölt téglalap, ami egyben az összes alakzat MBR-je.

Nézzük meg milyen előnyei és hátrányai vannak az R-fa indexnek. Az index létrehozása egyszerű, az index nem igényel sok helyet, viszont ha az alakzatainkat nem jól közelítik a téglalapok, mert például azok nagyon torz alakúak, akkor finomabb közelítést ezzel az indexszel nem tudunk elérni. Ha módosul valamelyik alakzatunk alakja, akkor lehet, hogy módosítanunk kell az őt tartalmazó levél MBR-t, majd annak szülőjét, és így tovább, egészen a gyökérig. Ez pedig jelentősen lelassíthatja a módosítások végrehajtását.

Negyedelőfa index Ennek az indexelésnek az alapja az, hogy a teljes területet, ahol az elemeink elhelyezkednek, felbontjuk egyre kisebb részekre (téglalapokra), majd ezekkel a kis részekkel közelítjük az alakzatot. Kiindulásul vegyünk egy olyan téglalapot, amely az összes alakzatunkat lefedi, majd ezt osszuk fel négy részre úgy, hogy mindkét koordinátatengely mentén megrajzoljuk az oldalfelező merőlegeseket. Ekkor 4 azonos méretű téglalapot kapunk. Folytassuk a negyedelő eljárást az előbb elmondottakhoz hasonlóan, a kapott téglalapokat tovább és még tovább negyedelve. Az eljárás során kapott téglalapokat a továbbiakban rasztereknek fogjuk nevezni. Ha minden lépésben az összes téglalapot negyedeljük, akkor azonos méretű rasztereket kapunk, ha egyes lépések során csak bizonyos téglalapokat negyedelünk, akkor lesznek kisebb és nagyobb méretű rasztereink is. Az alakzatok indexelése azt fogja jelenteni, hogy hozzájuk rendeljük azokat a rasztereket, amelyek nem diszjunktak tőlük. Így az alakzat indexbeli raszterei lefedik az alakzatot. Mindezt a következő ábrán is bemutattuk. Az ábrán látható alakzatot 3 nagyobb és 3 kisebb raszter indexeli.

9


Esszé

Források http://lazarus.elte.hu/hun/dolgozo/jesus/terinfo/terinfo.htm Hanan Samet: Hierarchical Spatial Data Structures http://en.wikipedia.org/wiki/Quadtree#The_region_quadtree https://en.wikipedia.org/wiki/R-tree http://people.inf.elte.hu/nikovits/TERINFO/SDO9_index.doc

10


Térinformatikai adatszerkezetek

Recommend Documents