Albero quadramentale

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;   } }