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:
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]
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.
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 n × 2 n 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.
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 al comparar puntos de datos ordenados bidimensionales, y generalmente opera en tiempo O (log n) . Vale la pena mencionar los árboles cuádruples de puntos por su integridad, 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 procesamiento previo para crear un árbol de altura equilibrada.
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:
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. Sin embargo, las celdas de un árbol cuádruple 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 cuádruple de puntos, el árbol cuádruple PR también puede tener una altura lineal cuando se le da un conjunto "malo".
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.
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.
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".
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).
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.
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).
Para realizar una ubicación de punto (es decir, encontrar su celda en el árbol comprimido):
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.
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 región y las operaciones de procesamiento de imágenes realizadas en ellos son igualmente adecuados para imágenes en color. [4] [16]
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.
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]
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.
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:
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:
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).
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.
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).
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.
La creación de la malla se realiza de la siguiente manera:
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 intersectado, 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.
El siguiente pseudocódigo muestra una forma de implementar un quadtree que maneja solo puntos. Hay otros enfoques disponibles.
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) {...}}
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 ) {...}}
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 ; }}
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; }}
Las encuestas realizadas por Aluru [4] y Samet [22] [16] brindan una buena descripción general de los quadtrees.
{{cite book}}
: Mantenimiento CS1: varios nombres: lista de autores ( enlace )Capítulo 14: Quadtrees: págs. 291–306.