Kvadratno stablo
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Point_quadtree.svg/300px-Point_quadtree.svg.png)
Kvadratno stablo je vrsta binarnog stabla čiji svaki unutrašnji čvor ima tačno četvoro dece. Kvadratna stabla najčešće se koriste za podelu dvodimenzionalnog prostora rekurzivnom paralelizacijom u četiri kvadranta ili regije. Regije mogu biti kvadratnog ili pravougaonog oblika, ili mogu imati proizvoljne oblike. Rafael Finkel i Džon Bentli dali su naziv ovoj strukturi podataka,Kvadratno stablo, 1974. godine. Kvadratno stablo je takođe poznato i kao Q-stablo.
Sve forme kvadratnog stabla dele neke zajedničke karakteristike:
- Razlažu prostor u prilagodljive ćelije
- Svaka ćelija ima maksimalni kapacitet. Kada se dostigne maksimalni kapacitet,ćelija se deli
- Stablo direktorijum prati prostornu dekompoziciju kvadratnog stabla
Vrste
Kvadratna stabla mogu se klasifikovati prema vrsti podataka koje oni predstavljaju,uključujući regije,tačke,prave i krive. Kvadratna stabla takođe mogu biti klasifikovana po tome da li je oblik stabla nezavisan od redosleda podataka koji obrađuje. Neki uobičajeni tipovi su:
Regionsko kvadratno stablo
Regionsko kvadratno stablo predstavlja podelu prostora u dve dimenzije tako što razlaže regiju na četiri jednaka kvadranta,podkvadranta i tako dalje, svaki lisni čvor sadrži podatke koji odgovaraju određenom podregionu. Svaki čvor u stablu ili ima tačno četvoro dece, ili nema decu (lisni čvor).
Regionsko kvadratno stablo je vrsta stabla. Regionsko kvadratno stablo dubine n može biti korišćeno za predstavljanje slike 2n x 2n piksela, gde je svaki piksel vrednosti 0 ili 1. Koreni čvor predstavlja ceo region slike. Ako pikseli u bilo kojoj regiji nisu isključivo nule ili jedinice,ona je podeljena. U ovoj prijavi,svaki lisni čvor predstavlja blok piksela koji su sve nule ili sve jedinice.
Regionsko kvadratno stablo takođe moze biti korišćeno kao reprezentacija promenljive rezolucije polja podataka.Ako se regionsko kvadratno stablo koristi pri predstavljanju skupa tačaka podataka(kao što su geografska širina i dužina skupa gradova),regioni su podeljeni dok jedan list sadrži najviše jednu tačku.[1]
Tačkasto kvadratno stablo
Tačkasto kvadratno stablo kombinuje pristup grid struktura sa višedimenzionalnom generalizacijom stabla binarnog pretraživanja. Svaki granski(ne-lisni) čvor je povezan sa podatkovnim zapisom sa lokacijom tačke i ima četiri sledbenika (NW,NE,SW i SE). Svaka kvadrantska podela je centrirana nad podatkovnom tačkom. Vreme razvoja(izrade) kvadratnog stabla je O(n log n), a vreme traženja je O(log n).[2]
Struktura čvora za Tačkasto kvadratno stablo
Čvor tačkastog kvadratnog stabla je sličan čvoru binarnog stabla, sa glavnom razlikom u tome što ima četiri pokazivača(jedan za svaki kvadrant) umesto dva("levi" i "desni") kao u uobičajenom binarnom stablu. Takođe,ključ se obično dekomponuje na dva dela,koje se odnose na x i y koordinate. Zato čvor sadrži sledeće podatke:
- četiri pokazivača:['NW'],['NE'],['SW'], i ['SE']
- tačku; što zauzvrat sadrži:
- ključ, obično izražen kao x,y koordinate
- vrednost; na primer ime
Rubno kvadratno stablo
Rubna kvadratna stabla se obično koriste za čuvanje linija više nego za čuvanje tačaka. Krive su aproksimirane paralelizacijom ćelija u veoma fine rezolucije. Ovo može dovesti do izuzetno neuravnoteženih stabala koja mogu anulirati svrhu indeksiranja.
Poligonalna mapa kvadratnog stabla
Poligonalna mapa kvadratnog stabla (ili PM Kvadratno stablo) je varijacija kvadratnog stabla, koja se koristi za skladištenje kolekcije poligona koja mogu biti degenerisana(što znači da su izolovana temena ili ivice).[1] Postoje tri glavne klase PM Kvadratnih stabala koje variraju u zavisnosti od toga koje informacije čuvaju unutar svakog crnog čvora. PM3 kvadratna stabla mogu da skladište bilo koju veličinu ivica koje se ne seku i najviše jednu tačku. PM2 kvadratna stabla su ista kao PM3 kvadratna stabla, osim što sve ivice moraju da dele istu krajnju tačku. Konačno,PM1 kvadratna stabla slična su PM2, ali u ovom slučaju crni čvorovi mogu da ili sadrže tačku i njegove ivice, ili da sadrže skup ivica koje dele jednu tačku , ali ne može imati tačku i skup ivica koje ne sadrže tu tačku.
- Reprezentacija Kvadratnog stabla
- Prostorno indeksiranje
- Efikasno otkrivanje sudara u dve dimenzije
- Conway's Game of Life program.[3]
- Kvadratna stabla se takođe koriste u oblasti fraktalne analize slike
Pseudokod
Sledeći pseudokod pokazuje jedan način implementacije kvadratnog stabla koji koristi samo tačke. Postoje i drugi pristupi na raspolaganju.
Preduslovi
Pretpostavlja se da su ove strukture korišćene.
struct XY { float x; float y; function __construct(float _x, float _y) {...} } struct AABB { XY center; XY halfDimension; function __construct(XY center, XY halfDimension) {...} function containsPoint(XY p) {...} function intersectsAABB(AABB other) {...} }
Klasa kvadratnog stabla
Ova klasa predstavlja i kvadratno stablo i čvor gde je ukorenjen
class QuadTree { constant int QT_NODE_CAPACITY = 4; AABB boundary; Array of XY [size = QT_NODE_CAPACITY] points; // Deca QuadTree* northWest; QuadTree* northEast; QuadTree* southWest; QuadTree* southEast; // Metode function __construct(AABB _boundary) {...} function insert(XY p) {...} function subdivide() {...} function queryRange(AABB range) {...} }
Umetanje
Sledeći metod ubacuje tačku u odgovarajući kvadrat kvadratnog stabla.
class QuadTree { ... // Ubacujemo tačku u kvadratno stablo function insert(XY p) { // Zanemarujemo objekte koji ne pripadaju ovom kvadratnom stablu if (!boundary.containsPoint(p)) return false; // Ako ima mesta u ovom kvadratnom stablu,dodajemo objekat ovde if (points.size < QT_NODE_CAPACITY) { points.append(p); return true; } // U suprotnom,moramo podeliti na manje delove,zatim dodati tačku bilo kojem čvoru koji će to prihvatiti if (northWest == null) subdivide(); if (northWest->insert(p)) return true; if (northEast->insert(p)) return true; if (southWest->insert(p)) return true; if (southEast->insert(p)) return true; // Inače,tačka neće biti ubačena iz nekog nepoznatog razloga return false; } }
Ispitivanje opsega
Sledeći metod pronalazi sve tačke koje se nalaze u opsegu.
class QuadTree { ... //Pronalazimo sve tačke koje se pojavljuju unutar opsega function queryRange(AABB range) { // Priprema se niz rezultata Array of XY pointsInRange; // Automatski prekid ukoliko se opseg ne podudara sa ovim kvadratom if (!boundary.intersectsAABB(range)) return pointsInRange; // empty list // Provera objekata for (int p := 0; p < points.size; p++) { if (range.containsPoint(points[p])) pointsInRange.append(points[p]); } // Prekida se ovde,ako nema dece if (northWest == null) return pointsInRange; // U suprotnom,dodajemo tačke koje pripadaju deci pointsInRange.appendArray(northWest->queryRange(range)); pointsInRange.appendArray(northEast->queryRange(range)); pointsInRange.appendArray(southWest->queryRange(range)); pointsInRange.appendArray(southEast->queryRange(range)); return pointsInRange; } }
Reference
Beleške
- ^ а б Hanan Samet and Robert Webber. "Storing a Collection of Polygons Using Quadtrees". ACM Transactions on Graphics July (1985), pp. 182-222. InfoLAB. Web. 23 March 2012
- ^ Strukture i metode pristupa
- ^ Rokicki, Tomas G. (1. 4. 2006). „An Algorithm for Compressing Space and Time”. Приступљено 20. 5. 2009.
Glavne reference
- Finkel, Raphael; J.L. Bentley (1974). „Quad Trees: A Data Structure for Retrieval on Composite Keys”. Acta Informatica. 4 (1): 1—9. doi:10.1007/BF00288933.
- Mark de Berg; et al. (2000). „Quadtrees”. Computational Geometry (2nd revised изд.). Springer-Verlag. стр. 291–306. ISBN 978-3-540-65620-3.
- Samet, Hanan; Webber, Robert (jul 1985). „Storing a Collection of Polygons Using Quadtrees” (PDF). Архивирано из оригинала (PDF) 17. 06. 2012. г. Приступљено 23. 3. 2012.
Spoljašnje veze
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png)
- Diskusija o kvadratnom stablu
- Javascript implementacija kvadratnog stabla korišćena za detekciju kolizije
- Java Implementacija
- C++ implementacija kvadratnog stabla koje se koristi za prostorno indeksiranje trouglova