Quadtree

Una regione quadtree.

Un quadtree è un 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

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

• R-tree

Collegamenti esterni

• Spatial Index Demos

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