El termino Quadtree es utilizado para describir clases de estructuras de datos jerárquicas cuya propiedad común es que están basados en el principio de descomposición recursiva del espacio. En un QuadTree de puntos, el centro de una subdivisión está siempre en un punto. Al insertar un nuevo elemento, el espacio queda divido en cuatro cuadrantes. Al repetir el proceso, el cuadrante se divide de nuevo en cuatro cuadrantes, y así sucesivamente.

Contenido 1 Introducción 1.1 Visión General del Quadtree 2 Representación de Puntos en Quadtree 3 Inserción 4 Descripción en seudo codigo, paso a paso, de la inserción de un punto "P" 4.1 Tipos 4.1.1 Quadtree de Puntos 4.1.2 Quadtree de la Región 4.1.2.1 Ventajas del QuadTree 4.1.2.2 Desventajas del QuadTree 4.1.3 El Qtree-cubo 4.2 Algunas Aplicaciones Comunes de Quadtrees 4.3 Algoritmos Quadtree 4.3.1 Algoritmo de inserción 4.3.2 Algoritmo para eliminar elementos del árbol 4.3.3 Algoritmo para buscar nodos de una región 4.3.4 Algoritmo para obtener el cuadrante 5 Enlaces externos 5.1 En Inglés

Introducción

Una gran variedad de estructuras jerárquicas existen para representar los datos espaciales. Una técnica usualmente usada es Quadtree. El desarrollo de éstos fue motivado por la necesidad de guardar datos que se insertan con valores idénticos o similares. Este artículo trata de la representación de datos en el espacio bidimensional. Quadtree también se usa para la representación de datos en los espacios tridimensionales o con hasta 'n' dimensiones.

Visión General del Quadtree

El término Quadtree se usa para describir una clase de estructuras jerárquicas cuya propiedad en común es el principio de recursividad de descomposición del espacio.

Estas clases, basan su diferencia en los requisitos siguientes:

1. El tipo del dato en que ellas actúan.
2. El principio que las guías del proceso de descomposición.
3. La resolución (inconstante o ninguna).

La familia Quadtree se usa para representar puntos, áreas, curvas, superficies y volúmenes. La descomposición puede hacerse en las mismas partes en cada nivelado (la descomposición regular), o puede depender de los datos de la entrada. La resolución de la descomposición, en otros términos, el número de tiempos en que el proceso de descomposición es aplicado, puede tratarse de antemano, o puede depender de las propiedades de los datos de la entrada.

El primer ejemplo de un Quadtree se relaciona a la representación de un área bidimensional. La región Quadtree que representa las áreas es el tipo más estudiado. Este ejemplo es basado en la subdivisión sucesiva del espacio en cuatro cuadrantes del mismo tamaño. El subcuadrante que contiene datos simplemente se denomina área Negra, y los que no contienen datos se denominan área Blanca. Un subcuadrante que contiene partes de ambos se denomina área Ceniza. Los subcuadrantes Ceniza, que contienen aéreas Blancas y Negras (Vacío y Datos), deben subdividirse sucesivamente hasta que solo queden cuadrantes Negros Y Blancos... (Datos y Vacíos).

Cada cuadrante representa un nodo del Quadtree, los espacios negros y blancos siempre están en las hojas, mientras todos los nodos interiores representan los espacios grises. La ilustración 1.1 muestra los pasos necesarios para la creación de un Quadtree a través de la subdivisión sucesiva de un área espacial. A los espacios negros, en esta ilustración, se sustituyen simplemente por espacios amarillos para facilitar la visualización. La enumeración de los cuadrantes es hecho en sentido del horario que sale del cuadrante superior izquierdo.

Representación de Puntos en Quadtree

Pueden representarse las multidimensiones de los puntos de varias maneras. La representación escogida depende de la tarea específica que uno quiera ejecutar con un grupo de puntos. Dos de las tareas más comunes que se realizan con un grupo de puntos son:

1. Determinar si un punto dado está en el grupo.
2. Para encontrar un grupo de puntos que se relacionan dado algún criterio de un segundo punto.

El Quadtree, sus variantes y también el kd-árbol, representan los formularios bastante eficaces para representar los puntos. Los dos tipos más común de Quadtree para representar los puntos son el "Point Quadtree" y el "PR Quadtree (la variante del Quadtree de la región)".

A continuación se muestra a modo de ejemplo tres posibles representaciones de puntos con el algoritmo RE Quadtree:

El PR-Quadtree es una adaptación del Quadtree para la representación de puntos en una región. Cada punto es asociado con el cuadrante. Diferente del Point Quadtree dónde la división de los cuadrantes depende de los datos de la entrada, la división siempre es hecha de una manera regular. Los nodos-hoja que contienen un punto los denominaremos Negros, y si están vacíos Blancos. Todos los nodos que no tienen hojas se denominan Ceniza.

Cada nodo se guarda en un registro que contiene cinco campos. El primero contiene un vector de indicadores para los cuatro hijos del nodo (correspondiendo a los cuatro cuadrantes), el segundo, el color del nodo (blanco, negro o ceniza), un tercer campo puede reservarse para un poco de información relacionada al nodo.

  struct PRNo {  
  PRNo * filhos[4];  
  int color; 	/ * 0 = white; 1 = gray; 2 = black; * /  
  char info [20];  
  int x;  
  int y;  
  };

Inserción

Los puntos se insertan de una manera similar a la usada en el Point Quadtree. Primeramente se hace una búsqueda para encontrar el subquadrante a que el nodo pertenece (el nodo echa hojas). Si este subquadrante ya está ocupado para otro nudo B con las coordenadas diferentes, entonces este cuadrante debe subdividirse en las partes necesarias para que los nodos A y B no ocupen el mismo cuadrante. Esto puede causar un gran número de subdivisiones, sobre todo si los dos puntos se contienen en un bloque muy pequeño del espacio. Los nodos interiores no guardan los datos, desde el punto que ocupó el cuadrante previamente (el punto B) si se vuelve el hermano del nuevo punto (el punto A). Como resultado se observa que todos los nodos grises poseen a dos descendientes que contienen los datos como mínimo. El formulario que resulta de un PR-Quadtree es independiente del orden en que los puntos se insertan.

Descripción en seudo codigo, paso a paso, de la inserción de un punto "P"

1. Si la raíz es nula, P se vuelve la raíz.
2. Si la raíz no es GRIS, significa que hay simplemente un nodo
3. Se realiza una búsqueda a partir de la raíz para encontrar el cuadrante a que P pertenece

Nota: Si el nodo echa hojas y donde P debe insertarse está vacío (BLANCO), P se inserta. En caso de que está ocupado, el punto que está ahora en el nodo (R) debe recuperarse. En caso de que P y R pertenezcan el subcuadrantes diferente, ellos son simplemente insertados en sus posiciones respectivas. En caso de que ellos pertenezcan a los mismos cuadrantes, las subdivisiones sucesivas deben realizarse hasta que los cuadrantes sean diferentes. En cada subdivisión un nodo gris debe crearse.

Tipos

Quadtrees se puede clasificar según el tipo de datos que representan, incluyendo áreas, puntos, líneas y curvas. Quadtrees puede también ser clasificado independientemente de la forma que tenga por la información que contiene. Algunos tipos comunes de quadtrees son:

Quadtree de Puntos

El quadtree del punto es una adaptación de un árbol binario usado para representar datos de dos dimensiones del punto. Comparte las características de todos los quadtrees pero es un árbol verdadero mientras que el centro de una subdivisión está siempre en un punto. Se procesa la forma del árbol depende de los datos de la orden. Es a menudo muy eficiente en comparar los puntos de referencias pedidos de dos dimensiones, funcionando generalmente en tiempo de O (log n.

Estructura del nodo para un quadtree de puntos

• 4 Punteros: cuadrante [‘NW’], cuadrante [‘NE’], cuadrante[‘SW’], y cuadrante[‘SE’]
• Puntos, del tipo DataPoint, que alternadamente contiene:

-Nombre -(x, y) Coordenadas

Una imagen binaria es normalmente representada como una serie de entradas binarias, es decir; cada una de las entradas de la serie tiene un valor de 0 o 1. Para guardar la imagen binaria normalmente se usa la conocida partición quadtree. Para una serie N*N, N<=512 y N=2i para algún entero positivo i, si las entradas no tienen igual valor, entonces se divide en 4 N/2*N/2 series. Si una serie N/2*N/2 no tiene el mismo valor binario, tal como arriba a la derecha y abajo a la derecha de la serie N/2*N/2, entonces podemos dividirlo en cuatro N/4*N/4 formas otra vez. Estas N/4*N/4 formas pueden a su vez también, si es necesario dividirse en 4 N/8*N/8 formas, etc. La partición quadtree es completa cuando toda la forma esta dividida en series de varios tamaños en las cuales cada serie contiene sólo un valor binario. En lugar de guardar la imagen binaria, sólo necesitamos guardar el quadtree con el código que referente a la imagen de la entrada.

Quadtree de la Región

El quadtree de la región representa una partición del espacio en dos dimensiones descomponiendo la región en cuatro cuadrantes iguales, subcuadrantes, y así sucesivamente con cada nodo de la hoja que contiene los datos que corresponden a un subregion específico. Cada nodo en el árbol tiene exactamente cuatro niños, o no tiene ningún niño (un nodo de la hoja). Un quadtree de la región con una profundidad de n se puede utilizar para representar una imagen que consiste en 2n * pixeles 2n, donde está 0 o 1 cada valor del pixel. Esta estructura de datos es unidimensional y solo se encuentra en memoria principal. Cada nodo hijo tiene asociado a él cuatro nodos, representando así los dieciséis sub-cuadrantes de dicha imagen. Una vez formado el Quadtree, los nodos hojas representan la característica de dicho píxel, que puede ser blanco o negro, si son imágenes monocromáticas, dependiendo de la uniformidad del color de los nodos hijos (si todos sus hijos son de color negro, entonces dicho nodo será representado por el color negro). Pero si algún nodo posee nodos hijos con colores no uniformes, entonces es representado por un “nodo gris”. Un quadtree de la región se puede también utilizar como representación variable de la resolución de una zona de informaciones. Por ejemplo, las temperaturas en un área se pueden almacenar como quadtree, con cada nodo de la hoja almacenando la temperatura media sobre el subregion que representa. Si un quadtree de la región se utiliza para representar un sistema de datos del punto (tales como la latitud y la longitud de un sistema de ciudades), se subdividen las regiones hasta que cada hoja contiene a lo máximo un solo punto.

Ventajas del QuadTree

• La representación de imágenes por medio de esta estructura.

Desventajas del QuadTree

• Una desventaja que presenta la estructura es cuando debe almacenar gran cantidad de diferentes píxeles existentes en una imagen con muchos colores, dado que podría tomar un tamaño excesivamente grande.
• Por ser esta estructura de datos de memoria principal, al querer representar imágenes muy grandes, muchas veces el Quadtree no puede ser almacenado en dicha memoria. En tal caso, se utilizan estructuras alternativas por ejemplo, un B+ tree, para compensar tal limitación.

El Qtree-cubo

Lo primero que nos viene a la mente para el problema de la ubicación de un punto es un Q-tree balanceado. El clásico método de Qtree tiene algunas desventajas cuando por ejemplo se le permiten a las coordenadas de un punto cambiar o cuando existen muchas inserciones y eliminaciones.

Para esto el mejor (sin dudas) es el Qtree de cubo por las siguientes razones: Es muy fácil de implementar y la teoría de la localización del punto menos eficiente está bastante lejos por el “balance implícito” del método (la secuencia de inserciones de puntos no tiene impacto en la estructura del árbol final sin la necesidad de explicar el balance del árbol). Es insensible a los cambios de coordenadas de los puntos y muy eficiente a la hora de eliminaciones. Estructura de datos de un q-tree de región usado para la locación de puntos en la malla de Delaunay. El qtree es adaptablemente refinado durante la iterativa inserción de mallas y puntos geométricos.

Algunas Aplicaciones Comunes de Quadtrees

• Representación de la imagen.
• Indexación de direcciones espaciales.
• Detección eficiente de la colisión en dos dimensiones.
• Desecho del tronco de la visión de los datos del terreno.
• Almacenando datos escasos, tales como una información del formato para una hoja de balance o para algunos cálculos de la matriz.
• Solución de los campos multidimensionales (dinámica, electromagnetismo flúidos de cómputo)
• Quadtrees es el análogo de dos dimensiones de octrees.

Algoritmos Quadtree

Los algoritmos que se presentan empiezan construyendo un quadtree para guardar los puntos. Así, las hojas del árbol tendrán almacenadas las posiciones correspondientes de las partículas. Cuando se presenta una distribución no uniforme de los puntos en su “cajón”, se nota que muchas de las hojas de un quadtree completo presentan vacíos. En este caso, no tiene ningún sentido guardar estas partes del quadtree. En lugar, se continua subdividiendo los cuadrados sólo cuando contienen más de 1 punto (o algún número pequeño de puntos).

Algoritmo de inserción

void Insertar(int px, int py, T pinfo)

   {
     if(EsVacio())
     {
       info=pinfo;
       x=px;
       y=py;
       NW=new CQuadTree<T>();
       SW=new CQuadTree<T>();
       NE=new CQuadTree<T>();
       SE=new CQuadTree<T>();
     }
     else if(EsHoja())
     {
       int hijo=ObtenerHijo(px, py);
       switch(hijo)
       {
         case 1:
         {
           SE=new CQuadTree<T>(px, py, pinfo);
         };break;
         case 2:
         {
           NE=new CQuadTree<T>(px, py, pinfo);
         };break;
         case 3:
         {
           SW=new CQuadTree<T>(px, py, pinfo);
         };break;
         case 4:
         {
           NW=new CQuadTree<T>(px, py, pinfo);
         };break;
       }
     }
     else
     {
       int hijo=ObtenerHijo(px, py);
       switch(hijo)
       {
         case 1:
         {
           SE->Insertar(px, py, pinfo);
         };break;
         case 2:
         {
           NE->Insertar(px, py, pinfo);
         };break;
         case 3:
         {
           SW->Insertar(px, py, pinfo);
         };break;
         case 4:
         {
           NW->Insertar(px, py, pinfo);
         };break;
       }
     }
   }

/*

   int ObtenerHijo(int px, int py)
   {
     if(x<px)
     {
       if(y<py)
         return 1;
       else
         return 2;
     }
     else
     {
       if(y<py)
         return 3;
       else
         return 4;
     }
   }

• /

Algoritmo para eliminar elementos del árbol

/*método extraído de el libro de estructuras espaciales*/

Método void eliminar() {

    observer.agrega_Rect(limite, Tipo_Actividad.VISITAR);
         if (tieneDatos()) {
              visita_Elimi(dato);
              dato = null;
         } else if (tieneHijos()) {
              for (QuadTreeNodo n : hijos) {
                   n.elimiTodo();}
              for (QuadTreeNodo n : hijos) {
                   observer.agrega_Rect(n.getBounds(), Tipo_Actividad.ELIMINAR);
                   observer.elimina_Rect(n.getBounds(), Tipo_Actividad.NINGUNO);
                   observer.elimina_Rect(n.getBounds(), Tipo_Actividad.ELIMINAR);
              }
              hijos = null;
         } else {}
    observer.elimina_Rect(limite, Tipo_Actividad.VISITAR);
}

Algoritmo para buscar nodos de una región

/*método extraído del libro de estructuras espaciales*/

void buscar(Rect rect) {

     observer.agrega_Rect(limite, Tipo_Actividad.VISITAR);
          if (rect.intersect(limite)) {
               if (tieneDatos()) {
                    observer.agrega_Pto(dato, Tipo_Actividad.VISITAR);
                    if (rect.intersecto(dato)) {
                         observer.agrega_Pto(dato, Tipo_Actividad.RESULTADO);
                    }
                    observer.elimina_Pto(dato, Tipo_Actividad.VISITAR);
               } else if (tieneHijos()) {
                    for (QuadTreeNodo n : hijos) {
                         n.seleccion(rect);}
               } else { }
          }
     observer.elimina_Rect(limite, Tipo_Actividad.VISITAR);

}

Algoritmo para obtener el cuadrante

El punto P se compara con el resto de los puntos con respecto al centro del cuadrante.

  retorna_quadrante (PRNo * p, int XX, int YY)    
  {    
  Si (el p->x <XX)    
  Si (el p->y <YY)    
  Devuelva 3;    
  Sino    
  Devuelva 0;    
  Sino    
  Si (el p->y <YY)    
  Devuelva 2;    
  Sino    
  Devuelva 1;    
  }

Enlaces externos

En Inglés

• Spatial Index Demos
• A discussion of the Quadtree and an application
• Considerable discussion and demonstrations of Spatial Indexing