Quadtree
El término Quadtree, o árbol cuaternario, se utiliza 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.[1] Al repetir el proceso, el cuadrante se divide de nuevo en cuatro, y así sucesivamente. Esta estructura de datos fue nombrada quadtree por Raphael Finkel y J.L. Bentley en 1974.[2]
Una gran variedad de estructuras jerárquicas existen para representar los datos espaciales. Una técnica normalmente usada es Quadtree. El desarrollo de estos 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.
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:
- El tipo del dato en que ellas actúan.
- El principio que las guías del proceso de descomposición.
- 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.
Representación de puntos
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:
- Determinar si un punto dado está en el grupo.
- 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)".
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 gris), un tercer campo puede reservarse para un poco de información relacionada al nodo.
struct PRNo {
PRNo *hijos[4];
int color; // blanco = 0; gris = 1; negro = 2;
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 subcuadrante a que el nodo pertenece (el nodo echa hojas). Si este subcuadrante ya está ocupado para otro nodo 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 pseudocódigo
- Si la raíz es nula, P se vuelve la raíz.
- Si la raíz no es GRIS, significa que hay simplemente un nodo
- 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
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 está dividida en series de varios tamaños en las cuales cada serie contiene solo un valor binario. En lugar de guardar la imagen binaria, solo 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 subregión 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 subregión 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 y desventajas
- Ventajas
- La representación de imágenes por medio de esta estructura.
- Desventajas
- 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 localización de puntos en la malla de Delaunay. El qtree es adaptablemente refinado durante la iterativa inserción de mallas y puntos geométricos.
Uso
- 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.
Véase también
Referencias
- adrigm (30 de junio de 2013). «Teoría de colisiones 2D: QuadTree». Genbeta. Consultado el 12 de septiembre de 2022.
- Finkel, R. A.; Bentley, J. L. (1974). «Quad trees a data structure for retrieval on composite keys». Acta Informatica 4 (1): 1-9. S2CID 33019699. doi:10.1007/BF00288933. Consultado el 6 de noviembre de 2019.
