title: Albero quadramentale
text: # Albero quadramentale
  
  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.
  
  ### Inserimento
  
  Il seguente metodo inserisce un punto all'interno della zona desiderata di un albero quadramentale.
  
  ### Query range
  
  Il metodo seguente trova tutti i punti contenuti in un intervallo.
  
  