|
Universidad tecnolgica del Per Facultad de ingenieras Carrera
profesional de ingeniera de sistema e informtica Tema Quad-tree
Ciclo: III Curso: Algoritmos y estructura de datos Docente:
Autor(es): Juan Gabriel Nez Garca Ivn choquemaqui Mamani Alison
Rodrguez Rendn
Arequipa 23/02/12
ndice 1.- Introduccion 1.1.-Vision general del Quadtree 2.-
Representacin de Puntos en Quadtree 3.- Tipos 3.1.- Quadtree de
Puntos 3.1.2.- Estructura del nodo para un quadtree de puntos 3.2.-
Quadtree de la Regin 4.- Ventajas del QuadTree 5.- Desventajas del
QuadTree 6.- El Qtree-cubo 7.- Algunas Aplicaciones Comunes de
Quadtrees 8.- Algoritmos Quadtree 8.1.- Algoritmo de insercin 8.2.-
Algoritmo para eliminar elementos del rbol 8.3.- Algoritmo para
buscar nodos de una regin 8.4.- Algoritmo para obtener el cuadrante
9.- Conclusiones 10.- Sugerencias investigativas 11.- Referencias
12.- Anexos
1.- Introduccin * Un quadtree se puede utilizar para codificar
imgenes. La idea fundamental detrs de stos es que cada imagen se
puede dividir en cuatro cuadrantes, y a su vez, cada cuadrante se
puede dividir en otros cuatro sub-cuadrantes, etc. En un quadtree,
la imagen es representada por el nodo padre, mientras que los
cuatro cuadrantes son representados por sus nodos hijos en un orden
determinado. Por ejemplo, si la imagen est compuesta por un solo
color, se puede representar con un quadtree que consta de un solo
nodo. En general, un cuadrante tiene que ser subdividido si est
compuesto por diferentes colores. Como resultado, la profundidad de
un quadtree no es uniforme. Ya con las imgenes representadas en el
quadtree se pueden hacer muchas operaciones sobre stas, como
unirlas, modificar solamente ciertos cuadrantes, agregar/modificar
colores, etc. *Una gran variedad de estructuras jerrquicas existen
para representar los datos espaciales. Una tcnica normalmente usada
es Quadtree. El desarrollo de stos fue motivado por la necesidad de
guardar datos que se insertan con valores idnticos o similares.
Este artculo trata de la representacin de datos en el espacio
bidimensional. Quadtree tambin se usa para la representacin de
datos en los espacios tridimensionales o con hasta 'n' dimensiones.
1.1.- Visin general del QuadTree El trmino Quadtree se usa para
describir una clase de estructuras jerrquicas cuya propiedad en
comn es el principio de recursividad de descomposicin del espacio.
Estas clases, basan su diferencia en los requisitos siguientes: 1.
El tipo del dato en que ellas actan. 2. El principio que las guas
del proceso de descomposicin. 3. La resolucin (inconstante o
ninguna). La familia Quadtree se usa para representar puntos, reas,
curvas, superficies y volmenes. La descomposicin puede hacerse en
las mismas partes en cada nivelado (la descomposicin regular), o
puede depender de los datos de la entrada. La resolucin de la
descomposicin, en otros trminos, el nmero de tiempos en que el
proceso de
descomposicin es aplicado, puede tratarse de antemano, o puede
depender de las propiedades de los datos de la entrada. El primer
ejemplo de un Quadtree se relaciona a la representacin de un rea
bidimensional. La regin Quadtree que representa las reas es el tipo
ms estudiado. Este ejemplo es basado en la subdivisin sucesiva del
espacio en cuatro cuadrantes del mismo tamao. 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 areas Blancas y Negras (Vaco y Datos), deben
subdividirse sucesivamente hasta que solo queden cuadrantes Negros
Y Blancos... (Datos y Vacos). Cada cuadrante representa un nodo del
Quadtree, los espacios negros y blancos siempre estn en las hojas,
mientras todos los nodos interiores representan los espacios
grises. 2.- Representacin de Puntos en Quadtree Pueden
representarse las multidimensiones de los puntos de varias maneras.
La representacin escogida depende de la tarea especfica que uno
quiera ejecutar con un grupo de puntos. Dos de las tareas ms
comunes que se realizan con un grupo de puntos son: 1. Determinar
si un punto dado est en el grupo. 2. Para encontrar un grupo de
puntos que se relacionan dado algn criterio de un segundo punto. El
Quadtree, sus variantes y tambin el kd-rbol, representan los
formularios bastante eficaces para representar los puntos. Los dos
tipos ms comn de Quadtree para representar los puntos son el "Point
Quadtree" y el "PR Quadtree (la variante del Quadtree de la
regin)". El PR-Quadtree es una adaptacin del Quadtree para la
representacin de puntos en una regin. Cada punto es asociado con el
cuadrante. Diferente del Point Quadtree dnde la divisin de los
cuadrantes depende de los datos de la entrada, la divisin siempre
es hecha de una manera regular. Los nodos-hoja que contienen un
punto los denominaremos Negros, y si estn vacos 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 informacin relacionada al nodo. struct PRNo {
PRNo * filhos[4]; int color; // white = 0; gray = 1; black = 2;
char info [20]; int x; int y; }; 3.- Tipos Quadtrees se puede
clasificar segn el tipo de datos que representan, incluyendo reas,
puntos, lneas y curvas. Quadtrees puede tambin ser clasificado
independientemente de la forma que tenga por la informacin que
contiene. Algunos tipos comunes de quadtrees son: 3.1.- Quadtree de
Puntos El quadtree del punto es una adaptacin de un rbol binario
usado para representar datos de dos dimensiones del punto. Comparte
las caractersticas de todos los quadtrees pero es un rbol verdadero
mientras que el centro de una subdivisin 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.
3.1.2.- Estructura del nodo para un quadtree de puntos
4 Punteros: cuadrante [NW], cuadrante [NE], cuadrante[SW], y
cuadrante[SE] Puntos, del tipo DataPoint, que alternadamente
contiene:
-Nombre -(x, y) Coordenadas Una imagen binaria es normalmente
representada como una serie de entradas binarias, es decir; cada
una de las entradas de la serie tiene un valor de 0 o 1. Para
guardar la imagen binaria normalmente se usa la conocida particin
quadtree. Para una serie N*N, NInsertar(px, py, pinfo); };break;
case 2: { NE->Insertar(px, py, pinfo); };break; case 3: {
SW->Insertar(px, py, pinfo); };break;
case 4: { NW->Insertar(px, py, pinfo); };break; } } } int
ObtenerHijo(int px, int py) { if(x
