Árbol cuaternario

Estructura de datos de árbol en la que cada nodo interno tiene exactamente cuatro hijos, para particionar un área 2D

Un árbol cuaternario de regiones puntuales con datos puntuales. Capacidad del depósito: 1.

Compresión de una imagen en árbol cuaternario paso a paso. A la izquierda se muestra la imagen comprimida con los cuadros delimitadores del árbol, mientras que a la derecha se muestra solo la imagen comprimida.

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

Las regiones subdivididas pueden ser cuadradas o rectangulares, o pueden tener formas arbitrarias. Esta estructura de datos fue denominada quadtree por Raphael Finkel y JL Bentley en 1974. ^[1] Una partición similar también se conoce como Q-tree .

Todas las formas de árboles cuadráticos comparten algunas características comunes:

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

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

Tipos

Un ejemplo de un quadtree de partición espacial binaria recursiva para un índice 2D.

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

Árbol cuaternario de regiones

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., con cada nodo hoja que contiene datos correspondientes a una subregión específica. Cada nodo del árbol tiene exactamente cuatro hijos o no tiene hijos (un nodo hoja). La altura de los quadtrees que siguen esta estrategia de descomposición (es decir, subdividir los subcuadrantes siempre que haya datos interesantes en el subcuadrante para el que se desea un mayor refinamiento) es sensible y depende de la distribución espacial de las áreas interesantes en el espacio que se está descomponiendo. El quadtree de región es un tipo de trie .

Un árbol cuaternario de regiones con una profundidad de n puede utilizarse para representar una imagen que consta de 2 ⁿ × 2 ⁿ píxeles, donde cada valor de píxel es 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 todos 0 o 1, se subdivide. En esta aplicación, cada nodo de hoja representa un bloque de píxeles que son todos 0 o todos 1. Observe el potencial ahorro en términos de espacio cuando estos árboles se utilizan para almacenar imágenes; las imágenes suelen tener muchas regiones de tamaño considerable que tienen el mismo valor de color en todas partes. En lugar de almacenar una gran matriz 2D de cada píxel de la imagen, un árbol cuaternario puede capturar la misma información potencialmente a muchos niveles de división más altos que las celdas de tamaño de resolución de píxel que necesitaríamos de otro modo. La resolución del árbol y el tamaño general están limitados por los tamaños de píxel e imagen.

Un árbol cuaternario de regiones también se puede utilizar como representación de resolución variable de un campo de datos. Por ejemplo, las temperaturas de un área se pueden almacenar como un árbol cuaternario, en el que cada nodo hoja almacena la temperatura promedio de la subregión que representa.

Punto cuadriárbol

El árbol cuaternario de puntos ^[3] es una adaptación de un árbol binario que se utiliza para representar datos puntuales bidimensionales. Comparte las características de todos los árboles cuaternarios, 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, y normalmente funciona en tiempo O(log n) . Vale la pena mencionar los árboles cuaternarios de puntos por su integridad, pero han sido superados por los árboles k -d como herramientas para la búsqueda binaria generalizada. ^[4]

Los árboles de puntos cuadráticos se construyen de la siguiente manera. Dado el siguiente punto que se va a insertar, buscamos la celda en la que se encuentra y lo añadimos al árbol. El nuevo punto se añade de forma que la celda que lo contiene se divide en cuadrantes por las líneas verticales y horizontales que pasan por el punto. En consecuencia, 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 decide por el orden de inserción de los puntos, la altura del árbol es sensible y depende del orden de inserción. Insertar en un orden "incorrecto" puede dar lugar a un árbol con una altura lineal en relación con el número de puntos de entrada (momento en el que se convierte en una lista enlazada). Si el conjunto de puntos es estático, se puede realizar un preprocesamiento para crear un árbol con una altura equilibrada.

Estructura de nodo para un árbol cuaternario de puntos

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 ("izquierdo" y "derecho") como en un árbol binario común. Además, una clave suele descomponerse 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 expresada como coordenadas x, y
  • valor; por ejemplo un nombre

Árbol cuaternario de regiones puntuales (PR)

Los árboles cuaternarios de regiones puntuales (PR) ^{[5] [6]} son ​​muy similares a los árboles cuaternarios de regiones. La diferencia es el tipo de información almacenada sobre las celdas. En un árbol cuaternario de regiones, se almacena un valor uniforme que se aplica a toda el área de la celda de una hoja. Sin embargo, las celdas de un árbol cuaternario 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 árbol cuaternario de puntos, el árbol cuaternario PR también puede tener una altura lineal cuando se le da un conjunto "malo".

Árbol cuadrilongo de borde

Los árboles cuaternarios de aristas ^{[7] [8]} (de forma muy similar a los árboles cuaternarios 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 solo segmento de línea por celda. Cerca de las esquinas o los vértices, los árboles cuaternarios de aristas continuarán dividiéndose hasta que alcancen su nivel máximo de descomposición. Esto puede generar árboles extremadamente desequilibrados que pueden anular el propósito de la indexación.

Mapa poligonal (PM) quadtree

El quadtree de mapa poligonal (o PM Quadtree) es una variación de quadtree que se utiliza para almacenar colecciones de polígonos que pueden estar degenerados (lo que significa que tienen vértices o aristas aislados). ^{[9] [10]} Una gran diferencia entre los quadtrees PM 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 dentro de cada nodo negro. Los árboles cuaternarios PM3 pueden almacenar cualquier cantidad de aristas que no se intersequen y, como máximo, un punto. Los árboles cuaternarios PM2 son iguales a los árboles cuaternarios PM3, excepto que todas las aristas deben compartir el mismo punto final. Por último, 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, pero no se puede tener un punto y un conjunto de aristas que no contengan el punto.

Árboles cuadráticos comprimidos

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

Si tuviéramos que almacenar cada nodo correspondiente a una celda subdividida, podríamos terminar almacenando muchos nodos vacíos. Podemos reducir el tamaño de estos árboles dispersos almacenando solo subárboles cuyas hojas tengan datos interesantes (es decir, "subárboles importantes"). En realidad, podemos reducir el tamaño aún más. Cuando solo mantenemos subárboles importantes, el proceso de poda puede dejar caminos largos 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 al comienzo de este camino (y asociar algunos metadatos con él para representar los nodos eliminados) y adjuntar el subárbol enraizado en su extremo a . Todavía es posible que estos árboles comprimidos tengan una altura lineal cuando se les dan puntos de entrada "malos". ${\displaystyle u}$ ${\displaystyle u}$

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

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

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

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

1. Encuentre la celda existente en el árbol comprimido que viene antes en el orden Z. Llame a esta celda . ${\displaystyle q}$ ${\displaystyle v}$
2. Si , devuelve . ${\displaystyle q\in v}$ ${\displaystyle v}$
3. De lo contrario, encuentre cuál habría sido el ancestro común más bajo del punto y la celda en un árbol cuaternario sin comprimir. Llame a este ancestro celda . ${\displaystyle q}$ ${\displaystyle v}$ ${\displaystyle u}$
4. Encuentre la celda existente en el árbol comprimido que viene antes en el orden Z y devuélvala. ${\displaystyle u}$

Sin entrar en detalles específicos, para realizar inserciones y eliminaciones primero ubicamos un punto para lo que queremos insertar/eliminar y luego lo insertamos/eliminamos. Se debe tener cuidado de remodelar el árbol según corresponda, creando y eliminando nodos según sea necesario.

Algunos usos comunes de los quadtrees

• Representación de imágenes
  
• Procesamiento de imágenes
• Generación de mallas ^[12]
• Indexación espacial , consultas de ubicación de puntos y consultas de rango
• Detección eficiente de colisiones en dos dimensiones
• Ver la selección de datos de terreno del frustum
• Almacenamiento de datos dispersos, como información de formato para una hoja de cálculo ^[13] o para algunos cálculos matriciales ^{[ cita requerida ]}
• Solución de campos multidimensionales ( dinámica de fluidos computacional , electromagnetismo )
• Programa de simulación del Juego de la Vida de Conway . ^[14]
• Estimación del estado ^[15]
• Los árboles cuaternarios también se utilizan en el área de análisis de imágenes fractales.
• Conjuntos disjuntos máximos

Procesamiento de imágenes mediante quadtrees

Los árboles cuaternarios, en particular el árbol cuaternario de regiones, se han adaptado bien a las aplicaciones de procesamiento de imágenes. Limitaremos nuestro análisis a los datos de imágenes binarias, aunque los árboles cuaternarios de regiones y las operaciones de procesamiento de imágenes que se realizan en ellos son igualmente adecuados para imágenes en color. ^{[4] [16]}

Unión/intersección de imágenes

Una de las ventajas de usar quadtrees para la manipulación de imágenes es que las operaciones de unión e intersección de conjuntos se pueden realizar de forma sencilla y rápida. ^{[4] [17] [18] [19] [20]} 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 hacer 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 blancos y negros, diremos que la raíz de ese subárbol está coloreada de gris.

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

• Si o es negro, se crea el nodo correspondiente y se colorea de 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. ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$ ${\displaystyle T}$
• Si (respectivamente, ) es blanco, (respectivamente, ) y el subárbol debajo de él (si hay alguno) se copia a . ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$ ${\displaystyle v_{2}}$ ${\displaystyle v_{1}}$ ${\displaystyle T}$
• Si ambos son grises, entonces se consideran los hijos correspondientes de y . ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$

Si bien este algoritmo funciona, no garantiza por sí mismo un árbol cuaternario de tamaño mínimo. Por ejemplo, considere el resultado si uniéramos un tablero de ajedrez (donde cada mosaico es un píxel) de tamaño con su complemento. El resultado es un cuadrado negro gigante que debería estar representado por un árbol cuaternario con solo el nodo raíz (de color negro), pero en cambio el algoritmo produce un árbol cuaternario completo de profundidad . Para solucionar esto, realizamos un recorrido de abajo hacia arriba del árbol cuaternario resultante donde verificamos si los cuatro nodos hijos tienen el mismo color, en cuyo caso reemplazamos su padre con una hoja del mismo color. ^[4] ${\displaystyle 2^{k}\times 2^{k}}$ ${\displaystyle k}$

La intersección de dos imágenes es prácticamente el mismo algoritmo. Una forma de pensar en la intersección de las dos imágenes es que estamos realizando una unión con respecto a los píxeles blancos . Por lo tanto, para realizar la intersección intercambiamos las menciones de blanco y negro en el algoritmo de unión.

Etiquetado de componentes conectados

Considere 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 los 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 imágenes en quadtree, Samet ^[21] mostró cómo podemos encontrar y etiquetar estos componentes conectados en un tiempo proporcional al tamaño del quadtree. ^{[4] [22]} 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 desde el 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 el análisis, supongamos que los hijos de un nodo en el árbol cuaternario siguen el orden Z (SO, NO, SE, NE). Como podemos contar con esta estructura, para cualquier celda sabemos cómo navegar por el árbol cuaternario para encontrar las celdas adyacentes en los diferentes niveles de la jerarquía.

El primer paso se logra con un recorrido de orden posterior del árbol cuaternario. Para cada hoja negra, observamos el nodo o los nodos que representan 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 ). Dado que el árbol está organizado en orden Z , tenemos la invariante de que ya se han tenido en cuenta y atendido a los vecinos del sur y del oeste. Sea . Si representa píxeles negros: ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle u}$

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

El segundo paso se puede lograr utilizando la estructura de datos union-find . ^[23] Comenzamos con cada etiqueta única como un conjunto separado. Para cada relación de equivalencia observada en el primer paso, unimos los conjuntos correspondientes. Luego, cada conjunto restante distinto se asociará con un componente conectado distinto en la imagen.

El tercer paso realiza otro recorrido posterior al orden. Esta vez, para cada nodo negro, utilizamos la operación find de union-find (con la etiqueta anterior de ) para buscar y asignar su nueva etiqueta (asociada con el componente conectado del cual es parte). ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$

Generación de mallas mediante árboles cuaternarios

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

La generación de mallas es esencialmente la triangulación de un conjunto de puntos para el cual se puede realizar un procesamiento posterior. Como tal, es deseable que la triangulación resultante tenga ciertas propiedades (como falta de 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 árboles cuádruples creados a partir del conjunto de puntos se pueden utilizar para crear mallas con estas propiedades deseadas.

Una hoja equilibrada tiene como máximo una esquina en cada lado.

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

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

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

1. Construya un quadtree en los puntos de entrada.
2. Asegúrese de que el árbol cuaternario esté equilibrado. Para cada hoja, si hay un vecino que es demasiado grande, subdivida el vecino. Esto se repite hasta que el árbol esté equilibrado. También nos aseguramos de que, para una hoja con un punto en ella, los nodos del grupo extendido de cada hoja estén en el árbol.
3. Para cada nodo de hoja 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 tuviéramos que subdividir, para cada hijo de nos aseguramos de que los nodos del clúster extendido de estén en el árbol (y lo reequilibramos según sea necesario). ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$
4. Repita el paso anterior hasta que el árbol esté bien equilibrado.
5. Transformar el quadtree en una triangulación.

Consideramos los puntos de las esquinas de las celdas del árbol como vértices en nuestra triangulación. Antes del paso de transformación, tenemos un montón de cajas con puntos en algunas de ellas. El paso de transformación se realiza de la siguiente manera: para cada punto, deformamos la esquina más cercana de su celda para que se encuentre con él y triangulamos los cuatro cuadrángulos resultantes para formar triángulos "agradables" (el lector interesado puede consultar el capítulo 12 de Har-Peled ^[24] para obtener más detalles sobre qué hace que los triángulos sean "agradables").

Los cuadrados restantes se triangulan de acuerdo con algunas reglas simples. Para cada cuadrado regular (sin puntos dentro ni puntos de esquina en sus lados), introduzca la diagonal. Debido a la forma en que separamos los puntos con la propiedad de buen equilibrio, ningún cuadrado con una esquina que interseca un lado es uno que esté deformado. Como tal, podemos triangular cuadrados con esquinas que se intersecan de la siguiente manera. Si hay un lado intersecado, el cuadrado se convierte en tres triángulos agregando las diagonales largas que conectan la intersección con las esquinas opuestas. Si hay cuatro lados intersecados, dividimos el cuadrado por la mitad agregando una arista entre dos de las cuatro intersecciones y luego conectamos estos dos puntos finales a los dos puntos de intersección restantes. Para los otros cuadrados, introducimos un punto en el medio y lo conectamos a las cuatro esquinas del cuadrado, así como a cada punto de intersección.

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

Pseudocódigo

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

Prerrequisitos

Se supone que se utilizan estas estructuras.

 // Objeto de coordenadas simple para representar puntos y vectores struct XY { float x ; float y ; function __construct ( float _x , float _y ) {...} } // Cuadro delimitador alineado al eje 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 ) {...} }                                        

Clase QuadTree

Esta clase representa tanto un árbol cuádruple como el nodo donde está enraizado.

 clase QuadTree { // Constante arbitraria para indicar cuántos elementos se pueden almacenar en este nodo de árbol cuádruple constante int QT_NODE_CAPACITY = 4 ; // Cuadro delimitador alineado con el eje almacenado como un centro con medias dimensiones // para representar los límites de este árbol cuádruple AABB bound ; // Puntos en este nodo de árbol cuádruple Matriz de puntos XY [ size = QT_NODE_CAPACITY ] ; // 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 cuadrilátero en cuatro cuadriláteros de igual área function queryRange ( AABB range ) {...} }                                                   

Inserción

El siguiente método inserta un punto en el cuadrante apropiado de un árbol cuadrático, dividiéndolo si es necesario.

 class QuadTree { ... // Insertar un punto en el QuadTree function insert ( XY p ) { // Ignorar objetos que no pertenecen a este árbol cuádruple if ( ! bounder . containsPoint ( p )) return false ; // no se puede agregar un objeto // Si hay espacio en este árbol cuádruple y no tiene subdivisiones, agregue el objeto aquí if ( points . size < QT_NODE_CAPACITY && northWest == null ) { points . append ( p ); return true ; } // De lo contrario, subdivida y luego agregue el punto a cualquier nodo que lo acepte if ( northWest == null ) subdivide (); // Tenemos que agregar los puntos/datos contenidos en esta matriz cuádruple a los nuevos cuádruples 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 suceder) return false ; } }                                                              

Rango de consulta

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

 class QuadTree { ... // Encuentra todos los puntos que aparecen dentro de un rango function queryRange ( AABB range ) { // Prepara una matriz de resultados Matriz de XY pointsInRange ; // Aborta automáticamente si el rango no interseca este cuadrilátero if ( ! bounder . intersectsAABB ( range )) return pointsInRange ; // lista vacía // Verifica 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 ( suroeste -> rango de consulta ( rango )); puntosEnRango . appendArray ( sureste -> rango de consulta ( rango )); devolver puntosEnRango ; } }                                                        

Véase también

• Refinamiento de malla adaptativo
• Partición del espacio binario
• Mosaico binario
• árbol k -d
• Octárbol
• Árbol R
• Árbol UB
• Base de datos espacial
• Subpavimentación
• Curva de orden Z

Referencias

Los estudios de Aluru ^[4] y Samet ^{[22] [16]} ofrecen una buena descripción general de los árboles cuaternarios.

Notas

1. Finkel, RA; Bentley, JL (1974). "Árboles cuádruples: una estructura de datos para la recuperación de claves compuestas". Acta Informatica . 4 (1): 1–9. doi :10.1007/BF00288933. S2CID  33019699 . Consultado el 6 de noviembre de 2019 .
2. Milan Sonka, Vaclav Hlavac, Roger Boyle. "Procesamiento de imágenes, análisis y visión artificial". 2014. págs. 108-109.
3. Finkel, RA; Bentley, JL (1974). "Árboles cuádruples: una estructura de datos para la recuperación de claves compuestas". Acta Informatica . 4 . Springer-Verlag: 1–9. doi :10.1007/bf00288933. S2CID  33019699.
4. Aluru, S. (2004). "Árboles cuádruples y ocárboles". En D. Mehta y S. Sahni (ed.). Manual de estructuras de datos y aplicaciones . Chapman y Hall/CRC. págs. 19-1-19-26. ISBN 9781584884354.
5. Orenstein, JA (1982). "Intentos multidimensionales utilizados para la búsqueda asociativa". Information Processing Letters . 14 (4). Elsevier: 150–157. doi :10.1016/0020-0190(82)90027-8.
6. Samet, H. (1984). "El árbol cuádruple y las estructuras de datos jerárquicas relacionadas" (PDF) . Encuestas de computación de la ACM . 16 (2). ACM: 187–260. doi :10.1145/356924.356930. S2CID  10319214.
7. Warnock, JE (1969). "Un algoritmo de superficie oculta para imágenes de medios tonos generadas por computadora". Departamento de Ciencias de la Computación, Universidad de Utah . TR 4-15.
8. Schneier, M. (1981). "Dos representaciones de características lineales jerárquicas: pirámides de aristas y árboles cuadráticos de aristas". Procesamiento de imágenes y gráficos por computadora . 17 (3). Elsevier: 211–224. doi :10.1016/0146-664X(81)90002-2.
9. Hanan Samet y Robert Webber. "Almacenamiento de una colección de polígonos mediante árboles cuaternarios". ACM Transactions on Graphics, julio de 1985: 182-222. InfoLAB . Web. 23 de marzo de 2012
10. Nelson, RC; Samet, H. (1986). "Una representación jerárquica consistente para datos vectoriales". ACM SIGGRAPH Computer Graphics . 20 (4): 197–206. doi : 10.1145/15886.15908 .
11. Har-Peled, S. (2011). "Quadtrees - Hierarchical Grids". Algoritmos de aproximación geométrica . Encuestas y monografías matemáticas, vol. 173, American mathematics society.
12. Wanta, Damian; Smolik, Waldemar T.; Kryszyn, Jacek; Wróblewski, Przemysław; Midura, Mateusz (2021). "Un método de volumen finito que utiliza una malla estructurada no uniforme de árbol cuádruple para modelado en tomografía de capacitancia eléctrica". Actas de la Academia Nacional de Ciencias, India Sección A . 92 (3): 443–452. doi : 10.1007/s40010-021-00748-7 . S2CID  244224810.
13. Sestoft, Peter (2014). Tecnología de implementación de hojas de cálculo: conceptos básicos y extensiones . The MIT Press. pp. 60–63. ISBN 9780262526647.
14. Tomas G. Rokicki (1 de abril de 2006). "Un algoritmo para comprimir el espacio y el tiempo" . Consultado el 20 de mayo de 2009 .
15. Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Árboles de densidad para una estimación eficiente de estados no lineales , Actas de la 13.ª Conferencia internacional sobre fusión de información, Edimburgo, Reino Unido, julio de 2010.
16. Samet, H. (1989). "Estructuras jerárquicas de datos espaciales". Simposio sobre grandes bases de datos espaciales : 191–212.
17. Hunter, GM (1978). Computación eficiente y estructuras de datos para gráficos . Tesis doctoral, Departamento de Ingeniería Eléctrica y Ciencias de la Computación, Universidad de Princeton.
18. Hunter, GM; Steiglitz, K. (1979). "Operaciones sobre imágenes utilizando árboles cuádruples". IEEE Transactions on Pattern Analysis and Machine Intelligence . 2 (2): 145–153. doi :10.1109/tpami.1979.4766900. PMID  21868843. S2CID  2544535.
19. Schneier, M. (1981). "Cálculos de propiedades geométricas utilizando árboles cuaternarios". Procesamiento de imágenes y gráficos por computadora . 16 (3): 296–302. doi :10.1016/0146-664X(81)90042-3.
20. Mehta, Dinesh (2007). Manual de estructuras y aplicaciones de datos . Chapman y Hall/CRC Press. pág. 397.
21. Samet, H. (1981). "Etiquetado de componentes conectados utilizando árboles cuádruples". Revista de la ACM . 28 (3): 487–501. CiteSeerX 10.1.1.77.2573 . doi :10.1145/322261.322267. S2CID  17485118. 
22. Samet, H. (1988). "Una descripción general de los quadtrees, octrees y estructuras de datos jerárquicas relacionadas". En Earnshaw, RA (ed.). Fundamentos teóricos de gráficos por computadora y CAD . Springer-Verlag. págs. 51–68.
23. Tarjan, RE (1975). "Eficiencia de un algoritmo de unión de conjuntos bueno pero no lineal" (PDF) . Revista de la ACM . 22 (2): 215–225. doi :10.1145/321879.321884. hdl : 1813/5942 . S2CID  11105749.
24. Har-Peled, S. (2011). "Buenas triangulaciones y mallas". Algoritmos de aproximación geométrica . Encuestas y monografías matemáticas, vol. 173, American mathematics society.
25. de Berg, M.; Cheong, O.; van Kreveld, M.; Overmars, MH (2008). "Generación de malla no uniforme mediante árboles cuádruples". Algoritmos y aplicaciones de geometría computacional (3.ª ed.). Springer-Verlag.

Referencias generales

1. Raphael Finkel y JL Bentley (1974). "Árboles cuádruples: una estructura de datos para la recuperación de 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: varios nombres: lista de autores ( enlace )Capítulo 14: Árboles cuaternarios: págs. 291–306.
3. Samet, Hanan ; Webber, Robert (julio de 1985). "Almacenamiento de una colección de polígonos mediante árboles cuaternarios" (PDF) . Consultado el 23 de marzo de 2012 .