Quadtree

Image
Un árbol cuaternario puntual con datos puntuales. Capacidad del contenedor: 1.
Image
Compresión de árbol cuaternario de una imagen, paso a paso

Un quadtree (dt desuse . Quadtree ) es en la informática una estructura de árbol en la que cada nodo interno tiene exactamente cuatro nodos secundarios. Los árboles cuaternarios se utilizan principalmente para subdividir un espacio bidimensional dividiéndolo recursivamente en cuatro áreas (cuadrantes). Las áreas pueden ser cuadradas, rectangulares o de cualquier forma. Una división similar se conoce como Q-árbol . Todas las formas de quadtrees comparten ciertas características:

  • Dividen la habitación en áreas personalizables
  • Cada área tiene una capacidad máxima. Si se alcanza esto, el área se subdivide.
  • El directorio del árbol sigue la subdivisión espacial del árbol cuaternario.

especies

Los Quadtrees se pueden clasificar de acuerdo con el tipo de datos que representan, incluidas áreas, puntos y líneas. Los quadtrees también se pueden clasificar según si la forma del árbol depende de la secuencia de procesamiento de datos o no. Algunos tipos comunes de árboles cuaternarios son:

El árbol cuaternario del área

El árbol cuaternario de área representa una división del espacio en dos dimensiones, que divide el área en cuatro cuadrantes, subcuadrantes, etc. iguales, y cada nodo final contiene datos de una subárea específica. Cada nodo del árbol tiene exactamente cuatro hijos o ninguno (nodos hoja). El árbol cuaternario de área es un tipo de trie .

Se puede utilizar un árbol cuaternario de área con una profundidad de n para representar una imagen de 2 n × 2 n píxeles, teniendo cada píxel el valor 1 o 0. El nodo raíz representa toda el área de la imagen. Si no todos los píxeles son ceros o unos en un área, se subdivide. En esta aplicación, cada nodo final representa un área de imagen cuyos puntos de imagen son todos ceros o unos.

Un árbol cuaternario de área también se puede utilizar como una representación de resolución variable de un campo de datos. Por ejemplo, las temperaturas en un área se pueden almacenar como un árbol cuaternario, y la temperatura promedio de la subárea se almacena en cada hoja.

Cuando se usa un árbol cuaternario de rango para representar un registro de puntos (por ejemplo, latitud y longitud de varias ciudades), los rangos se subdividen hasta que cada hoja contiene como máximo un punto.

Árbol cuaternario de puntos

El árbol cuaternario de puntos es una adaptación de un árbol binario que se utiliza para representar datos puntuales bidimensionales. Comparte las características de un árbol cuaternario, pero es un árbol real porque el centro de una subdivisión es siempre un punto. La forma del árbol depende del orden de procesamiento de los datos. Con un tiempo de ejecución generalmente O (log n), a menudo es muy eficiente cuando se comparan puntos de datos ordenados bidimensionales.

Estructura nodal de un árbol cuádruple de puntos

Un nodo de un árbol cuádruple es similar a un nodo de un árbol binario, del cual se diferencia principalmente de los dos punteros (izquierdo y derecho) de un árbol binario normal por los cuatro punteros (uno por cuadrante). Además, una clave generalmente se divide en dos componentes que se relacionan con las coordenadas xey. Por tanto, un nodo contiene la siguiente información:

  • cuatro punteros: quad ['NW'], quad ['NO'], quad ['SW'] y quad ['SO']
  • Point, que a su vez contiene:
    • Atributo, generalmente expresado como coordenadas xey
    • Valor, por ejemplo un nombre

Árbol cuaternario de borde

Los árboles cuaternarios de bordes se utilizan especialmente para almacenar líneas en lugar de puntos. Las curvas se aproximan mediante celdas finamente divididas. Esto puede resultar en árboles muy desequilibrados, lo que puede ir en contra del propósito de la indexación.

Algunos usos comunes de los árboles cuaternarios

Los árboles cuaternarios son el equivalente bidimensional de los árboles octogonales .

Evidencia individual

  1. ^ Tomas G. Rokicki: un algoritmo para comprimir el espacio y el tiempo . 1 de abril de 2006. Consultado el 20 de mayo de 2009.
  2. ^ Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Árboles de densidad para una estimación de estado no lineal eficiente. Actas de la 13a Conferencia Internacional sobre Fusión de la Información, Edimburgo, Reino Unido, julio de 2010.

literatura

  • Hanan Samet: El diseño y análisis de estructuras de datos espaciales. Addison-Wesley, Reading, MA, 1990, ISBN 0-201-50255-0 .
  • Hanan Samet: Aplicaciones de estructuras de datos espaciales: gráficos por computadora, procesamiento de imágenes y SIG. Addison-Wesley, Reading, MA, 1990, ISBN 0-201-50300-X .
  • RA Finkel, JL Bentley: Quad trees una estructura de datos para la recuperación en claves compuestas . En: Acta Informatica . cinta 4 , no. 1 , ISSN  0001-5903 , pág. 1 a 9 , doi : 10.1007 / BF00288933 .
  • Mark de Berg, Marc van Kreveld, Mark Overmars , Otfried Schwarzkopf (eds.): Geometría computacional. Algoritmos y aplicaciones . 2do, rev. Edición. Springer, Berlín y col. 2000, ISBN 3-540-65620-0 , 14: Quadtrees, p. 291-306 .
  • Hanan Samet, Robert Webber: almacenamiento de una colección de polígonos mediante Quadtrees. (PDF) Julio de 1985, consultado el 23 de marzo de 2012 .

enlaces web

Commons : Quadtrees  - colección de imágenes, videos y archivos de audio

Implementaciones