Quadtree

Image
Un albero quaternario puntuale con dati puntuali. Capacità contenitore: 1.
Image
Compressione dell'albero quaternario di un'immagine, passo dopo passo

Un quadtree (dt disuse . Quadtree ) è in informatica una struttura ad albero in cui ogni nodo interno ha esattamente quattro nodi figli. Gli alberi quaternari vengono utilizzati principalmente per suddividere uno spazio bidimensionale dividendolo ricorsivamente in quattro aree (quadranti). Le aree possono essere quadrate, rettangolari o di qualsiasi forma. Una divisione simile è nota come Q-tree . Tutte le forme di quadtre condividono alcune caratteristiche:

  • Suddividono la stanza in aree personalizzabili
  • Ogni area ha una capienza massima. Se questo viene raggiunto, l'area viene suddivisa.
  • La directory dell'albero segue la suddivisione spaziale dell'albero quaternario.

specie

I Quadtrees possono essere classificati in base al tipo di dati che rappresentano, incluse aree, punti e linee. I Quadtrees possono anche essere classificati a seconda che la forma dell'albero dipenda o meno dalla sequenza di elaborazione dei dati. Alcuni tipi comuni di alberi quaternari sono:

L'area albero quaternario

L'albero quaternario dell'area rappresenta una divisione dello spazio in due dimensioni, che divide l'area in quattro quadranti uguali, sottoquadranti, ecc., Con ogni nodo finale contenente i dati di una specifica sottoarea. Ogni nodo dell'albero ha esattamente quattro figli o nessuno (nodi foglia). L'albero quaternario dell'area è un tipo di trie .

Un albero quaternario di intervallo con una profondità di n può essere utilizzato per rappresentare un'immagine di 2 n × 2 n pixel, ciascun pixel con valore 1 o 0. Il nodo radice rappresenta l'intera area dell'immagine. Se non tutti i pixel in un'area sono zero o uno, questo viene suddiviso. In questa applicazione, ogni nodo finale rappresenta un'area dell'immagine i cui punti dell'immagine sono tutti zero o uno.

Un albero quaternario di intervallo può anche essere utilizzato come rappresentazione a risoluzione variabile di un campo dati. Ad esempio, le temperature in un'area possono essere memorizzate come un albero quaternario, con la temperatura media della sottoarea memorizzata in ogni foglia.

Quando un albero quaternario di intervallo viene utilizzato per rappresentare un record di punti (ad esempio latitudine e longitudine di un numero di città), gli intervalli vengono suddivisi fino a quando ogni foglia contiene al massimo un punto.

Dot albero quaternario

L'albero quaternario puntuale è un adattamento di un albero binario utilizzato per rappresentare dati puntuali bidimensionali. Condivide le caratteristiche di un albero quaternario, ma è un vero albero perché il centro di una suddivisione è sempre un punto. La forma dell'albero dipende dall'ordine di elaborazione dei dati. Con un tempo di esecuzione di solito O (log n), è spesso molto efficiente quando si confrontano punti di dati ordinati bidimensionali.

Struttura nodale di un albero quadrangolare

Un nodo di un quadtree è simile a un nodo di un albero binario, dal quale differisce principalmente dai due puntatori (sinistro e destro) di un normale albero binario per i quattro puntatori (uno per quadrante). Inoltre, una chiave è generalmente suddivisa in due componenti che si riferiscono alle coordinate x e y. Pertanto, un nodo contiene le seguenti informazioni:

  • quattro indicatori: quad ['NW'], quad ['NO'], quad ['SW'] e quad ['SO']
  • Punto, che a sua volta contiene:
    • Attributo, solitamente espresso come coordinate x e y
    • Valore, ad esempio un nome

Albero quaternario del bordo

Gli alberi quaternari del bordo vengono utilizzati in particolare per memorizzare linee anziché punti. Le curve sono approssimate da celle finemente suddivise. Ciò può provocare alberi molto sbilanciati, il che può essere contrario allo scopo dell'indicizzazione.

Alcuni usi comuni degli alberi quaternari

Gli alberi quaternari sono l'equivalente bidimensionale degli alberi ottagonali .

Prove individuali

  1. ^ Tomas G. Rokicki: un algoritmo per comprimere spazio e tempo . 1 aprile 2006. Estratto il 20 maggio 2009.
  2. ^ Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation. Atti della 13a conferenza internazionale sulla fusione delle informazioni, Edimburgo, Regno Unito, luglio 2010.

letteratura

link internet

Commons : Quadtrees  - raccolta di immagini, video e file audio

Implementazioni