Árbol cuatripartito

Un quadtree es una estructura de datos en forma de árbol donde cada nodo interno tiene exactamente cuatro hijos. Los quadtrees son el análogo bidimensional de los octrees y se utilizan con frecuencia para particionar un espacio bidimensional, subdividiéndolo recursivamente en cuatro cuadrantes o regiones. Los datos asociados a una celda hoja varían según la aplicación, pero la celda hoja representa una "unidad de información espacial relevante".

Las regiones subdivididas pueden ser cuadradas o rectangulares, o pueden tener formas arbitrarias. Aunque se utilizaron subdivisiones similares mucho antes (por ejemplo, en el lema de cobertura de Whitney de 1934), ^{[ 1 ]} esta estructura de datos fue denominada quadtree por Raphael Finkel y JL Bentley en 1974. ^{[ 2 ]} Una partición similar también se conoce como Q-tree .

Todas las formas de quadtrees comparten algunas características comunes:

• Descomponen el espacio en células adaptables.
• Cada celda (o cubo) tiene una capacidad máxima. Cuando se alcanza la capacidad máxima, el cubo se divide.
• El directorio del árbol sigue la descomposición espacial del quadtree.

Una pirámide de árbol ( pirámide T ) es un árbol "completo"; cada nodo de la pirámide T tiene cuatro nodos hijos, excepto los nodos hoja; todas las hojas están en el mismo nivel, el nivel que corresponde a los píxeles individuales de la imagen. Los datos de una pirámide de árbol se pueden almacenar de forma compacta en un arreglo como una estructura de datos implícita, de manera similar a como un montón binario puede almacenar un árbol binario completo de forma compacta en un arreglo. ^{[ 3 ]}

Los quadtrees se pueden clasificar según el tipo de datos que representan, incluyendo áreas, puntos, líneas y curvas. También se pueden clasificar según si la forma del árbol es independiente del orden en que se procesan los datos. A continuación, se muestran algunos tipos comunes de quadtrees.

El quadtree de región representa una partición del espacio en dos dimensiones al descomponer la región en cuatro cuadrantes iguales, subcuadrantes, etc., donde cada nodo hoja contiene datos correspondientes a una subregión específica. También puede interpretarse como un método para " subdividir la región", basado en un conjunto de cuadrículas jerárquicas; o como un método de compresión de imágenes , cuando una imagen se discretiza como un mosaico de "regiones de igual color".

Cada nodo del árbol tiene exactamente cuatro hijos o ninguno (un nodo hoja). La altura de los quadtrees que siguen esta estrategia de descomposición (es decir, subdividir subcuadrantes siempre que haya datos interesantes en el subcuadrante para los que se desee mayor refinamiento) es sensible y depende de la distribución espacial de las áreas de interés en el espacio que se está descomponiendo. El quadtree de región es un tipo de trie .

Un quadtree de región con una profundidad n puede usarse para representar una imagen compuesta por 2n ^× 2n ^píxeles , donde cada píxel tiene un valor de 0 o 1. El nodo raíz representa toda la región de la imagen. Si los píxeles de una región no son completamente 0 o 1, se subdivide. En esta aplicación, cada nodo hoja representa un bloque de píxeles que son todos 0 o todos 1. Cabe destacar el ahorro potencial de espacio al usar estos árboles para almacenar imágenes; las imágenes suelen tener muchas regiones de tamaño considerable con el mismo valor de color. En lugar de almacenar una gran matriz bidimensional de cada píxel de la imagen, un quadtree puede capturar la misma información en niveles de división potencialmente mucho más altos que las celdas del tamaño de la resolución de píxeles que necesitaríamos de otro modo. La resolución del árbol y su tamaño total están limitados por el tamaño de los píxeles y de la imagen.

Un quadtree regional también puede utilizarse como representación de resolución variable de un campo de datos. Por ejemplo, las temperaturas de una zona pueden almacenarse como un quadtree, donde cada nodo hoja almacena la temperatura media de la subregión que representa.

El quadtree de puntos ^{[ 4 ]} es una adaptación de un árbol binario utilizado para representar datos de puntos bidimensionales. Comparte las características de todos los quadtrees, pero es un árbol verdadero, ya que el centro de una subdivisión siempre está en un punto. Suele ser muy eficiente para comparar puntos de datos ordenados bidimensionales, operando generalmente en tiempo O(log n) . Vale la pena mencionar los quadtrees de puntos para mayor exhaustividad, pero han sido superados por los árboles k -d como herramientas para la búsqueda binaria generalizada. ^{[ 5 ]} Los quadtrees de puntos con inserción aleatoria se han estudiado bajo el nombre de retículos estocásticos planares ponderados . ^{[ 6 ]}

Los quadtrees de puntos se construyen de la siguiente manera: dado el siguiente punto a insertar, se localiza la celda que lo contiene y se añade al árbol. El nuevo punto se añade de forma que la celda que lo contiene quede dividida en cuadrantes por las líneas verticales y horizontales que lo atraviesan. Por consiguiente, las celdas son rectangulares, pero no necesariamente cuadradas. En estos árboles, cada nodo contiene uno de los puntos de entrada.

Dado que la división del plano se determina por el orden de inserción de los puntos, la altura del árbol es sensible a dicho orden y depende de él. Una inserción en un orden incorrecto puede dar lugar a un árbol cuya altura sea lineal con respecto al número de puntos de entrada (en cuyo caso se convierte en una lista enlazada). Si el conjunto de puntos es estático, se puede realizar un preprocesamiento para crear un árbol de altura equilibrada.

Un nodo de un quadtree de puntos es similar a un nodo de un árbol binario , con la principal diferencia de que tiene cuatro punteros (uno para cada cuadrante) en lugar de dos ("izquierda" y "derecha") como en un árbol binario ordinario. Además, una clave generalmente se descompone en dos partes, que hacen referencia a las coordenadas x e y. Por lo tanto, un nodo contiene la siguiente información:

• cuatro punteros: quad['NW'], quad['NE'], quad['SW'] y quad['SE']
• punto; que a su vez contiene:
  • Clave; generalmente se expresa como coordenadas x, y.
  • valor; por ejemplo un nombre

Los quadtrees de región de puntos (PR) ^{[ 7 ] [ 8 ]} son ​​muy similares a los quadtrees de región. La diferencia radica en el tipo de información que almacenan sobre las celdas. En un quadtree de región, se almacena un valor uniforme que se aplica a toda el área de la celda de una hoja. Sin embargo, las celdas de un quadtree PR almacenan una lista de puntos que existen dentro de la celda de una hoja. Como se mencionó anteriormente, para los árboles que siguen esta estrategia de descomposición, la altura depende de la distribución espacial de los puntos. Al igual que el quadtree de puntos, el quadtree PR también puede tener una altura lineal cuando se le proporciona un conjunto "malo".

Los quadtrees de aristas ^{[ 9 ] [ 10 ]} (muy similares a los quadtrees PM) se utilizan para almacenar líneas en lugar de puntos. Las curvas se aproximan subdividiendo las celdas con una resolución muy fina, específicamente hasta que haya un único segmento de línea por celda. Cerca de las esquinas/vértices, los quadtrees de aristas continuarán dividiéndose hasta alcanzar su nivel máximo de descomposición. Esto puede dar lugar a árboles extremadamente desequilibrados, lo que podría anular el propósito de la indexación.

El quadtree de mapas poligonales (o PM Quadtree) es una variación del quadtree que se utiliza para almacenar colecciones de polígonos que pueden ser degenerados (es decir, que tienen vértices o aristas aislados). ^{[ 11 ] [ 12 ]} Una gran diferencia entre los PM quadtrees y los quadtrees de aristas es que la celda en consideración no se subdivide si los segmentos se encuentran en un vértice de la celda.

Existen tres clases principales de árboles cuaternarios PM, que varían según la información que almacenan en cada nodo negro. Los árboles cuaternarios PM3 pueden almacenar cualquier cantidad de aristas que no se intersecan y, como máximo, un punto. Los árboles cuaternarios PM2 son iguales a los PM3, excepto que todas las aristas deben compartir el mismo punto final. Finalmente, los árboles cuaternarios PM1 son similares a los PM2, pero los nodos negros pueden contener un punto y sus aristas, o solo un conjunto de aristas que comparten un punto; sin embargo, no se puede tener un punto y un conjunto de aristas que no lo contengan.

Esta sección resume una subsección de un libro de Sariel Har-Peled . ^{[ 13 ]}

Si almacenáramos cada nodo correspondiente a una celda subdividida, podríamos terminar almacenando muchos nodos vacíos. Podemos reducir el tamaño de dichos árboles dispersos almacenando solo los subárboles cuyas hojas tienen datos interesantes (es decir, "subárboles importantes"). De hecho, podemos reducir aún más el tamaño. Cuando solo conservamos los subárboles importantes, el proceso de poda puede dejar rutas largas en el árbol donde los nodos intermedios tienen grado dos (un enlace a un padre y un hijo). Resulta que solo necesitamos almacenar el nodo${\displaystyle u}$al comienzo de esta ruta (y asociarle algunos metadatos para representar los nodos eliminados) y adjuntar el subárbol enraizado en su extremo a${\displaystyle u}$. Todavía es posible que estos árboles comprimidos tengan una altura lineal cuando se les proporcionan puntos de entrada "malos".

Aunque recortamos gran parte del árbol al realizar esta compresión, aún es posible lograr búsqueda, inserción y eliminación en tiempo logarítmico aprovechando las curvas de orden Z. La curva de orden Z mapea cada celda del quadtree completo (y por lo tanto incluso del quadtree comprimido) en${\displaystyle O(1)}$tiempo a una línea unidimensional (y la mapea de nuevo en${\displaystyle O(1)}$tiempo también), creando un orden total en los elementos. Por lo tanto, podemos almacenar el quadtree en una estructura de datos para conjuntos ordenados (en la que almacenamos los nodos del árbol).

Debemos enunciar una suposición razonable antes de continuar: suponemos que dados dos números reales${\displaystyle \alpha ,\beta \in [0,1)}$expresado como binario, podemos calcular en${\displaystyle O(1)}$tiempo el índice del primer bit en el que difieren. También asumimos que podemos calcular en${\displaystyle O(1)}$tiempo el ancestro común más bajo de dos puntos/celdas en el quadtree y establecer su orden Z relativo , y podemos calcular la función piso en${\displaystyle O(1)}$tiempo.

Con estas suposiciones, la ubicación de un punto dado${\displaystyle q}$(es decir, determinar la célula que contendría${\displaystyle q}$Las operaciones de inserción y eliminación se pueden realizar en${\displaystyle O(\log {n})}$tiempo (es decir, el tiempo que se tarda en realizar una búsqueda en la estructura de datos del conjunto ordenado subyacente).

Para realizar una localización de punto para${\displaystyle q}$(es decir, encontrar su celda en el árbol comprimido):

1. Encuentra la celda existente en el árbol comprimido que viene antes${\displaystyle q}$en el orden Z. Llama a esta celda${\displaystyle v}$.
2. Si${\displaystyle q\in v}$, devolver${\displaystyle v}$.
3. De lo contrario, encuentra cuál habría sido el ancestro común más bajo del punto.${\displaystyle q}$y la célula${\displaystyle v}$en un quadtree sin comprimir. Llama a esta celda ancestral${\displaystyle u}$.
4. Encuentra la celda existente en el árbol comprimido que viene antes${\displaystyle u}$en el orden Z y devolverlo.

Sin entrar en detalles específicos, para realizar inserciones y eliminaciones primero localizamos el elemento que queremos insertar o eliminar, y luego procedemos a insertarlo o eliminarlo. Es importante reestructurar el árbol adecuadamente, creando y eliminando nodos según sea necesario.

• Representación de imágenes
• Procesamiento de imágenes
• Generación de malla ^{[ 14 ]}
• Indexación espacial , consultas de ubicación de puntos y consultas de rango.
• Detección eficiente de colisiones en dos dimensiones
• Visualización de datos de terreno mediante la eliminación de troncos de pirámide
• Almacenar datos dispersos, como información de formato para una hoja de cálculo ^{[ 15 ]} o para algunos cálculos matriciales.
• Solución de campos multidimensionales ( dinámica de fluidos computacional , electromagnetismo )
• Programa de simulación del Juego de la Vida de Conway . ^{[ 16 ]}
• Estimación de estado ^{[ 17 ]}
• Análisis de imágenes fractales
• Conjuntos disjuntos máximos

Los quadtrees, en particular el quadtree de región , se han adaptado bien a las aplicaciones de procesamiento de imágenes. Limitaremos nuestra discusión a datos de imágenes binarias, aunque los quadtrees de región y las operaciones de procesamiento de imágenes realizadas sobre ellos son igualmente adecuados para imágenes en color. ^{[ 5 ] [ 18 ]}

Una de las ventajas de usar quadtrees para la manipulación de imágenes es que las operaciones de unión e intersección se pueden realizar de forma sencilla y rápida. ^{[ 5 ] [ 19 ] [ 20 ] [ 21 ] [ 22 ]} Dadas dos imágenes binarias, la unión de imágenes (también llamada superposición ) produce una imagen en la que un píxel es negro si cualquiera de las imágenes de entrada tiene un píxel negro en la misma ubicación. Es decir, un píxel en la imagen de salida es blanco solo cuando el píxel correspondiente en ambas imágenes de entrada es blanco, de lo contrario el píxel de salida es negro. En lugar de realizar la operación píxel por píxel, podemos calcular la unión de forma más eficiente aprovechando la capacidad del quadtree para representar múltiples píxeles con un solo nodo. Para los fines de la discusión a continuación, si un subárbol contiene píxeles tanto negros como blancos, diremos que la raíz de ese subárbol está coloreada de gris.

El algoritmo funciona recorriendo los dos quadtrees de entrada (${\displaystyle T_{1}}$y${\displaystyle T_{2}}$) mientras se construye el quadtree de salida${\displaystyle T}$De manera informal, el algoritmo es el siguiente. Consideremos los nodos${\displaystyle v_{1}\in T_{1}}$y ${\displaystyle v_{2}\in T_{2}}$correspondiente a la misma región en las imágenes.

• Si${\displaystyle v_{1}}$o${\displaystyle v_{2}}$es negro, el nodo correspondiente se crea en${\displaystyle T}$y es de color negro. Si solo uno de ellos es negro y el otro es gris, el nodo gris contendrá un subárbol debajo. No es necesario recorrer este subárbol.
• Si${\displaystyle v_{1}}$(respectivamente,${\displaystyle v_{2}}$) es blanco,${\displaystyle v_{2}}$(respectivamente,${\displaystyle v_{1}}$) y el subárbol que se encuentra debajo (si lo hay) se copia a${\displaystyle T}$.
• Si ambos${\displaystyle v_{1}}$y${\displaystyle v_{2}}$son grises, entonces los hijos correspondientes de${\displaystyle v_{1}}$y${\displaystyle v_{2}}$se consideran.

Aunque este algoritmo funciona, por sí solo no garantiza un quadtree de tamaño mínimo. Por ejemplo, consideremos el resultado si unimos un tablero de ajedrez (donde cada casilla es un píxel) de tamaño ${\displaystyle 2^{k}\times 2^{k}}$con su complemento. El resultado es un cuadrado negro gigante que debería estar representado por un quadtree con solo el nodo raíz (coloreado de negro), pero en su lugar el algoritmo produce un árbol 4-ario completo de profundidad${\displaystyle k}$Para solucionar esto, realizamos un recorrido ascendente del quadtree resultante donde verificamos si los cuatro nodos hijos tienen el mismo color, en cuyo caso reemplazamos su padre con una hoja del mismo color. ^{[ 5 ]}

La intersección de dos imágenes se realiza mediante un algoritmo casi idéntico. Una forma de entender la intersección es considerarla como una unión de los píxeles blancos . Por lo tanto, para realizar la intersección, intercambiamos las referencias a blanco y negro en el algoritmo de unión.

Consideremos dos píxeles negros vecinos en una imagen binaria. Son adyacentes si comparten un borde horizontal o vertical delimitador. En general, dos píxeles negros están conectados si se puede llegar a uno desde el otro moviéndose solo a píxeles adyacentes (es decir, hay un camino de píxeles negros entre ellos donde cada par consecutivo es adyacente). Cada conjunto máximo de píxeles negros conectados es un componente conectado . Usando la representación de quadtree de imágenes, Samet ^{[ 23 ]} mostró cómo podemos encontrar y etiquetar estos componentes conectados en un tiempo proporcional al tamaño del quadtree. ^{[ 5 ] [ 24 ]} Este algoritmo también se puede usar para colorear polígonos.

El algoritmo funciona en tres pasos:

1. establecer las relaciones de adyacencia entre píxeles negros
2. procesar las relaciones de equivalencia del primer paso para obtener una etiqueta única para cada componente conectado
3. etiqueta los píxeles negros con la etiqueta asociada a su componente conectado.

Para simplificar la explicación, supongamos que los hijos de un nodo en el quadtree siguen el orden Z (SO, NO, SE, NE). Dado que podemos contar con esta estructura, para cualquier celda sabemos cómo navegar por el quadtree para encontrar las celdas adyacentes en los diferentes niveles de la jerarquía.

El primer paso se realiza mediante un recorrido en postorden del quadtree. Para cada hoja negra${\displaystyle v}$observamos el nodo o nodos que representan las celdas que son vecinas del norte y vecinas del este (es decir, las celdas del norte y del este que comparten bordes con la celda de${\displaystyle v}$). Dado que el árbol está organizado en orden Z , tenemos el invariante de que los vecinos del sur y del oeste ya han sido considerados y tenidos en cuenta. Sea el vecino del norte o del este que se está considerando actualmente.${\displaystyle u}$. Si${\displaystyle u}$representa píxeles negros:

• Si solo uno de${\displaystyle u}$o${\displaystyle v}$tiene una etiqueta, asigne esa etiqueta a la otra celda
• Si ninguno de ellos tiene etiquetas, crea una y asígnala a ambos.
• Si${\displaystyle u}$y${\displaystyle v}$Tienen etiquetas diferentes, registre esta equivalencia de etiquetas y continúe.

El segundo paso se puede realizar utilizando la estructura de datos de unión-búsqueda . ^{[ 25 ]} Comenzamos con cada etiqueta única como un conjunto separado. Para cada relación de equivalencia observada en el primer paso, unimos los conjuntos correspondientes. Posteriormente, cada conjunto restante distinto se asociará con un componente conexo distinto en la imagen.

El tercer paso realiza otro recorrido en postorden. Esta vez, para cada nodo negro${\displaystyle v}$utilizamos la operación de búsqueda de union-find (con la antigua etiqueta de${\displaystyle v}$) para encontrar y asignar${\displaystyle v}$su nueva etiqueta (asociada con el componente conectado del cual${\displaystyle v}$es parte).

Esta sección resume un capítulo de un libro de Har-Peled y de Berg et al. ^{[ 26 ] [ 27 ]}

La generación de mallas consiste esencialmente en la triangulación de un conjunto de puntos, sobre el cual se puede realizar un procesamiento posterior. Por ello, es deseable que la triangulación resultante posea ciertas propiedades (como no uniformidad, triángulos que no sean demasiado delgados, triángulos grandes en áreas dispersas y triángulos pequeños en áreas densas, etc.) para que el procesamiento posterior sea más rápido y menos propenso a errores. Los quadtrees construidos a partir del conjunto de puntos pueden utilizarse para crear mallas con estas propiedades deseadas.

Consideremos una hoja del quadtree y su celda correspondiente.${\displaystyle v}$Decimos:${\displaystyle v}$está equilibrado (para la generación de malla) si los lados de la celda son intersectados por los puntos de esquina de las celdas vecinas como máximo una vez en cada lado. Esto significa que los niveles de quadtree de las hojas adyacentes a${\displaystyle v}$difieren como máximo en uno del nivel de${\displaystyle v}$Cuando esto se cumple para todas las hojas, decimos que todo el quadtree está equilibrado (para la generación de la malla).

Consideremos la célula${\displaystyle v}$y el${\displaystyle 5\times 5}$vecindario de celdas del mismo tamaño centrado en${\displaystyle v}$. Llamamos a este vecindario el clúster extendido . Decimos que el quadtree está bien equilibrado si está equilibrado y para cada hoja${\displaystyle u}$que contiene un punto del conjunto de puntos, su clúster extendido también está en el quadtree y el clúster extendido no contiene ningún otro punto del conjunto de puntos.

La creación de la malla se realiza de la siguiente manera:

1. Construye un quadtree con los puntos de entrada.
2. Asegúrese de que el quadtree esté equilibrado. Para cada hoja, si hay un vecino demasiado grande, subdivídalo. Este proceso se repite hasta que el árbol esté equilibrado. Además, nos aseguramos de que, para una hoja con un punto, los nodos de su clúster extendido estén presentes en el árbol.
3. Por cada nodo hoja${\displaystyle v}$que contiene un punto, si el clúster extendido contiene otro punto, subdividimos aún más el árbol y lo reequilibramos según sea necesario. Si necesitáramos subdividir, para cada hijo${\displaystyle u}$de${\displaystyle v}$nos aseguramos de que los nodos de${\displaystyle u}$El clúster extendido se encuentra en el árbol (y se reequilibra según sea necesario).
4. Repita el paso anterior hasta que el árbol esté bien equilibrado.
5. Transforma el quadtree en una triangulación.

Consideramos los vértices de las celdas del árbol como vértices en nuestra triangulación. Antes de la transformación, tenemos varias cajas con puntos en algunas de ellas. La transformación se realiza de la siguiente manera: para cada punto, se deforma la esquina más cercana de su celda para que coincida con él y se triangulan los cuatro cuadriláteros resultantes para formar triángulos bien definidos (para más detalles sobre cómo se forman los triángulos bien definidos, consulte el capítulo 12 de Har-Peled ^{[ 26 ]} ).

Los cuadrados restantes se triangulan según unas reglas sencillas. Para cada cuadrado regular (sin puntos en su interior ni vértices en sus lados), se introduce la diagonal. Debido a la forma en que separamos los puntos con la propiedad de equilibrio adecuado, ningún cuadrado con un vértice que interseca un lado es un cuadrado deformado. Por lo tanto, podemos triangular cuadrados con vértices que se intersecan de la siguiente manera. Si hay un lado que se interseca, el cuadrado se convierte en tres triángulos al añadir las diagonales largas que conectan la intersección con los vértices opuestos. Si hay cuatro lados que se intersecan, dividimos el cuadrado por la mitad añadiendo una arista entre dos de las cuatro intersecciones, y luego conectamos estos dos extremos con los dos puntos de intersección restantes. Para los demás cuadrados, introducimos un punto en el centro y lo conectamos con los cuatro vértices del cuadrado, así como con cada punto de intersección.

Al final, tenemos una bonita malla triangulada de nuestro conjunto de puntos construida a partir de un quadtree.

El siguiente pseudocódigo muestra una forma de implementar un quadtree que solo maneja puntos. Existen otros enfoques disponibles.

Se supone que estas estructuras se utilizan.

// Objeto de coordenadas simple para representar puntos y vectores struct XY { float x ; float y ; function __construct ( float _x , float _y ) {...} } // Caja delimitadora alineada con los ejes con media dimensión y centro struct AABB { XY center ; float halfDimension ; function __construct ( XY _center , float _halfDimension ) {...} function containsPoint ( XY point ) {...} function intersectsAABB ( AABB other ) {...} }

Esta clase representa tanto un árbol cuádruple como el nodo donde tiene su raíz.

clase QuadTree { // Constante arbitraria para indicar cuántos elementos se pueden almacenar en este nodo de árbol cuaternario constant int QT_NODE_CAPACITY = 4 ; // Caja delimitadora alineada con los ejes almacenada como un centro con semidimensiones // para representar los límites de este árbol cuaternario AABB boundary ; // Puntos en este nodo de árbol cuaternario Array of XY [ size = QT_NODE_CAPACITY ] points ; // Hijos QuadTree * northWest ; QuadTree * northEast ; QuadTree * southWest ; QuadTree * southEast ; // Métodos function __construct ( AABB _boundary ) {...} function insert ( XY p ) {...} function subdivide () {...} // crea cuatro hijos que dividen completamente este cuaternario en cuatro cuaternarios de igual área function queryRange ( AABB range ) {...} }

El siguiente método inserta un punto en el cuadrilátero apropiado de un quadtree, dividiéndolo si es necesario.

clase QuadTree { ... // Inserta un punto en el QuadTree función insert ( XY p ) { // Ignora los objetos que no pertenecen a este quad tree if ( ! boundary . containsPoint ( p )) return false ; // el objeto no se puede agregar // Si hay espacio en este quad tree y no tiene subdivisiones, agrega el objeto aquí if ( points . size < QT_NODE_CAPACITY && northWest == null ) { points . append ( p ); return true ; } // De lo contrario, subdivide y luego agrega el punto al nodo que lo acepte if ( northWest == null ) subdivide (); // Tenemos que agregar los puntos/datos contenidos en este quad array a los nuevos quads si solo queremos // que el último nodo contenga los datos if ( northWest -> insert ( p )) return true ; if ( northEast -> insert ( p )) return true ; if ( southWest -> insert ( p )) return true ; if ( southEast- > insert ( p )) return true ; // De lo contrario, el punto no se puede insertar por alguna razón desconocida (esto nunca debería ocurrir) return false ; } }

El siguiente método encuentra todos los puntos contenidos dentro de un rango.

clase QuadTree { ... // Encuentra todos los puntos que aparecen dentro de un rango function queryRange ( AABB range ) { // Prepara una matriz de resultados Array of XY pointsInRange ; // Aborta automáticamente si el rango no interseca este cuadrilátero if ( ! boundary . intersectsAABB ( range )) return pointsInRange ; // lista vacía // Comprueba los objetos en este nivel de cuadrilátero for ( int p = 0 ; p < points . size ; p ++ ) { if ( range . containsPoint ( points [ p ])) pointsInRange . append ( points [ p ]); } // Termina aquí, si no hay hijos if ( northWest == null ) return pointsInRange ; // De lo contrario, agrega los puntos de los hijos pointsInRange . appendArray ( northWest -> queryRange ( range )); pointsInRange . appendArray ( northEast -> queryRange ( range )); pointsInRange . appendArray ( southWest - > queryRange ( range )); pointsInRange.appendArray ( southEast - > queryRange ( range )); return pointsInRange ; } }

• Refinamiento adaptativo de la malla
• Particionamiento binario del espacio
• Teselado binario
• árbol k -d
• Octree
• Árbol R
• Árbol UB
• base de datos espacial
• Subpavimentación
• Curva de orden Z

Los estudios de Aluru ^{[ 5 ]} y Samet ^{[ 24 ] [ 18 ]} ofrecen una buena visión general de los quadtrees.

1. Raphael Finkel y JL Bentley (1974). "Árboles cuádruples: una estructura de datos para la recuperación en claves compuestas". Acta Informatica . 4 (1): 1– 9. doi : 10.1007/BF00288933 . S2CID  33019699 .
2. Mark de Berg , Marc van Kreveld , Mark Overmars y Otfried Schwarzkopf (2000). Geometría computacional (2ª edición revisada). Springer-Verlag . ISBN 3-540-65620-0.{{cite book}}: CS1 maint: nombres múltiples: lista de autores ( enlace ) Capítulo 14: Quadtrees: págs. 291–306.
3. Samet, Hanan ; Webber, Robert (julio de 1985). "Almacenamiento de una colección de polígonos mediante quadtrees" (PDF) . Archivado del original (PDF) el 17 de junio de 2012. Recuperado el 23 de marzo de 2012 .