kD-Tree
- Un Árbol kd (abreviatura de árbol k-dimensional) es una estructura de datos de particionado del espacio que organiza los puntos en un Espacio euclídeo de k dimensiones.
- Un árbol kd emplea sólo planos perpendiculares a uno de los ejes del sistema de coordenadas. Además, todos los nodos de un árbol kd, desde el nodo raíz hasta los nodos hoja, almacenan un punto.
- La letra k se refiere al número de dimensiones. Un árbol kd tridimensional podría ser llamado un árbol 3d. Sin embargo se suele emplear la expresión "árbol kd tridimensional".
- Construcción:
- Según se desciende en el árbol, se alterna por los ejes. (Por ejemplo, la raíz plano alineado con el eje x, sus descendientes planos alineados con el y y los nietos alineados con el z..)
- En cada paso, el punto por donde pasa el plano será la mediana de los puntos.
- Este método es balanceado, donde cada nodo hoja está a la misma distancia de la raíz.
- Dada una nube de 6 puntos, el siguiente algoritmo genera un árbol kd balanceado que contiene dichos puntos.
Función para construir el kDTree, dado un conjunto de puntos P y una profundidad en el árbol.
BuildKdTree ( P , PROFUNDIDAD )
- SI P contiene sólo un punto ENTONCES devuelve la hoja que contiene el punto
- SI TIENE MAS DE UN PUNTO
- SI PROFUNDIDAD esta vacio
- Divido P en dos subconjuntos con una línea vertical (1) en la mediana de todas las coordeanadas X de los puntos de P
- A es el subconjunto de puntos de la izquierda
- B es el subconjunto de puntos de la derecha
- SI PROFUNDIDAD no esta vacio
- Divido P en dos subconjuntos con una línea horizontal(2) en la mediana de todas las coordeanadas Y de los puntos de P
- A es el subconjunto de puntos de por encima
- B es el subconjunto de puntos de por debajo
- Creo un nodo nuevo en el árbol almacenando la linea y sus hijos.
- Con los puntos de la izquierda repito BuildKdTree ( P , PROFUNDIDAD )
- Con los puntos de la derecha repito BuildKdTree ( P , PROFUNDIDAD )
- Para encontrar la mediana en cada nodo es mejor crear una lista de puntos ordenados de cada una de las dimensiones.
KDTREE es lo más eficiente en entornos estáticos con Ray-Tracing.
- Al pasar un rayo por una celda se producen 4 casos:
- Que el rayo atraviese el plano después de salir de la celda:
- Descarto la hoja al otro lado del plano: F
- Que el rayo atraviese el plano antes de salir:
- No se descarta ninguno de los hojas.
- Que el rayo atraviese el plano antes de llegar a la celda
- Se descarta la hoja antes del plano: N
- Que no intercepto: la celda se descarta
