Albero quadramentale
![](https://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Point_quadtree.svg/220px-Point_quadtree.svg.png)
Un albero quadramentale,[1] spesso indicato con il termine inglese "quadtree", è una struttura dati ad albero non bilanciata nella quale tutti i nodi interni hanno esattamente quattro nodi figli. I quadtree sono spesso usati per partizionare uno spazio bidimensionale suddividendolo ricorsivamente in quattro quadranti, comunemente denotati come Nord-Est, Nord-Ovest, Sud-Est, Sud-Ovest.
Utilizzi comuni di questo tipo di strutture sono i seguenti:
- Rappresentazione di immagini;
- Indicizzazione spaziale;
- determinazione di collisioni in due dimensioni;
- Memorizzazione di dati sparsi, come la memorizzazione di informazioni di formattazione per un foglio elettronico o per calcoli su matrici.
I alberi quadramentali sono i corrispondenti in due dimensione degli alberi ottali (chiamati anche "octree") .
I quadtree sono strutture dati ad albero in cui l'immagine è divisa in 4 quadranti; procedendo in senso orario e partendo da quello in alto a sinistra, per ogni quadrante si controlla se è uniforme: se non lo è si ripete il procedimento per quel quadrante fino al raggiungimento di zone uniformi (al massimo si arriva al singolo pixel).
Alberi quadramentali come rappresentazioni spaziali 2D
[modifica | modifica wikitesto]Gli alberi quadramentali PR (Punto Regione) rappresentano un insieme di punti in due dimensioni che decompongono la regione che li contiene in quattro sotto-quadranti, che possono, a loro volta venir decomposti, e così via sino ai nodi foglia. Gli stop-criteria generalmente utilizzati sono due:
- La foglia contiene un numero di punti inferiore ad un numero massimo prefissato
- La foglia ha un'area minima
Pseudocodice
[modifica | modifica wikitesto]Classe QuadTree
[modifica | modifica wikitesto]Questa classe rappresenta sia un albero quadramentale che un nodo dove è radicato.
class QuadTree { // Arbitrary constant to indicate how many elements can be stored in this quad tree node constant int QT_NODE_CAPACITY = 4; // Axis-aligned bounding box stored as a center with half-dimensions // to represent the boundaries of this quad tree AABB boundary; // Points in this quad tree node Array of XY [size = QT_NODE_CAPACITY] points; // Children QuadTree* northWest; QuadTree* northEast; QuadTree* southWest; QuadTree* southEast; // Methods function __construct(AABB _boundary) {...} function insert(XY p) {...} function subdivide() {...} // create four children that fully divide this quad into four quads of equal area function queryRange(AABB range) {...} }
Inserimento
[modifica | modifica wikitesto]Il seguente metodo inserisce un punto all'interno della zona desiderata di un albero quadramentale.
class QuadTree { ... // Insert a point into the QuadTree function insert(XY p) { // Ignore objects that do not belong in this quad tree if (!boundary.containsPoint(p)) return false; // object cannot be added // If there is space in this quad tree, add the object here if (points.size < QT_NODE_CAPACITY) { points.append(p); return true; } // Otherwise, subdivide and then add the point to whichever node will accept it 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; // Otherwise, the point cannot be inserted for some unknown reason (this should never happen) return false; } }
Query range
[modifica | modifica wikitesto]Il metodo seguente trova tutti i punti contenuti in un intervallo.
class QuadTree { ... // Find all points that appear within a range function queryRange(AABB range) { // Prepare an array of results Array of XY pointsInRange; // Automatically abort if the range does not intersect this quad if (!boundary.intersectsAABB(range)) return pointsInRange; // empty list // Check objects at this quad level for (int p := 0; p < points.size; p++) { if (range.containsPoint(points[p])) pointsInRange.append(points[p]); } // Terminate here, if there are no children if (northWest == null) return pointsInRange; // Otherwise, add the points from the children pointsInRange.appendArray(northWest→queryRange(range)); pointsInRange.appendArray(northEast→queryRange(range)); pointsInRange.appendArray(southWest→queryRange(range)); pointsInRange.appendArray(southEast→queryRange(range)); return pointsInRange; } }
Note
[modifica | modifica wikitesto]- ^ Daniela Cancilia e Stefano Mazzanti, Il dizionario enciclopedico di informatica (PDF), Zanichelli, p. 647. URL consultato il 4 gennaio 2018.
Voci correlate
[modifica | modifica wikitesto]Altri progetti
[modifica | modifica wikitesto]Wikimedia Commons contiene immagini o altri file sull'albero quadramentale
Collegamenti esterni
[modifica | modifica wikitesto]- (EN) Eric W. Weisstein, Albero quadramentale, su MathWorld, Wolfram Research.
- Spatial Index Demos, su cs.umd.edu, Università del Maryland.