Estructuras de datos espaciales

Estructura de Datos Espaciales
Algunos objetos espaciales pueden ser puntos, líneas, regiones, rectángulos, etc..
Estructuras de datos jerárquicas
Es un método que se basa en la descomposiciónrecursiva, similar al divide y vencerás.
R-Tree
En la parte de arriba se muestra un ejemplo de los arboles R, el cual se construye de la siguiente manera:
- Organizar los objetos espaciales enrectángulos dimensionales
- Cada nodo del árbol corresponde a un rectángulo menor que incluye nodos secundarios.
- El árbol se ajusta a los parámetros para un pequeño número de páginas visitadas durante unaconsulta espacial.
- Todos los nodos hoja aparecen al mismo nivel.
- Cada hoja de nodos corresponde a (R, O) donde R es el rectángulo más pequeño que contiene O.
- R-Tree de orden (m, M) significaque cada nodo del árbol contiene entre M/2 pisos y M nodos.
R+- Tree La descomposición del espacio en las celda disyuntas
- Los arboles R+- Tree y las celdas son usadas para descomponer losespacios dentro de las celdas.
- Múltiples caminos de oposición desde la raíz.
- Altura del árbol se incrementa.
- Los tiempos de recuperación son menores.
- Cuando se suman los objetos, desaparecen losduplicados.
- No es posible garantizar que todas las propiedades de los arboles se cumplan sin pasar por rutinas de eliminación.
- Los datos son dependientes unos de otros. Cuadricula uniforme Esideal para los datos distribuidos de manera uniforme, en donde los espacios se descomponen en bloques de tamaño uniforme. Árbol cuadrado El espacio se descompone sobre la base de puntos de datos, y essensible a la posición del objeto, y el ancho de los bloques se limita a dos. Buscando con Arboles cuadrado Son útiles para realizar operaciones de conjuntos, el peor escenario es la suma de los nodosen dos árboles. Rectángulos de datos Se utiliza para aproximar otros objetos en la imagen y en las normas de diseño. Si el ambiente es estático, la solución se basa en el uso del paradigma plano...