Vissza az előzőleg látogatott oldalra (nem elérhető funkció)Vissza a tananyag kezdőlapjára (P)Ugrás a tananyag előző oldalára (E)Ugrás a tananyag következő oldalára (V)Fogalom megjelenítés (nem elérhető funkció)Fogalmak listája (nem elérhető funkció)Oldal nyomtatása (nem elérhető funkció)Oldaltérkép megtekintése (D)Keresés az oldalon (nem elérhető funkció)Súgó megtekintése (S)

Open source fejlesztő eszközök, elméleti rész / Térbeli indexelés

Tanulási útmutató

Összefoglalás

A térinformatikai adatok gyors megjelenítése, keresése, hasonlóan az alfanumerikus adathoz, indexelés által valósítható meg. Ebben a részben bemutatunk néhány térbeli indexelési eljárást.

Térbeli indexelés

A digitális térképek — úgy a raszteres, mint a vektoros adatmodellt követők — általában nagy erőforrás igényűek. Megjelenítéskor megfeleltetést hozunk létre az adatbázis tartalma és a megjelenítő eszköz között.

A kép (nagyobb változata) külön ablakban is megtekinthető.37. ábra. A viewport és a teljes adatbázis térbeli kiterjedésének viszonya37_viewport_full.png37. ábra. A viewport és a teljes adatbázis térbeli kiterjedésének viszonya

A 37. ábrán a szürke terület az adatbázisunk teljes síkbeli kiterjedését mutatja, míg a fehér terület az ú.n. viewport, amely a megjeleníteni kívánt területet jelzi. A megjelenítés legegyszerűbb módja lenne beolvasni az egész adatrendszert a memóriába, és onnan végezni a kirajzolást. Ez az eljárás több szempontból sem követendő. Egyrészt minek beolvasni olyan területek adatait, amik kívül esnek a viewporton, másrészt a memória mérete sem korlátlan, és célszerű csak a látni kívánt terület adatait betölteni. Komplikálja a helyzetet, hogy a háttértár (diszk), amiről a memóriába való betöltést végezzük, lényegesen lassúbb működésű, mint a memória, ezért célszerű az objektumokat lapokra (pages) osztva csoportosítani, és laponként beolvasni. Egy input/output művelet egy page beolvasását (írását) jelenti. Másfelől viszont a háttértárból való olvasások számát a viewport méretével összefüggően kell megállapítanunk. E két ellentétes szempontnak való megfelelés a térképi adatok indexelése révén lehetséges. Így le tudjuk csökkenteni az objektumok térbeli elhelyezkedését célzó keresések számát.

A viewportba eső objektumok gyors megjelenítéséhez tehát ki kell tudnunk zárni a keresésből a viewporton kívüli területeket. Sajnos a hagyományos adatbázis-kezelőkben megszokott indexelési technikák, mint pl. a B-tree a térbeli indexelésre nem alkalmasak. Ennek a problémának a megoldására valók a térbeli indexelés algoritmusai. Még mielőtt rátérnénk néhány térbeli indexelési algoritmus ismertetésére, ismerkedjünk meg a centroid és a befoglaló négyszög fogalmával.

A centroid egy olyan helyettesítő objektum, egy pont, amely a poligon belsejében van, és alkalmas a poligon térbeli elhelyezkedésének reprezentálására. Konvex poligonok esetében a centroid kézenfekvő definiciója a poligon súlypontja, míg konkáv esetben egy a súlyvonalon lévő belső pont (38. ábra). A befoglaló négyszög az a legkisebb területű négyszög, amely teljes egészében tartalmazza a kérdéses poligont (39. ábra).

Mindkét fogalom a poligonok, polylineok (vonalláncok) helyettesítésére való. Azért használjuk őket, mert a térbeli indexeléskor ezen egyszerű objektumokkal reprezentáljuk az időnként rendkívüli összetettségű poligon és polyline objektumokat.

A térbeli adatok indexelési módszerei vagy a térbeli objektumokat, vagy pedig a vizsgált térrészt osztják fel partíciókra. A következőkben bemutatandó módszerek (grid index, quad-tree) a második kategóriába sorolhatók, tehát a tér valamely felosztásával próbálják gyorsítani az objektumok elérését, míg az utolsóként bemutatandó eljárás, az R-tree, egy adat vezérelt szerkezet.

A Grid index

Osszuk fel a síkbeli objektumainkat tartalmazó síkot szabályos négyzethálóra, ahogy a 40. ábrán látható.

A kép (nagyobb változata) külön ablakban is megtekinthető.40. ábra. Különböző méretű objektumok egy adott rácsállandójú négyzethálón 40_grid1_full.png40. ábra. Különböző méretű objektumok egy adott rácsállandójú négyzethálón

Az objektumok gyors megkeresésének első művelete az úgynevezett első szűrés, amikor — kihasználva, hogy a koordinátákra tett feltételekből gyorsan meghatározhatók a szóba jöhető gridek, valamint hogy a grid index a grid azonosítója szerint rendezett és gyorsan kereshető — jelölteket állítunk a lekérdezés feltételeit kielégítő objektumok halmazára. Az index objektumazonosítói segítségével beolvassuk ezt a jelölthalmazt, ami a teljes adatbázisnál várhatóan jóval kevesebb objektumot tartalmaz (41. ábra). A második szűrés dolgozza fel az így megtalált objektum részletes geometriáját (pl. poligonok esetén a vertex koordináták beolvasása és megjelenítése itt történik).

A kép (nagyobb változata) külön ablakban is megtekinthető.41. ábra. Az indexelt tábla és kapcsolata az eredeti táblával41_grid_full.png41. ábra. Az indexelt tábla és kapcsolata az eredeti táblával

méretével. Ha túl nagy a grid, akkor túl sok objektum esik egy adott cellába, ami szélsőséges esetben nem gyorsít a keresésen. Ha túl kicsi a grid, akkor a nagyobb objektumok túl sok gridet fednek le, ami szintén nem előnyös. Az eljárás valamelyest javítható több, eltérő rácsállandójú grid-szint bevezetésével.

A grid index egyszerű és hatékony módja a térbeli indexelésnek. Számos kereskedelmi szoftver alkalmazza is, annak ellenére, hogy hiányosságai nyilvánvalóak, különösen olyan esetekben, amikor az objektumok térbeli eloszlása nem egyenletes. Az volna ugyanis a kívánatos, hogy lehetőleg minden cellába azonos számú objektum essen, ami az állandó rácsméret miatt gyakorlatilag nem lehetséges. Inhomogén térbeli adateloszlás esetén a második szűrési fázis hatékonysága erősen lecsökkenhet, ezért jobb tulajdonságú indexelési algoritmusok szükségesek. Homogén térbeli adateloszlás esetén, mint amilyenek a raszteres adatszerkezetek, hatékony eszköz lehet a grid index is, bár a soron következő eljárás, a quadtree, sokkal hatékonyabb és elterjedtebb.

Vissza a tartalomjegyzékhez

Új Széchenyi terv
A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszirozásával valósul meg.

A Társadalominformatika: moduláris tananyagok, interdiszciplináris tartalom- és tudásmenedzsment rendszerek fejlesztése az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával, az ELTE TÁMOP 4.1.2.A/1-11/1-2011-0056 projekt keretében valósult meg.
A tananyag elkészítéséhez az ELTESCORM keretrendszert használtuk.