Quadtree

Da Wikipedia, l'enciclopedia libera.
Una regione quadtree.

Un 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 dei quadtree 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 quadtree sono i corrispondenti in due dimensione degli octree.

Quadtree come rappresentazioni spaziali 2D[modifica | modifica wikitesto]

I quadtree 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

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica