Quadtree (también quadtree , 4-tree , inglés quadtree ) es un árbol en el que cada nodo interno tiene exactamente 4 descendientes. Los quadtrees se utilizan a menudo para dividir recursivamente un espacio 2D en 4 cuadrantes (regiones). Las áreas son cuadrados, rectángulos o tienen una forma arbitraria. El término inglés quadtree fue acuñado por Raphael Finkel y John Bentley .en 1974. Una partición similar del espacio se conoce como Q-tree. Características comunes de los diferentes tipos de quadtrees:
Los quadtrees se pueden clasificar según el tipo de datos que representan: espacio, puntos, líneas, curvas. También se pueden dividir según si la forma del árbol depende del orden en que se procesan los datos. Algunos tipos de quadtrees:
Region quadtree representa cualquier parte de un espacio bidimensional al dividirlo en 4 cuadrantes, subcuadrantes, etc., con cada hoja del árbol correspondiente a un área determinada . Cada nodo del árbol tiene 4 hijos o ninguno (hojas). Los quadtrees de partición espacial no son completamente árboles porque la posición de los subcuadrantes es independiente de los datos. Un nombre más correcto es árboles de prefijos ( ing. trie ).
Se puede usar un árbol de altura n para representar una imagen que consta de 2n × 2n píxeles, donde cada píxel tiene un valor de 0 o 1. La raíz del árbol representa el área completa de la imagen. Si no todos los píxeles son solo ceros o solo unos, se rompe. En este caso, cada hoja corresponde a un conjunto de píxeles, ya sea solo ceros o solo unos.
Los quadtrees que rompen espacios también se pueden usar para representar la resolución variable de un conjunto de datos. Por ejemplo, la información de temperatura se puede almacenar como un quadtree, cada nodo del cual almacena la temperatura promedio de sus nodos secundarios.
Si el árbol se usa para representar un conjunto de puntos (por ejemplo, la latitud y la longitud de las posiciones de algunas ciudades), las regiones se subdividen hasta que las hojas no contienen más de un punto.
Point quadtree es un tipo de árbol binario utilizado para almacenar información sobre puntos en un plano . La forma del árbol depende del orden en que se especifican los datos. El uso de tales árboles es muy eficiente para comparar puntos ordenados en el plano y el tiempo de procesamiento es O(log n) .
Estructura de nodosEl nodo del quadtree que almacena información sobre los puntos del plano es similar al nodo de un árbol binario, con la única salvedad de que el primer nodo tiene cuatro hijos (uno para cada cuadrante) en lugar de dos ("derecha" y " izquierda"). La clave del nodo tiene dos componentes (para las coordenadas x e y ). Por lo tanto, un nodo de árbol contiene la siguiente información:
Los quadtrees que almacenan información sobre líneas ( edge quadtree ) se utilizan para describir líneas rectas y curvas . Las curvas se describen mediante aproximaciones exactas dividiendo las celdas en celdas muy pequeñas. Esto puede hacer que el árbol se desequilibre, lo que significa problemas de indexación.
Los quadtrees que almacenan información sobre polígonos ( eng. polygonal map quadtree/PMQuadtree ) pueden contener información sobre polígonos, incluidos los degenerados (que tienen vértices o caras aislados) [1] .
Los quadtrees son un análogo bidimensional de los árboles octantes ( ing. octtree ).
El siguiente código demuestra el uso de quadtrees para almacenar información de puntos. También son posibles otros enfoques de la construcción.
Se espera que se utilicen las siguientes estructuras de datos.
// Una estructura simple para representar un punto o vector struct XY { flotar x; flotar y; función __construct( float _x, float _y) {...} } // Cuadro delimitador alineado con el eje (AABB), estructura centrada en la mitad de la dimensión AABB { centro XY ; Semidimensión XY ; función __construir( centro XY, media dimensión XY ) {...} función contienePunto( XY p) {...} función intersecaAABB( AABB otro) {...} }La clase representa el propio árbol de 4 y el nodo raíz.
clase QuadTree { // Constante: el número de elementos que se pueden almacenar en un nodo constante int QT_NODE_CAPACITY = 4; // Un cuadro delimitador alineado con el eje // muestra los límites del límite AABB del árbol ; // Matriz de puntos de XY [tamaño = QT_NODE_CAPACITY] puntos; // Descendientes de QuadTree* noroeste; QuadTree* noreste; QuadTree* suroeste; QuadTree* sureste ; // Métodos function __construct( AABB _boundary) {...} function insert( XY p) {...} function subdivide() {...} // Crea 4 hijos que dividen el cuadrante en 4 partes iguales function queryRange( gama AABB ) {...} }El siguiente método inserta un punto en el cuadrante apropiado del árbol, dividiéndolo si es necesario.
El siguiente método encuentra todos los puntos dentro de un cierto rango.
clase QuadTree { ... // Buscar puntos dentro del rango function queryRange ( rango AABB ) { // Preparar una matriz para el resultado Array of XY pointsInRange; // Cancelar si el rango no coincide con el cuadrante if (!boundary.insersectsAABB(range)) return pointsInRange; // Lista vacía // Comprobar los objetos de nivel actual para ( int p := 0; p < puntos.tamaño; p++) { if (rango.containsPoint(puntos[p])) puntosEnRange.append(puntos[p]); } // Detener si no hay más hijos if (northWest == null ) return pointsInRange; // Agregar todos los puntos secundarios puntosEnRange.appendArray(noroeste->queryRange(rango)); pointsInRange.appendArray(noreste->queryRange(rango)); puntosEnRange.appendArray(suroeste->queryRange(rango)); puntosEnRange.appendArray(sureste->queryRange(rango)); puntos de retorno en rango; } }Quadtrees] (julio de 1985). Fecha de acceso: 23 de marzo de 2012. Archivado desde el original el 2 de octubre de 2012.
| Árbol (estructura de datos) | |
|---|---|
| Árboles binarios | |
| Árboles binarios autoequilibrados |
|
| árboles B |
|
| árboles de prefijo |
|
| Partición binaria del espacio | |
| Árboles no binarios |
|
| Rompiendo el espacio |
|
| Otros árboles |
|
| Algoritmos | |