Albero quadramentale

Un albero quadramentale a punti.

Un albero quadramentale, 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

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

Classe QuadTree

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

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

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

Voci correlate

• R-tree
• Algoritmo di Barnes-Hut

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sull'albero quadramentale

Collegamenti esterni

• (EN) Eric W. Weisstein, Quadtree, su MathWorld, Wolfram Research.
• Spatial Index Demos, su cs.umd.edu, Università del Maryland.