Á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. Los árboles kd son un caso especial de los árboles BSP.
Un árbol kd emplea sólo planos perpendiculares a uno de los ejes del sistema de coordenadas. Esto difiere de los árboles BSP, donde los planos pueden ser arbitrarios. Además, todos los nodos de un árbol kd, desde el nodo raíz hasta los nodos hoja, almacenan un punto. Mientras tanto, en los árboles BSP son las hojas los únicos nodos que contienen puntos (u otras primitivas geométricas). Como consecuencia, cada plano debe pasar a través de uno de los puntos del árbol kd.
Técnicamente, 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". (También es más descriptivo, ya que un árbol tridimensional puede ser varias cosas, pero el término árbol kd se refiere a un tipo en concreto de árbol de particionado.) Las letras k y d se escriben en minúsculas, incluso al principio de una oración. La k se escribe en cursiva, aunque son también comunes las formas "árbol KD" y "árbol Kd".
Un árbol kd tridimensional. La primera división (rojo) corta la celda raíz (blanco) en dos subceldas, que son divididas a su vez (verde) en dos subceldas. Finalmente, cada una de esas cuatro es dividida (azul) en dos subceldas. Dado que no hay más divisiones, las ocho finales se llaman hojas. Las esferas amarillas representan los nodos del árbol.
Operaciones en árboles k
Construir un árbol k
Dado que hay muchas maneras posibles de elegir planos alineados a los ejes, hay muchas maneras de generar árboles kd. El sistema habitual es:
- Conforme se desciende en el árbol, se emplean ciclos a través de los ejes para seleccionar los planos. (Por ejemplo, la raíz puede tener un plano alineado con el eje x, sus descendientes tendrían planos alineados con el y y los nietos de la raíz alineados con el z, y así sucesivamente)
- En cada paso, el punto seleccionado para crear el plano de corte será la mediana de los puntos puestos en el árbol kd, lo que respeta sus coordenadas en el eje que está siendo usado.
Este método lleva a un árbol kd balanceado, donde cada nodo hoja está a la misma distancia de la raíz. De todas formas, los árboles balanceados no son necesariamente óptimos para todas las aplicaciones.
Dada una lista de n puntos, el siguiente algoritmo genera un árbol kd balanceado que contiene dichos puntos.
function kdtree (list of points pointList, int depth)
{
if pointList is empty
return nil;
else
{
// Select axis based on depth so that axis cycles through all valid values
var int axis := depth mod k;
// Sort point list and choose median as pivot element
sort pointList using predicate: point1[axis] < point2[axis];
choose median from pointList;
// Create node and construct subtrees
var tree_node node;
node.location := median;
node.leftChild := kdtree(points in pointList before median, depth+1);
node.rightChild := kdtree(points in pointList after median, depth+1);
return node;
}
}
Este algoritmo implementado en Python sería:
class Node:pass
def kdtree(pointList, depth=0):
if not pointList:
return
# Select axis based on depth so that axis cycles through all valid values
k = len(pointList[0]) # assumes all points have the same dimension
axis = depth % k
# Sort point list and choose median as pivot element
pointList.sort(key=lambda x:x[axis])
median = len(pointList)/2 # choose median
# Create node and construct subtrees
node = Node()
node.location = pointList[median]
node.leftChild = kdtree(pointList[0:median], depth+1)
node.rightChild = kdtree(pointList[median+1:], depth+1)
return node
Un ejemplo de uso:
pointList = [(2,3),(5,4),(9,1),(4,7),(8,1)]
tree = kdtree(pointList)
Este algoritmo crea el invariante para cualquier nodo. Todos los nodos en el subárbol de la izquierda están en un lado del plano de corte, y todos los nodos del subárbol de la derecha están en el otro lado. El plano de corte de un nodo pasa a través del punto asociado con ese nodo (referenciado en el código por node.location)
Añadir elementos a un árbol kd
Los nodos se añaden a un árbol kd de la misma forma que se añaden a cualquier otro árbol. Primero, se recorre el árbol empezando por la raíz y siguiendo por el nodo de la izquierda o de la derecha dependiendo de si el punto que se quiere insertar está en la derecha o en la izquierda del plano de corte. Una vez que se llega a un nodo hoja, se añade el nuevo punto a la izquierda o a la derecha del nodo hoja, de nuevo dependiendo de en que lado del plano se encuentra el nuevo punto.
Eliminar elementos de un árbol kd
Eliminar un punto de un árbol kd sin romper el invariante. (POR HACER)
Equilibrar un árbol kd
Hay que ser cuidadoso al equilibrar un árbol kd. Como estos árboles están ordenados en múltiples dimensiones, no se puede emplear la técnica de rotación de árboles para equilibrarlos — esto rompería el invariante.
Usos de un árbol kd
- Implementación en CBR ( Razonamiento Basado En Casos)
Búsqueda ortogonal en un árbol kd
Usar un árbol kd para encontrar todos los puntos que se encuentran en un rectángulo determinado (o análogo de más dimensiones). Esta operación también se denomina rango de búsqueda ortogonal.
Determinar dónde evaluar una superficie
En las regresiones locales es común evaluar la superficie contenida directamente sólo por los vértices del árbol kd e interpolar en algún punto. Este uso, reflejado en la imagen de arriba, busca asegurar que sólo se realizarán las evaluaciones directas necesarias. Como los árboles kd se "adaptan" al espacio, este método puede suministrar una excelente aproximación a las verdaderas superficies de regresión local. Si la aproximación es pobre, puede mejorarse con más subdivisiones.
Complejidad
- Construir un árbol kd estático a partir de n puntos es de O(nlogn).
- Insertar un nuevo punto en un árbol kd balanceado es de O(logn).
- Eliminar un punto de un árbol kd balanceado es de O(logn).
Condición para Usar el Árbol kd
Nótese que se requiere la existencia de un número mínimo de nodos para que la estructura del árbol kd sea útil.
- Por ejemplo, si el nodo más bajo en un árbol 10-d se encuentra en el nivel 9, una de las claves nunca se ha empleado en la construcción del árbol.
- Por ejemplo, si el nodo más bajo en un árbol 10-d se encuentra en el nivel 9, una de las claves nunca se ha empleado en la construcción del árbol.
Una buena regla podría ser:
LA ESTRUCTURA DEL ÁRBOL kd SE USA
SÓLO SI SE CUMPLE QUE N > 22K
No es necesario almacenar el discriminante como un campo en cada nodo; se puede ver que es fácil recordar la historia de los discriminantes que se han utilizado a lo largo del descenso en el árbol kd. Se mantiene en cada nodo para mayor claridad algorítmica.
Algoritmo de Bowyer–Watson es un método para calcular la triangulación de Delaunay de un conjunto finito de puntos en cualquier número de dimensiones. El algoritmo se puede emplear también para construir el Diagrama de Voronoi de los puntos, el cual es el grafo dual de dicha triangulación. El algoritmo es a veces denominado como Algoritmo de Bowyer o Algoritmo de Watson ya que ambos autores, Adrian Bowyer y David Watson, lo desarrollaron de forma independiente al mismo tiempo. Cada uno publicó un artículo sobre el mismo asunto en la revista The Computer Journal.
Descripción del algoritmo
El algoritmo de Bowyer-Watson emplea un método incremental, donde se parte de una triangulación de Delaunay trivial (generalmente un triángulo o un par de triángulos que forman una caja contenedora) a la que se añaden uno a uno los puntos. Después de cada inserción, se eliminan aquellos triángulos cuyo circuncírculo contengan al punto recién introducido. El agujero resultante tiene forma de polígono estrellado simple, el cual puede ser retriangulado alrededor del punto recién insertado.
Si nuestra estructura de datos dispone de información de conectividad entre triángulos, el algoritmo tiene orden O(N log N) operaciones para triangular N puntos, a pesar de que existen casos degenerados especiales donde puede tomar O(N2). El orden en que se insertan los vértices tiene una gran influencia en el tiempo de ejecución del algoritmo, por lo que a veces se realiza una ordenación previa de los mismos acorde a una curva de Hilbert.3
Este algoritmo puede ser sensible a datos de entrada degenerados, como puntos situados en patrones regulares que hacen que la resolución de si un punto está dentro o fuera del circuncírculo de un triángulo dependa de decimales por debajo del umbral de precisión de la representación en coma flotante. Por ello, es recomendable emplear algún test robusto en lugar de comparar distancias euclídeas entre puntos. 4
Explicación gráfica del proceso
Pseudocódigo
function BowyerWatson (pointList)
// pointList es una lista de coordenadas de los puntos de entrada
triangulation := super-triangle // Crea un triángulo suficientemente grande como para contener todos los puntos de entrada
for each point in pointList do // Añade los puntos uno a uno
badTriangles := empty set
for each triangle in triangulation do // busca los triángulos que van a dejar de ser válidos
if point is inside circumcircle of triangle
add triangle to badTriangles
for each triangle in badTriangles do // Elimina los triángulos de la estructura, creando un hueco
remove triangle from triangulation
polygon := empty set
for each triangle in badTriangles do // Calcula la frontera del hueco creado por bad_triangles
for each edge in triangle do
if edge is not shared by any other triangles in badTriangles
add edge to polygon
for each edge in polygon do // re-triangula el hueco usando el nuevo punto.
newTri := form a triangle from edge to point
add newTri to triangulation
for each triangle in triangulation // Limpieza de los triángulos externos a la lista de vértices.
if triangle contains a vertex from original super-triangle
remove triangle from triangulation
return triangulation
No hay comentarios:
Publicar un comentario