|
36. Fejezet - HIERARCHIKUS ADATSZERKEZETEK
Magyar változat: Végső Ferenc, Erdészeti és Faipari Egyetem, Székesfehérvár
A. BEVEZETÉS
B. A KÉPPONTOK INDEXELÉSE
Eljárás
A helyek dekódolása
C. A NÉGYFA
A négyfa kódolása
Adatelérés a négyfán
Különböző adatszerkezetek összehasonlítása
D. A NÉGYFA VÁLTOZATAI
E. A HIERARCHIKUS ADATSZERKEZETEK ELŐNYEI
IRODALOM
ELLENŐRZŐ KÉRDÉSEK
MEGJEGYZÉSEK
36. Fejezet - HIERARCHIKUS ADATSZERKEZETEK
Magyar változat: Végső Ferenc, Erdészeti és Faipari Egyetem, Székesfehérvár
A. BEVEZETÉS
- az eltérő letapogatási módszerek csak kis különbséget mutatnak az adattömörítésben
- az ok, amiért érdekesek a Morton és egyéb letapogatási sorrendek: a gyorsabb adatelérés
- az információk mennyisége - amely a térképen helyről-helyre erősen változik - a helyi változékonyságtól függ
- ez szükségessé teheti, hogy az információk mennyiségétől függően eltérő raszterméretekkel dolgozzunk
- nagy cellákkal a sima, vagy lassan változó részeken, kis cellákkal a tagolt, vagy gyorsan változó részeken
- sajnos, az egyenlőtlen méretű négyzeteket nem tudjuk illeszteni ("a sík lefedése"), kivéve az egészen szokatlan körülményeket
- ilyen körülmény az, ha kis négyzetek ágyazódnak be nagyobbakba
- következzék néhány adattömörítő módszer, amely kezelni tud változó adatsűrűséget is
B. A KÉPPONTOK INDEXELÉSE
36.1.ábra - raszterből négyfa
- képzeljünk el egy 16x16-os tömböt, amiben csak egy cella tér el a többitől
- megjegyzés: a sorok és oszlopok számozása 0-tól kezdődik (0 - 15)
- páratlan cella van a 4. sor 7. oszlopában
Eljárás:
- kezdetnek osszuk fel a tömböt négy 8x8-as negyedre, és számozzuk meg őket a Morton sorrend szerint 0,1,2,3-as számokkal
- az 1,2, és 3 homogén (mind A)
- a 0-s negyed nem homogén, ezért ezt tovább osztjuk négy 4x4-es negyedre
- ezeket 00, 01, 02, 03 számmal számozzuk, mert részei a 0-s jelű 8x8-as negyednek
- ezek közül a 00, a 01 és 02 homogének, de a 03-ast tovább osztjuk 030, 031, 032, 033-ra
- most már csak a 031 nem homogén, ezért továbbosztjuk 0310, 0311, 0312 és 0313-ra
- amit csináltunk, az a rekurzív felosztás a 4-es szabály szerint és addig folytattuk, amíg:
- a négyzet nem lett homogén
- el nem értük a feloldás legmagasabb szintjét (a pixel méretet)
- ez lehetővé teszi eltérő felbontások kezelését, ahol a felbontás lépcsői rögzítettek
- ez az elv kapcsolódik az adathossz Morton sorrend szerinti kódolásához
- ha a rasztert Morton sorrend szerint kódoltuk, minden homogén négyzetnek ismerjük a hosszát
- a 8x8-as négyzetek hossza 64, a 4x4-eseké 16, stb.
- az adathossz szerint kódolt Morton sorrend az alábbi lesz:
16A 16A 16A 4A 1A 1B 1A 1A 4A 4A 64A 64A 64A
- ha megengedjük az adathosszak folytatódását a blokkok között, a fentieket tovább redukálhatjuk:
53A 1B 202A
- vagyis a 2mx2m-es homogén pixelblokk megfelel a Morton kódolásban 22m hosszú pixelnek
A helyek dekódolása
- a sor-és oszlopszámmá visszaalakítás hasonló, mint a Morton számok dekódolása, kivéve, hogy itt a kód mindig a 4-es számrendszeren alapul
- ebben a példában a magányos B pixel kódja 0311
1. alakítsuk át a kódot 2-es alapra
- megj.: minden 4-es alapú szám 2-es alapon két számot ad
- így a 0311-ből 00110101 lesz
2. válasszuk szét a biteket, hogy megkapjuk:
- a sort 0100 = 4
- az oszlopot 0111 = 7
- tehát a számozási rendszer megegyezik a blokkok Morton számozásával 4-es alapon kifejezve
- ugyanakkor, a sorrend és az adattömörítés nem a leghasznosabb oldala ennek az eljárásnak
C. A NÉGYFA
- a fenti felosztást elképzelhetjük úgy is, mint egy fát
- a teteje a szóbanforgó tömb
- minden szintjén négyfelé ágazik
- minden elágazás véget ér egy homogén blokknál
- a négyfa elnevezést használjuk, mert a 4 alapú felosztást használjuk
36.2. ábra - a négyfa
- minden lezárt elágazást a fán (amelyhez érték tartozik) levélnek nevezünk
- ebben az esetben 13 levél, illetve homogén négyzetes blokk van
A négyfa kódolása
- a négyfa memóriában való tárolásához el kell dönteni, hogy mit akarunk tárolni a memóriarekeszekben
- sok módszer van a négyfa tárolására, de mindegyiknek ugyanaz az alapfilozófiája
- egy módszer, hogy minden memória helyen tároljuk az alábbiak VALAMELYIKÉT:
1. a blokk értékét (pl. A vagy B), vagy
2. az egy szinttel lejjeb lévő négy "gyermek" blokk első blokkjának mutatóját
- mind a négy "gyermek" blokk megjelenhet később, mint "szülő"
36.3. ábra - a négyfa kódolása
- tehát a négyfát így tárolhatjuk a memóriában:
Pozíció: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Tartalom: 2 6 A A A A A A 10 A 14 A A A B A A
(szint): 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4
- az egyes pozícióban 1 van, ami azt jelzi, hogy a térkép tovább oszlik négy blokkra, amelyek tartalma a 2. pozícióban kezdődik
- a 2 pozíció azt jelzi, hogy a 0-s blokk négy részét a 6. pozíciótól kezdve találhatjuk meg
- a 3, 4 és 5 pozíció azt jelzi, hogy az 1 blokk másik három szintjének tartalma mind A, és nem oszlik tovább blokkokra
Adatelérés a négyfán
- képzeljünk el két utat, amelyen a négyfát be akarjuk járni
- meg akarjuk találni az azonos értéket tartalmazó helyeket
- meg akarjuk határozni egy adott pixel értékét
- megjegyzés: ha a tömbben 2nx2n db pixel van,- akkor a fának n db lehetséges szintje van, vagy n+1, ha a felső szinttel is számolunk (0-s szint)
- használjuk az m-t a levelek számozására
1. a térkép adott értékkel rendelkező részeinek megtalálásához meg kell vizsgálnunk minden levelet, hogy a keresett értéket tartalmazza-e
- ez m lépést kíván, mivel m db levél van
2. az adott tartalmú pixel megtalálásához el kell indulnunk a fa tetejéről
- ha a térkép homogén, megállunk, mert minden további pixel értékét ismerjük
- ha nem, követnünk kell az elágazást a következő pixel felé
- hogyan tudjuk meg, hogy melyik elágazás következik?
- vegyük a sor és oszlopszámokat, alakítsuk binárissá, fűzzük össze a biteket és konvertáljuk 4-es alapra
- pl. a 4 sor és 7 oszlop lesz a 0311
- minden szinten használjuk a megfelelő számjegyet a következő elágazás megállapításához
- pl. a 0311-nél a 0-s szinten a következő elágazás 0, az 1-es szinten a következő elágazás a 3, stb.
- egy rosszabb esetben n szinten kell átmenni a pixel tartalmának megtalálásához, vagyis a lépések száma n lesz
Különböző adatszerkezetek összehasonlítása
- összegezzük a kétféle kereséshez szükséges munkát:
módszer adott értékű részek adott tartalmú
megtalálása pixel keresése
négyfa m n
sorról-sorra 22n (a) 1 (b)
sorról-sorra
hosszkódolással m (c) m (d)
Morton
hosszkódolással m (c) m (d)
megjegyzés:
(a) inden pixelt meg kell vizsgálni a tömbben
(b) ki tudjuk számítani minden pixel pozícióját és közvetlenül el tudjuk érni
(c) a futások száma közelítőleg egyenlő a levelek számával
- bár a módszerek különböznek, korábban megállapítottuk, hogy az egyes módszerek nem adnak nagy eltérést az adathosszakban
(d) minden futásnál vizsgálatot kell végezni, hogy van-e pixel
- tehát a négyfa határozott előnyt mutat a keresésben a többi módszerrel szemben
D. A NÉGYFA VÁLTOZATAI
- nyolcfa a három dimenziós változata a négyfának, és a 8-as számrendszeren alapul
- a kockát rekurzív módon nyolc részre osztjuk
- a nyolcfa nagyon hasznos a három dimenziós adatok esetén, mint pl. a bányászatban, geológiában, orvosi fényképezésben
- l. a 42. Fejezetet a témában
- a globális adatok ábrázolása nagy problémákat okozhat
- alkalmazhatunk egy vetítést, mint a Mercator, és az adatokat ábrázolhatjuk raszterként ezen a vetületen
- a pixelek által képviselt területek és formák nagy torzulást szenvedhetnek, különösen a sarkok közelében
- a szomszédos pixelek kapcsolatai is eltorzulnak
- a valóságban a felső és alsó sorok pixelei szomszédai egymásnak az egész sarkvidéken
- ezek a problémák az ilyen adatokon alapuló modelleket eltorzítják
- sokkal jobb megközelítést talált ki Geoffrey Dutton az alábbiak szerint:
36.4. ábra - a globális háromszögelési mozaik
- vetítsük a földgömböt nyolclapú testre, amely nyolc háromszögből áll (tetraéder)
- a nyolclapú test élei a sarkoknál találkoznak, és 90 fokot zárnak be az egyenlítőnél
- számozzuk meg a lapokat 0-tól 7-ig
- az élek középpontjainak összekötésével osszunk tovább minden lapot további négy háromszögre
- számozzuk be őket: a középső 0, a fölötte vagy alatta lévő 1, átlósan balra 2, átlósan jobbra 3
- ennek a mintának a 20. szintjén a háromszögek éle 1m-es, a Föld felszínén számolva
- egy ilyen hely címe egy 8-as alapú szám és 20 4-es alapú szám, vagy 43 bináris szám
E. A HIERARCHIKUS ADATSZERKEZETEK ELŐNYEI
- minden koordináta egyszerűen címezhető
- egy szám jelzi a síkbeli helyzetet
- a földfelszín minden négyzetméterének van egy egyértelmű 21 jegyű címe
- a felbontást automatikusan tükrözi a cím hossza
- a fent leírt globális mintában egy 21 jegyű szám 1 m-es felbontást jelez, az 1 km-es felbontáshoz elegendő 13 jegy
- összehasonlításképpen, a szélesség-hosszúság koordinátához két számjegy kell, de a számokból nemigen lehet megállapítani a felbontást
IRODALOM
Gargantini, I., 1982. "An effective way to represent Quadtrees," Communications of the ACM 25:905-910
Mark, D. M., J. P. Lauzon and J. A. Cebrian 1989. "A review of quad-tree based strategies for interfacing
coverage data with digital models in grid form," International Journal of Geographical Information Systems 3(1):3-14.
Samet, Hanan, 1984. "The quadtree and related hierarchical data structures," ACM Computer Surveys
16(2):187-260
Samet, Hanan, 1989. "The Design and Analysis of Spatial Data Structures," Addison-Wesley, Reading, MA.
Kiváló áttekintés a négyfákról
Samet, Hanan, 1989. "Applications of Spatial Data Structures," Addison-Wesley, Reading, MA. Kiváló
áttekintés a négyfák alkalmazásáról
Shaffer, C.A., H. Samet and R.C. Nelson, 1990. "QUILT: a geographic information system based on
quadtrees," International Journal of Geographical Information Systems 4(2):103-32
Waugh, Thomas C., 1986. "A response to recent papers and articles on the use of quadtrees for geographic
information systems," Proceedings, Second IGU Symposium, Seattle, pp. 33-37. A négyfák izgalmas kritikája.
ELLENŐRZŐ KÉRDÉSEK
1. " A hierarchikus adatszerkezetek elve egyike a GIS kutatásból származó néhány zseniális elgondolásnak". Beszéljük meg.
2. Beszélgessünk azokról az érvekről, amelyeket Waugh (1986) hoz fel a négyfák ellen és mellett.
3. Összegezzük a pro- és kontra érveket a jelen fejezetben kifejtett nyolclapú felbontásról, összefüggésben a globális adatbázisok vizsgálatával.
4. Módosítsuk a négyfa elvet, hogy megfelelő legyen a magasságok digitális ábrázolására. Mik az előnyei és hátrányai ennek a megközelítésnek az egyszerű raszterrel szemben?
5. Mik lehetnének az előnyei és hátrányai Dutton módszerének a földfelszín helyeinek azonosításában, szembeállítva a postacímmel?
6. A háromdimenziós adatbázisoknak nagy szerepe van a geológiában, geofizikában, felszín alatti vizek esetén, a meteorológiában, az óceánográfiában és az ásvány-gáz-olajbányászatban. Egy vagy több témáról beszélgetve, tárgyaljuk meg a nyolcfa adatmodellként való alkalmazhatóságát.
|
