Árbol cuaternario
| ||||||
Árbol cuaternario. Un árbol cuaternario es un conjunto de clases de estructuras de datos jerárquicas cuya propiedad común es que están basados en el principio de descomposición recursiva del espacio. En un árbol cuaternario de puntos, el centro de una subdivisión está siempre en un punto. Al insertar un nuevo elemento, el espacio queda divido en cuatro cuadrantes. Al repetir el proceso, el cuadrante se divide de nuevo en cuatro cuadrantes, y así sucesivamente.
Sumario
Visión General del árbol cuaternario
El término árbol cuaternario se usa para describir una clase de estructuras jerárquicas cuya propiedad en común es el principio de recursividad de descomposición del espacio.
Estas clases, basan su diferencia en los requisitos siguientes:
- El tipo del dato en que ellas actúan.
- El principio que las guías del proceso de descomposición.
- La resolución (inconstante o ninguna).
La familia del árbol cuaternario se usa para representar puntos, áreas, curvas, superficies y volúmenes. La descomposición puede hacerse en las mismas partes en cada nivelado (la descomposición regular), o puede depender de los datos de la entrada. La resolución de la descomposición, en otros términos, el número de tiempos en que el proceso de descomposición es aplicado, puede tratarse de antemano, o puede depender de las propiedades de los datos de la entrada.
El primer ejemplo de un árbol cuaternario se relaciona a la representación de un área bidimensional. La región árbol cuaternario que representa las áreas es el tipo más estudiado. Este ejemplo es basado en la subdivisión sucesiva del espacio en cuatro cuadrantes del mismo tamaño. El subcuadrante que contiene datos simplemente se denomina área Negra, y los que no contienen datos se denominan área Blanca. Un subcuadrante que contiene partes de ambos se denomina área Ceniza. Los subcuadrantes Ceniza, que contienen aéreas Blancas y Negras (Vacío y Datos), deben subdividirse sucesivamente hasta que solo queden cuadrantes Negros Y Blancos... (Datos y Vacíos).
Cada cuadrante representa un nodo del árbol cuaternario, los espacios negros y blancos siempre están en las hojas, mientras todos los nodos interiores representan los espacios grises.
Representación de Puntos en árbol cuaternario
Pueden representarse las multidimensiones de los puntos de varias maneras. La representación escogida depende de la tarea específica que uno quiera ejecutar con un grupo de puntos. Dos de las tareas más comunes que se realizan con un grupo de puntos son:
- Determinar si un punto dado está en el grupo.
- Para encontrar un grupo de puntos que se relacionan dado algún criterio de un segundo punto.
El árbol cuaternario, sus variantes y también el árbol kd, representan los formularios bastante eficaces para representar los puntos. Los dos tipos más común de árbol cuaternario para representar los puntos son el "árbol cuaternario de puntos" y el "PR - árbol cuaternario (la variante del árbol cuaternario de la región)".
El PR-árbol cuaternario es una adaptación del árbol cuaternario para la representación de puntos en una región. Cada punto es asociado con el cuadrante. Diferente del Point árbol cuaternario dónde la división de los cuadrantes depende de los datos de la entrada, la división siempre es hecha de una manera regular. Los nodos-hoja que contienen un punto los denominaremos Negros, y si están vacíos Blancos. Todos los nodos que no tienen hojas se denominan Ceniza. Cada nodo se guarda en un registro que contiene cinco campos. El primero contiene un vector de indicadores para los cuatro hijos del nodo (correspondiendo a los cuatro cuadrantes), el segundo, el color del nodo (blanco, negro o ceniza), un tercer campo puede reservarse para un poco de información relacionada al nodo.
Tipos
árbol cuaternarios se puede clasificar según el tipo de datos que representan, incluyendo áreas, puntos, líneas y curvas. árbol cuaternarios puede también ser clasificado independientemente de la forma que tenga por la información que contiene. Algunos tipos comunes de árbol cuaternarios son:
Árbol cuaternario de Puntos
El árbol cuaternario del punto es una adaptación de un árbol binario usado para representar datos de dos dimensiones del punto. Comparte las características de todos los árbol cuaternarios pero es un árbol verdadero mientras que el centro de una subdivisión está siempre en un punto. Se procesa la forma del árbol depende de los datos de la orden. Es a menudo muy eficiente en comparar los puntos de referencias pedidos de dos dimensiones, funcionando generalmente en tiempo de O (log n)
Estructura del nodo para un árbol cuaternario de puntos
- 4 Punteros: cuadrante [NW], cuadrante [NE], cuadrante[SW], y cuadrante[SE]
- Puntos, del tipo DataPoint, que alternadamente contiene:-Nombre -(x, y) Coordenadas
Árbol cuaternario de Región
El árbol cuaternario de región representa una partición del espacio en dos dimensiones descomponiendo la región en cuatro cuadrantes iguales, subcuadrantes, y así sucesivamente con cada nodo de la hoja que contiene los datos que corresponden a un subregion específico. Cada nodo en el árbol tiene exactamente cuatro hijos, o no tiene ningún hijo (un nodo hoja). Un árbol cuaternario de la región con una profundidad de n se puede utilizar para representar una imagen que consiste en 2n * pixeles 2n, donde está 0 o 1 cada valor del pixel. Esta estructura de datos es unidimensional y solo se encuentra en memoria principal. Cada nodo hijo tiene asociado a él cuatro nodos, representando así los dieciséis sub-cuadrantes de dicha imagen. Una vez formado el árbol cuaternario, los nodos hojas representan la característica de dicho píxel, que puede ser blanco o negro, si son imágenes monocromáticas, dependiendo de la uniformidad del color de los nodos hijos (si todos sus hijos son de color negro, entonces dicho nodo será representado por el color negro). Pero si algún nodo posee nodos hijos con colores no uniformes, entonces es representado por un *nodo gris*. Un árbol cuaternario de región se puede también utilizar como representación variable de la resolución de una zona de informaciones. Por ejemplo, las temperaturas en un área se pueden almacenar como árbol cuaternario, con cada nodo de la hoja almacenando la temperatura media sobre el subregion que representa. Si un árbol cuaternario de la región se utiliza pacarpeta sin títulora representar un sistema de datos del punto (tales como la latitud y la longitud de un sistema de ciudades), se subdividen las regiones hasta que cada hoja contiene a lo máximo un solo punto.
Algunas aplicaciones comunes del árbol cuaternario
- Representación de la imagen.
- Indexación de direcciones espaciales.
- Detección eficiente de la colisión en dos dimensiones.
- Desecho del tronco de la visión de los datos del terreno.
- Almacenando datos escasos, tales como una información del formato para una hoja de balance o para algunos cálculos de la matriz.
- Solución de los campos multidimensionales (dinámica, electromagnetismo flúidos de cómputo)
- árbol cuaternarios es el análogo de dos dimensiones de octrees.
