|
37. Fejezet - A NÉGYFA ALGORITMUSOK ÉS A TÉRBELI INDEXELÉS
Magyar változat: Végső Ferenc, Erdészeti és Faipari Egyetem, Székesfehérvár
A. BEVEZETÉS
Meghatározások
B. TERÜLETSZÁMÍTÁSI ALGORITMUSOK
Eljárás
Példa
C. FEDVÉNY ALGORITMUSOK
Eljárás
Eredmény
D. SZOMSZÉDSÁGI ALGORITMUSOK
A feladat
Meghatározás
Két eset
Mozaik módszer
Szomszédság meghatározása
A közös határ hossza
E. AZ ÖSSZEFÜGGŐ FOLTOK TERÜLETÉNEK ALGORITMUSA
A feladat
Módszer
Műveletek
Eredmények
F. NÉGYFA INDEXEK
Indexelés a négyfák segítségével
Az index meghatározása
Az index használata
Általánosítások
G. R-FA INDEXEK
Módszer
Probléma
IRODALOM
ELLENŐRZŐ KÉRDÉSEK
MEGJEGYZÉSEK
Ez a fejezet nagyon hosszú, és sok összetett műveletet ismertet. A hallgatók képességeitől és érdeklődésétől függően elhagyhatjuk a harmadik és a negyedik módszert vagy kiadhatjuk külön, mint sokszorosított anyagot.
A képzettebb hallgatókkal alkalmat lehet találni a fejlettebb algoritmusok összetettségének, finomságainak tanulmányozására. Az indexelésről szóló későbbi részek függetlenek a korábban ismertetett anyagoktól.
37. Fejezet - A NÉGYFA ALGORITMUSOK ÉS A TÉRBELI INDEXELÉS
Magyar változat: Végső Ferenc, Erdészeti és Faipari Egyetem, Székesfehérvár
A. BEVEZETÉS
- az előző fejezet ismertette a négyfa alapgondolatát
- ebben a fejezetben megvizsgáljuk, hogyan alkalmazhatjuk a négyfát egyszerű feladatok esetén, úgymint:
- területszámítás
- fedvényműveletek
- levelek szomszédságának megállapítása
- összefüggő foltok területének számítása
- ráadásul, ebben a fejezetben megnézzük, hogy a négyfák hogyan alkalmazhatók indexelésre a vektoros objektumok gyorsabb elérése céljából
- végül áttekintjük a térbeli indexelés egyéb formáit
Meghatározás
- mozgás a négyfán:
- elindulunk a gráf bal szélső ágán az első levél felé
- miután feldolgoztunk minden levelet ezen az ágon, visszalépünk az előző elágazásra és elindulunk a jobboldali ágon
- ez vagy elvezet minket egy lejjebb fekvő levélhez, vagy visszatérünk az előző elágazási pontra
37.1. ábra - első térkép
- a további példák némelyike ugyanezen az egyszerű raszteren és a hozzátartozó négyfán alapul
B. TERÜLETSZÁMÍTÁSI ALGORITMUS
Eljárás
- a térkép A jelű területének kiszámításához:
- mozogjunk a négyfán és adjuk össze az A jelű leveleket, a területeket aszerint súlyozva, hogy a levél hányadik szinten van
- a minta-négyfán a 0 szinten lévő elemek területe 16, az 1-es szinten lévőké 4, a 2-es szinten lévőké 1
- ezért az A területe
1(00. levél)+1(02. levél)+1(03. levél)+4(2. levél)+1(32. levél)
azaz 8 egység
C. FEDVÉNY ALGORITMUS
37.2. ábra - második térkép
- megj.: ezt a fóliát ténylegesen is az első fölé tehetjük
Eljárás
- a két térkép fedésbe hozásához:
- mozogjunk a fákon egyszerre, követve minden ágat, amely valamelyik fán a kettő közül van
- ha az egyik fán hiányzik az elágazás (levél van ott, ahol a másik fán elágazások), rendeljük hozzá a levél értékét minden elágazáshoz
- pl. a 3 pont elágazik az első térképen, a másodikon nem
- az ehhez a ponthoz tartozó levelek (30, 31, 32 és 33) értékei B, B, A és B az első térképen, mindegyik 2 a második térképen
- új fa keletkezik, aminek az értékei mindkét térkép értékeit fölveszik, pl. A1, B2
Eredmény
37.3. ábra - első térkép + második térkép
D. SZOMSZÉDSÁGI ALGORITMUS
A feladat
- felismerni, hogy két levél (pl. a 03 és a 2) szomszédos
Következmény: felismerni egy adott levél (pl. 03) szomszédait
- megjegyezzük, hogy a vonal alapú rendszerekben a szomszédságot az adatszerkezetben tároljuk (Jobboldali és Baloldali szomszédok), ezért ezek a műveletek egyszerűbbek a vektoros rendszerekben
Meghatározás
- itt a szomszédságot a közös él (oldal) jelenti, nem csak a közös pont
Két eset lehet
- a levelek kódja:
1. egyforma hosszú (azonos méretűek, pl. 01 és 02) vagy
2. az egyik hosszabb mint a másik (eltérő hosszúak pl. 03 és 2)
- a probléma megoldásához:
1. átszámítunk a 4-es rendszerből binárissá és vissza
- mert a négyfa létrehozásához a "négyes szabályt" alkalmaztuk
2. alkalmazzuk a bitek összefűzését
3. új alapelvet használunk, amit mozaik műveletnek nevezünk
Mozaik módszer
- a mozaik módszer egy lehetséges megoldás, amit a négyfa címzés sajátosságainak kezelésére használhatunk
- bináris számok szokásos összeadásánál a "mutató" egy hellyel balra mozdul
- pl. 0001-hez 1-et adva 0010-t kapunk
- ez ugyanaz, mint a tizes számrendszerben, kivéve, hogy az elmozdulás nem tízre, hanem már kettőre bekövetkezik
- a mozaik módszernél a "mutató" két pozícióval kerül balra
- pl. ha 0001-hez adunk 1-et, az eredmény 0100 lesz
- kivonáskor megfordul a helyzet
- 1000-ból 1-et, az eredmény 0010, nem pedig 0111, mivel a kivonás csak minden második bitet változtatja meg
- más szóval, ha megszámozzuk a biteket balról eggyel kezdődően,
- egy hozzáadása vagy kivonása csak a páros biteket változtatja
- kettő (bináris 10) hozzáadása vagy kivonása a páratlan biteket változtatja
Szomszédság meghatározása
37.1. melléklet - szomszédság meghatározása
1. azonos méretű blokkok:
- két levél szomszédos, ha bináris megfelelőik bináris 1-el vagy bináris 10-el különböznek (decimális 1 vagy 2) a mozaik aritmetikában
- példa: 01 és 03 szomszédos, mert a 0001 és 0011 bináris 10-el, illetve decimális 2-vel különböznek
- példa: 033 és 211 szomszédos, mert a mozaik módszerben 001111 + 10 = 100101, vagy 100101 - 10 = 001111
2. eltérő méretű blokkok:
- vegyük a két kód közül a hosszabbikat
- alakítsuk át négyes rendszerből binárissá
- a mozaik elv szerint adjunk hozzá és vonjunk ki 01-et és 10-et, hogy négy új kódot kapjunk
- hagyjuk figyelmen kívül azokat az eseteket, amikor a kivonás nem volt lehetséges ( "negatív" kódot kapnánk, vagy a "mutató" a balra esne a balszélső bithez képest)
- hagyjuk el a hosszabb transzformált kódok jobboldali számjegyeit
- alakítsuk vissza négyes számrendszerbe, hogy levelet kapjunk
- a két blokk szomszédos, ha az átalakított és levágott kódok bármelyike megegyezik a legrövidebb kóddal
- példa: 02 és 2 szomszédos-e ?
- alakítsuk a 02-t binárissá = 0010
0010 + 1 = 0011
0010+ 10 = 1000
0010 - 1 = (lehetetlen)
0010- 10 = 0000
- az elhagyás után marad 00 és 10
- ezek a négyes alapon 0 és 2
- ezért 02 és 2 szomszédosak ( 02 és 0 szintén szomszédos)
- példa: 033 és 2 szomszédos-e ?
- alakítsuk a 033-at binárissá = 001111
001111 + 1 = 011010
001111+ 10 = 100101
001111 - 1 = 001110
001111- 10 = 001101
- két számjegyet levágva kapjuk: 01, 10 és 00
- ezek négyes alapon: 1, 2 és 0
- ezért a 033 és a 2 szomszédosak
- példa: a fent bemutatott első térképen keressük meg a 03 szomszédait
- módszer: keressük meg az azonos hosszúságú szomszédos blokkok kódjait, majd mozogjunk lefelé a fán, hogy a megfelelő leveleket megtaláljuk
- (megjegyzés: csak egyforma vagy rövidebb kódokat tudjuk megkeresni - egyforma vagy nagyobb levélblokkokat)
0011 + 1 0110 12: 1 levél
0011+ 10 1001 21: 2 levél
0011 - 1 0010 02: 02 levél
0011- 10 0001 01: 01 levél
A közös határ hossza
- két blokk közös határának hosszát a hosszabbik kód szintje határozza meg
- ezt felhasználhatjuk olyan művelet definiálására, amely alkalmas a folt kerületének meghatározására
- pl. az A\B határának hossza az első példatérképen
E. A ÖSSZEFÜGGŐ FOLTOK TERÜLETÉNEK MEGHATÁROZÁSA
Feladat
- határozzuk meg az azonos értékkel rendelkező összefüggő foltok területét, pl. minden A jelűét
Következmény: Hány elkülönülő A jelű folt található ?
- megjegyzés: ez egy általános eljárás, amit egyaránt alkalmazhatunk raszteres és vektoros adatszerkezet esetén
- azaz keressük meg az összetartozó blokkok, vagy szabálytalan alakú poligonok csoportját, amelyek szomszédságát ismerjük, vagy meg tudjuk határozni
- az alábbi példában az eredeti rasztertérképet használjuk
- megjegyezzük, hogy ezen csak két összefüggő folt van; az A és B típusú területekből egyaránt egy van
Módszer
37.2. melléklet - az összefüggő foltok területe
- a fán mozogva készítsük el a levelek listáját a kódjaikkal együtt
- hagyjunk helyet egy "mutató" számára minden levélhez, és adjuk mindnek a 0 kezdeti értéket (l. másolat)
Algoritmus
- minden i jelű levélre:
- keressük meg a j jelű szomszédos leveleket, amelyek azonos hosszúságú vagy rövidebb kóddal rendelkeznek (maximum 4)
- ha a szomszédos j levélnek azonos az értéke, határozzuk meg, hogy az i vagy j levélnek van-e magasabb (nagyobb értékű) pozíciója a listán, és állítsuk a mutatóját alacsonyabb értékre
- (megjegyzés: ha a mutatót már változtattuk, tovább változtathatjuk, vagy hagyhatjuk utolsó értékén, az eredmény ugyanaz lesz)
- így létrehoztuk a végleges mutató listát
Eredmények
1. a szomszédos foltok számai nullával lesznek egyenlők
- a példában két mutató nulla, jelezve, hogy a két folt szomszédos
2. minden folt értékét meghatározhatjuk, ha elérjük azokat a leveleket, amelyek mutatója nulla
- a példában a 00 és 01 levél mutatója 0
- ezek értéke egyenként A és B
3. a foltok területének meghatározásához válasszuk ki a nullákat és adjuk össze a területüket, valamint adjuk hozzá mindazon levelek területét, amelyekre közvetlenül vagy közvetve rámutat
- a foltot összetevő leveleket megtalálhatjuk, ha elindulunk a lista végén (vagy az elején) és követjük a mutatót, amíg nullát nem találunk
- pl. a 10. helyen lévő levél (33-as kódú) a 8-ra mutat, amelyik a 7-re mutat, amelyik az 5-re mutat, amelyik a 2-re mutat, amelynek nulla a mutatója
- ezért, a 10-es pozíciójú levél (33-as kód) része ugyanannak a foltnak, mint a 2-es (01-es kód) és az értéke B
- a területet a levelek területének összeadásával kaphatjuk
- a példában:
"A" levelek: 00 02 03 2 32
"A" pozíciók: 1 3 4 6 9
"A" területe: 1 + 1 + 1 + 4 + 1 = 8
"B" levelek: 01 1 30 31 33
"B" pozíciók: 2 5 7 8 10
"B" területe: 1 + 4 + 1 + 1 + 1 = 8
F. NÉGYFA INDEXEK
Indexelés a négyfák segítségével
- az indexelést vektoros rendszerekben használjuk a térkép egyes részein lévő objektumok gyorsabb elérésére
- nagyon hasznos a lehetséges átfedő, vagy kizáró területek megtalálásához
- ezért az indexek alapvető részei a poligonok fedvényműveleteinek
- a 34. Fejezetben láthattuk az egy tengely (pl. az X) mentén végzett sorbarendezés hasznosságát a mozgó sáv módszernél, amikor kizáró objektumokat keresünk
- most olyan módszert nézünk meg, amely mindkét tengely irányában egyidejűleg tud rendezni
- ehhez kétdimenziós kódrendszert és egyszerű egydimenziós rendezést használnak
Az index meghatározása
37.4. ábra - a négyfa indexek
- a lépések:
1. az adatbázis minden objektuma (pont, vonal, terület) számára keressük meg azt a legkisebb levelet, amely tartalmazza a kérdéses objektumot
- sok nagy objektum a NULL kódot kapja, mert túlnyúlik az első elágazás négy levelén is (0, 1, 2 és 3)
- más, kis objektumok teljesen beleesnek egy kis levélbe, pl. a 031
2. rendezzük, vagy indexeljük az objektumokat a négyfa befoglaló levelei szerint
Az index használata
- ahhoz, hogy megtaláljunk minden olyan objektumot, amely keresztez egy minket érdeklő pontot, vonalat vagy területet:
- keressük meg a négyfa azon levelét, amely tartalmazza a kérdéses objektumot
- ennél a pontnál kezdve kövessük a fa ágait fölfelé minden olyan elágazáson keresztül, amely tartalmazza az eredeti cellát és mozogjunk lefelé azokon a csomópontokon és leveleken, amelyek a cella alatt helyezkednek el
- példa: a keresett terület az eredeti példában a 31-es levélben van
37.1. ábra - Első térkép
- azok az objektumok, amelyek a kérdéses területet metszhetik, a 31-es cellában vannak, vagy minden fölötte lévő levélben
- tehát ezek a 3-as vagy a nullás levelek
- a többi levélben lévő objektumok (a távoliak) nem metszhetik a kérdéses területet, tehát vizsgálni sem kell őket
- példa: a kérdéses terület a 0 levélben van
- azok az objektumok, amelyek metszhetik a 0-s levélben lévő területet, maga a nullás levél, és minden levél a 0 alatt, úgymint 00, 01, 02, 03
- itt szerepelhetnek egyéb, ezek alatti levelek, mint a 010, 011, 012, 013 stb.
Általánosítások
- a négyfa indexelés hatékonyabb kis objektumokra, önálló pontokra
- a nagy objektumok nagyobb befoglaló leveleket kívánnak, ráadásul nem töltik ki a terület nagyobb részét (pl. főutak nyomvonalai)
- ezeket az objektumokat mindig ellenőrizni kell metszés szempontjából
- ilyen esetben szükséges lehet feldarabolni az objektumot, hogy a részei teljesen beleessenek kisebb levelekbe
- az ilyen módon való indexelés sokkal hatékonyabb, mint az X és Y irányban külön-külön, mivel a négyfa index eredendően kétdimenziós
- a felosztásnak az elágazások mentén nem kell feltétlenül egyformának lenni
- használhatunk más blokkokat a kisebb területekhez és más blokkokat a nagyobb területekhez, mintsem négy egyforma négyzetet használnánk minden elágazásnál
- mindazonáltal a leggazdaságosabb blokkok a négyzetesek
G. R-FA INDEXEK
- az R-fa indexek a nagy területek indexelésének problémáját oldják meg
- az "R" terjedelmet (Range) jelent, az elv hasonló a MER-hez
Módszer
37.5. ábra - az R-fa
- határozzunk meg, lehetőleg átfedő, az X és Y tengellyel párhuzamos oldalú négyzetet, amelyre igaz:
- a lehetséges legtöbb objektum teljesen essen bele egyik vagy másik négyzetbe
- durván egyenlő számú objektum legyen minden négyzetben
- a négyzetek közötti átfedés minimális legyen
- az indexelést az a négyzet határozza meg, amelyik tartalmazza az objektumot
- azok az objektumok, amelyek teljesen beleesnek a négyzetbe, a négyzethez tartoznak
- azok az objektumok, amelyek nem esnek bele teljesen egyik négyzetbe sem, az osztatlan (eredeti) térképhez tartoznak
- alkalmazzuk az eljárást ismételten, két kisebb négyzetet meghatározva mindegyik meglévő négyzeten belül
- így létrejön egy fa struktúra, hasonlatosan a négyfához
- minden objektum a fa néhány csomópontjához lesz rendelve
- ahhoz, hogy megtaláljuk azokat az objektumokat, amelyek metszik a kérdéses területet:
- keressük meg az indexelési eljárás alkalmazásával azt a legkisebb négyzetet, amely teljesen tartalmazza a kérdéses objektumot
- a metsző területek tartozhatnak ehhez a négyzethez, és minden csomóponthoz, amely e fölött vagy alatt van a fán
Probléma
- bár a sebességi tesztek azt mutatják, hogy az R-fák általában sokkal hatékonyabbak, mint a négyfák, vagy az egyszerű egydimenziós rendezések, létrehozásuk számításigényesebb
IRODALOM
Buchmann, A., O. Gunther, T. R. Smith and Y.-F. Wang. "Design and Implementation of Large Spatial
Databases", Unit Notes in Computer Science 409, Springer Verlag, Berlin. A térbeli adatindexelésről tartalmaz fejezeteket
Guttman, A., and J.P. Lauzon, 1984. "Linear quadtrees for Geographic Information Systems," Proceedings,
International Symposium on Spatial Data Handling, Zurich, 2:412-430
Noronha V., 1988. "A Survey of Hierarchical Partitioning Methods for Vector Images," Proceedings, Third
International Symposium on Spatial Data Handling, Sydney, Australia, pp. 185-199.
Oosterom, P. van, 1990. "A modified binary space partitioning tree for geographic information systems,"
International Journal of Geographical Information Systems 4(2):133-46
A 36. Fejezet irodalomjegyzékében szereplő két Samet-könyv hasznos részeket tartalmaz a négyfával kapcsolatban.
Pataki, F. and Csernák, G. 1993. "New, fast and simple quadtree structure for vector GIS databases: the topologic quadtree", EGIS'93 Vol. 1. p. 213-216.
ELLENŐRZŐ KÉRDÉSEK
1. Hasonlítsuk össze az indexelés elvi megoldásait (négyfa, R-fa, 1D rendezés) a gyakorlatban alkalmazott megoldásokkal (pl. földrészek, államok, régiók, postacímek stb.).
2. Hogyan tervezne meg egy tanulmányt a különböző indexelési formák hatékonyságának összehasonlítására? Milyen adatokat használna? Mely dimenziókat hasonlítana össze?
3. A jelenlegi vektor alapú rendszerek az indexelési formák sok formáját alkalmazzák. Miért nincs egyetértés a legjobb módszert illetően? Mely módszerek milyen célokra alkalmasak és mely alkalmazási területeken?
4. Találjon ki egy Manhattan távolság mérési módszert két négyfa blokkra!(Legyen a kódjuk azonos hosszúságú!)
|
