árbol cuádruple

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

Un árbol cuádruple de región de puntos con datos de puntos. Capacidad del cubo 1.

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

Un quadtree es una estructura de datos 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 subdividié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 quadtrees comparten algunas características comunes:

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

Un árbol-pirámide ( pirámide T ) es un árbol "completo"; cada nodo de la pirámide T tiene cuatro nodos secundarios 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 en una pirámide de á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

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

Árbol cuádruple de región

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 árboles cuádruples que siguen esta estrategia de descomposición (es decir, subdividir subcuadrantes siempre que haya datos interesantes en el subcuadrante para el cual se desea mayor refinamiento) es sensible y dependiente de la distribución espacial de áreas interesantes en el espacio que se está descomponiendo. La región quadtree es un tipo de trie .

Se puede utilizar un árbol cuádruple de región con una profundidad de n 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 cualquier 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. Tenga en cuenta los ahorros potenciales 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 2-D de cada píxel de la imagen, un árbol cuádruple puede capturar la misma información potencialmente muchos niveles de división más altos que las celdas de tamaño de resolución de píxeles que de otro modo necesitaríamos. La resolución del árbol y el tamaño general están limitados por los tamaños de píxeles y de imagen.

También se puede utilizar un árbol cuádruple de región como representación de resolución variable de un campo de datos. Por ejemplo, las temperaturas en un área se pueden almacenar como un árbol cuádruple, donde cada nodo de hoja almacena la temperatura promedio en la subregión que representa.

Punto cuádruple

El quadtree de puntos ^[3] 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 verdadero árbol ya que el centro de una subdivisión siempre está en un punto. A menudo es muy eficiente para comparar puntos de datos ordenados bidimensionales y generalmente opera en tiempo O (log n) . Vale la pena mencionar los árboles cuádruples de puntos para que sean completos, pero han sido superados por los árboles k -d como herramientas para la búsqueda binaria generalizada. ^[4]

Los quadtrees de puntos se construyen de la siguiente manera. Dado el siguiente punto a insertar, buscamos la celda en la que se encuentra y la agregamos al árbol. El nuevo punto se agrega de manera que la celda que lo contiene quede dividida 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 "malo" puede generar un árbol de altura lineal en el número de puntos de entrada (en cuyo punto se convierte en una lista vinculada). Si el conjunto de puntos es estático, se puede realizar un preprocesamiento para crear un árbol de altura equilibrada.

Estructura de nodos para un árbol cuádruple de puntos

Un nodo de un árbol cuádruple 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 suele descomponerse en dos partes, haciendo referencia a las coordenadas xey. Por tanto, un nodo contiene la siguiente información:

• cuatro punteros: cuádruple['NW'], cuádruple['NE'], cuádruple['SW'] y cuádruple['SE']
• punto; que a su vez contiene:
  • llave; generalmente expresado como coordenadas x, y
  • valor; por ejemplo un nombre

Árbol cuádruple punto-región (PR)

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

Árbol cuádruple de borde

Los quadtrees de borde ^{[7] [8]} (muy parecidos a los quadtrees PM) se utilizan para almacenar líneas en lugar de puntos. Las curvas se aproximan subdividiendo celdas con una resolución muy fina, específicamente hasta que haya un solo segmento de línea por celda. Cerca de las esquinas/vértices, los quadtrees de borde continuarán dividiéndose hasta que alcancen su nivel máximo de descomposición. Esto puede dar como resultado árboles extremadamente desequilibrados que pueden frustrar el propósito de la indexación.

Árbol cuádruple del mapa poligonal (PM)

El quadtree de mapas poligonales (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 aisladas). ^{[9] [10]} Una gran diferencia entre los quadtrees PM y los quadtrees de borde es que la celda bajo consideración no se subdivide si los segmentos se encuentran en un vértice de la celda.

Hay tres clases principales de PM Quadtrees, que varían según la información que almacenan dentro de cada nodo negro. Los quadtrees PM3 pueden almacenar cualquier cantidad de bordes que no se cruzan y como máximo un punto. Los quadtrees PM2 son iguales que los quadtrees PM3, excepto que todos los bordes deben compartir el mismo punto final. Finalmente, los quadtrees PM1 son similares a PM2, pero los nodos negros pueden contener un punto y sus aristas o simplemente 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 cuádruples 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 árboles tan dispersos almacenando únicamente subárboles cuyas hojas tengan datos interesantes (es decir, "subárboles importantes"). De hecho, 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 vínculo con un padre y un hijo). Resulta que solo necesitamos almacenar el nodo al comienzo de esta ruta (y asociarle algunos metadatos para representar los nodos eliminados) y adjuntar el subárbol con raíz en su final . 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úsqueda, inserción y eliminación en tiempo logarítmico aprovechando las curvas de orden Z. La curva de orden Z asigna cada celda del quadtree completo (y, por lo tanto, incluso del quadtree comprimido) en el tiempo a una línea unidimensional (y también la asigna en el tiempo), creando un orden total en los elementos. Por tanto, podemos almacenar el quadtree en una estructura de datos para conjuntos ordenados (en la que almacenamos los nodos del árbol). ${\displaystyle O(1)}$ ${\displaystyle O(1)}$

Debemos formular 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 asumimos que podemos calcular en el tiempo el ancestro común más bajo de dos puntos/celdas en el árbol cuádruple y establecer su orden Z relativo , y podemos calcular la función suelo en el tiempo. ${\displaystyle \alpha ,\beta \in [0,1)}$ ${\displaystyle O(1)}$ ${\displaystyle O(1)}$ ${\displaystyle O(1)}$

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

Para realizar una ubicación de punto (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 este celular . ${\displaystyle q}$ ${\displaystyle v}$
2. Si , regresa . ${\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 cuádruple sin comprimir. Llame a esta célula ancestral . ${\displaystyle q}$ ${\displaystyle v}$ ${\displaystyle u}$
4. Busque 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 quadtrees

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

Procesamiento de imágenes usando quadtrees

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

Unión / intersección de imágenes

Una de las ventajas de utilizar quadtrees para la manipulación de imágenes es que las operaciones establecidas de unión e intersección 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 realizar la operación píxel por píxel, podemos calcular la unión de manera más eficiente aprovechando la capacidad del árbol cuádruple para representar múltiples píxeles con un solo nodo. Para los propósitos de la discusión siguiente, si un subárbol contiene píxeles blancos y negros, diremos que la raíz de ese subárbol es de color gris.

El algoritmo funciona atravesando los dos quadtrees de entrada ( y ) mientras construye el quadtree de salida . Informalmente, 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, el nodo correspondiente se crea en y se colorea negro. Si solo uno de ellos es negro y el otro es gris, el nodo gris contendrá un subárbol debajo. No es necesario atravesar este subárbol. ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$ ${\displaystyle T}$
• Si (respectivamente, ) es blanco, (respectivamente, ) y el subárbol debajo de él (si lo hay) se copia en . ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$ ${\displaystyle v_{2}}$ ${\displaystyle v_{1}}$ ${\displaystyle T}$
• Si ambos y 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í solo un árbol cuádruple de tamaño mínimo. Por ejemplo, consideremos 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 representarse mediante un árbol cuádruple con solo el nodo raíz (de color negro), pero en su lugar el algoritmo produce un árbol completo de 4 arios de profundidad . Para solucionar este problema, realizamos un recorrido ascendente del árbol cuádruple resultante donde comprobamos si los cuatro nodos secundarios 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 casi el mismo algoritmo. Una forma de pensar en la intersección de las dos imágenes es que estamos haciendo una unión con respecto a los píxeles blancos . Como tal, 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 delimitador horizontal o vertical. En general, dos píxeles negros están conectados si se puede llegar a uno desde el otro moviéndose sólo 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 . Utilizando la representación de imágenes de 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 utilizar para colorear polígonos.

El algoritmo funciona en tres pasos:

• establecer las relaciones de adyacencia entre píxeles negros
• procesar las relaciones de equivalencia desde el primer paso para obtener una etiqueta única para cada componente conectado
• etiquete los píxeles negros con la etiqueta asociada con su componente conectado

Para simplificar la discusión, supongamos que los hijos de un nodo en el árbol cuádruple siguen el orden Z (SW, NW, SE, NE). Como podemos contar con esta estructura, para cualquier celda sabemos cómo navegar por el árbol cuádruple para encontrar las celdas adyacentes en los diferentes niveles de la jerarquía.

El primer paso se logra con un recorrido posterior al pedido del quadtree. Para cada hoja negra, observamos el nodo o los nodos que representan celdas que son vecinas del norte y 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 los vecinos del sur y del oeste ya han sido atendidos y contabilizados. Dejemos que el vecino del norte o del este que se está considerando actualmente 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 los dos tiene etiquetas, crea una y asígnasela a ambos.
• Si y tienen etiquetas diferentes, registre la equivalencia de esta etiqueta 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. Posteriormente, cada conjunto restante distinto se asociará con un componente conectado distinto en la imagen.

El tercer paso realiza otro recorrido posterior al pedido. Esta vez, para cada nodo negro utilizamos la operación de búsqueda de unión-find (con la antigua etiqueta de ) para buscar y asignar su nueva etiqueta (asociada con el componente conectado del que forma parte). ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$

Generación de malla usando quadtrees

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

La generación de malla es esencialmente la triangulación de un conjunto de puntos para el cual se puede realizar un procesamiento adicional. 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 escasas 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 construidos en el conjunto de puntos se pueden utilizar para crear mallas con estas propiedades deseadas.

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

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

Considere la celda y la vecindad de celdas del mismo tamaño centradas en . A esta vecindad la llamamos grupo extendido . Decimos que el árbol cuádruple está bien equilibrado si está equilibrado, y por 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 árbol cuádruple en los puntos de entrada.
2. Asegúrese de que el árbol cuádruple esté equilibrado. Por cada hoja, si hay una vecina que es demasiado grande, subdivida la vecina. Esto se repite hasta que el árbol esté equilibrado. También nos aseguramos de que, para una hoja con una punta, los nodos del grupo extendido de cada hoja estén en el árbol.
3. Para cada nodo hoja que contiene un punto, si el grupo 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 de nos aseguramos de que los nodos del clúster extendido estén en el árbol (y los 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. Transforma 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 cuadros con puntos en algunos de ellos. El paso de transformación se realiza de la siguiente manera: para cada punto, deforma la esquina más cercana de su celda para encontrarla y triangular los cuatro cuadrángulos resultantes para hacer triángulos "bonitos" (el lector interesado puede consultar el capítulo 12 de Har-Peled ^{[ 24]} para obtener más detalles sobre lo que hace que los triángulos sean "bonitos").

Los cuadrados restantes se triangulan según algunas reglas simples. Para cada cuadrado regular (sin puntos dentro ni esquinas 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 cruce un lado está deformado. Como tal, podemos triangular cuadrados con esquinas que se cruzan de la siguiente manera. Si hay un lado intersecado, el cuadrado se convierte en tres triángulos sumando las diagonales largas que conectan la intersección con las esquinas opuestas. Si hay cuatro lados intersecados, dividimos el cuadrado por la mitad agregando un borde entre dos de las cuatro intersecciones y luego conectamos estos dos puntos finales con 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 de todo, tenemos una bonita malla triangulada de nuestro conjunto de puntos construida a partir de un árbol cuádruple.

Pseudocódigo

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

Requisitos previos

Se supone que se utilizan estas estructuras.

// Objeto de coordenadas simple para representar puntos y vectores estructura XY{ flotar x; flotar y; función __construct( flotante _x, flotante _y) {...}}// Cuadro delimitador alineado con el eje con media dimensión y estructura central AABB{ centro XY ; flotar media dimensión; función __construct( XY _center, float _halfDimension) {...} función contienePunto( punto XY ) {...} función intersectaAABB( AABB otro) {...}}

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 límite AABB de árbol cuádruple; // Puntos en este nodo de árbol cuádruple  Matriz de puntos XY [tamaño = QT_NODE_CAPACITY] ; // Niños  QuadTree* noroeste; QuadTree* noreste; QuadTree* suroeste; QuadTree* sureste; // Métodos  function __construct( AABB _boundary) {...} function insert( XY p) {...} function subdivide() {...} // crea cuatro hijos que dividen completamente este quad en cuatro quads de igual área  función queryRange ( rango AABB ) {...}}

Inserción

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

clase QuadTree{ ...  // Inserta un punto en la  función Insertar QuadTree ( XY p) { // Ignora los objetos que no pertenecen a este árbol cuádruple  si (!boundary.containsPoint(p)) devuelve  false ; // el objeto no se puede agregar  // Si hay espacio en este árbol cuádruple y no tiene subdivisiones, agregue el objeto aquí  if (points.size < QT_NODE_CAPACITY && northWest == null ) { puntos.append(p); devolver  verdadero ; }  // De lo contrario, subdivida y luego agregue el punto a cualquier nodo que lo acepte  si (noroeste == nulo ) subdividir(); // 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  si (noroeste->insertar(p)) devuelve  verdadero ; si (noreste->insertar(p)) devuelve  verdadero ; si (suroeste->insertar(p)) devuelve  verdadero ; si (sureste->insertar(p)) devuelve  verdadero ;  // 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.

clase QuadTree{ ...  // Encuentra todos los puntos que aparecen dentro de una  función de rango queryRange ( rango AABB ) { // Preparar una matriz de resultados  Matriz de puntos XYInRange ;  // Cancelar automáticamente si el rango no intersecta este quad  if (!boundary.intersectsAABB(range)) return puntosInRange; // lista vacía  // Verifica los objetos en este nivel cuádruple  para ( int p = 0; p < puntos.tamaño; p++) { si (rango.contienePunto(puntos[p])) puntosInRange.append(puntos[p]); }  // Terminar aquí, si no hay hijos  if (northWest == null ) return puntosInRange;  // De lo contrario, suma los puntos de los niños. puntosInRange.appendArray(noroeste->queryRange(rango)); puntosInRange.appendArray(noreste->queryRange(rango)); puntosInRange.appendArray(suroeste->queryRange(rango)); puntosInRange.appendArray(sureste->queryRange(rango));  puntos de retorno en el rango; }}

Ver también

• Refinamiento de malla adaptable
• Partición del espacio binario
• mosaico binario
• árbol kd
• octree
• árbol R
• árbol UB
• Base de datos espacial
• Subpavimento
• Curva de orden Z

Referencias

Las encuestas realizadas por Aluru ^[4] y Samet ^{[22] [16]} brindan una buena descripción general de los quadtrees.

Notas

1. Finkel, RA; Bentley, JL (1974). "Quad arboles una estructura de datos para la recuperación de claves compuestas". Acta Informática . 4 (1): 1–9. doi :10.1007/BF00288933. S2CID  33019699 . Consultado el 6 de noviembre de 2019 .
2. Milán Sonka, Vaclav Hlavac, Roger Boyle. "Procesamiento, análisis y visión artificial de imágenes". 2014. pág. 108-109.
3. Finkel, RA; Bentley, JL (1974). "Quad Trees, una estructura de datos para la recuperación de claves compuestas". Acta Informática . 4 . Springer-Verlag: 1–9. doi :10.1007/bf00288933. S2CID  33019699.
4. Aluru, S. (2004). "Quadtrees y octrees". En D. Mehta y S. Sahni (ed.). Manual de estructuras y aplicaciones de datos . Chapman y Hall/CRC. págs. 19-1 - 19-26. ISBN 9781584884354.
5. Orenstein, JA (1982). "Intentos multidimensionales utilizados para la búsqueda asociativa". Cartas de procesamiento de información . 14 (4). Elsevier: 150-157. doi :10.1016/0020-0190(82)90027-8.
6. Samet, H. (1984). "El quadtree y las estructuras de datos jerárquicas relacionadas" (PDF) . Encuestas de Computación ACM . 16 (2). MCA: 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 borde y árboles cuádruples de borde". Gráficos por computadora y procesamiento de imágenes . 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 Quadtrees". Transacciones ACM sobre gráficos, 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". Gráficos por computadora ACM SIGGRAPH . 20 (4): 197–206. doi : 10.1145/15886.15908 .
11. Har-Peled, S. (2011). "Quadtrees - Cuadrículas jerárquicas". Algoritmos de aproximación geométrica . Encuestas y monografías matemáticas vol. 173, sociedad matemática estadounidense.
12. Wanta, Damián; 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 Quadtree 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 . La prensa del MIT. págs. 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 del estado no lineal , 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. Cazador, GM (1978). Computación eficiente y estructuras de datos para gráficos . Doctor. disertación, Departamento de Ingeniería Eléctrica e Informática, Universidad de Princeton.
18. Cazador, director general; Steiglitz, K. (1979). "Operaciones sobre imágenes mediante árboles cuádruples". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 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 quadtrees". Gráficos por computadora y procesamiento de imágenes . 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. pag. 397.
21. Samet, H. (1981). "Etiquetado de componentes conectados mediante quadtrees". 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 quadtrees, octrees y estructuras de datos jerárquicas relacionadas". En Earnshaw, RA (ed.). Fundamentos Teóricos de la Computación Gráfica 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 mallados". Algoritmos de aproximación geométrica . Encuestas y monografías matemáticas vol. 173, sociedad matemática estadounidense.
25. de Berg, M.; Cheong, O.; van Kreveld, M.; Overmars, MH (2008). "Generación de malla no uniforme de Quadtrees". Algoritmos y aplicaciones de geometría computacional (3ª ed.). Springer-Verlag.

Referencias generales

1. Raphaël Finkel y JL Bentley (1974). "Árboles cuádruples: una estructura de datos para la recuperación de claves compuestas". Acta Informática . 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}}: Mantenimiento CS1: varios nombres: 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) . Consultado el 23 de marzo de 2012 .