Un árbol k -d implícito es un árbol k -d definido implícitamente sobre una cuadrícula rectilínea . Las posiciones y orientaciones de sus planos de división no se dan explícitamente, sino implícitamente, mediante una función de división recursiva definida en los hiperrectángulos que pertenecen a los nodos del árbol . El plano de división de cada nodo interno se posiciona en un plano de cuadrícula de la cuadrícula subyacente, lo que divide la cuadrícula del nodo en dos subcuadrículas.
Los términos " árbol k -d min/max " y " árbol k -d implícito" a veces se confunden. Esto se debe a que la primera publicación que utilizó el término "árbol k -d implícito" [1] en realidad utilizó árboles k -d min/max explícitos, pero se refirió a ellos como " árboles k -d implícitos" para indicar que se pueden utilizar para trazar rayos de superficies iso dadas implícitamente. Sin embargo, esta publicación también utilizó árboles k -d delgados que son un subconjunto de los árboles k -d implícitos con la restricción de que solo se pueden construir sobre hiperrectángulos enteros con longitudes laterales que sean potencias de dos. Los árboles k -d implícitos como se definen aquí se han introducido recientemente, con aplicaciones en gráficos de computadora. [2] [3] Como es posible asignar atributos a los nodos de árboles k -d implícitos, se puede hacer referencia a un árbol k -d implícito que tiene valores min/max asignados a sus nodos como un "árbol k -d min/max implícito ".
Los árboles k -d implícitos generalmente no se construyen explícitamente. Al acceder a un nodo, la orientación y la posición de su plano de división se evalúan utilizando la función de división específica que define el árbol. Diferentes funciones de división pueden generar diferentes árboles para la misma cuadrícula subyacente.
Las funciones de división pueden adaptarse a propósitos especiales. A continuación se describen dos especificaciones de clases de funciones de división especiales.
Una función de división completa es, por ejemplo, la función de división de la mediana de la cuadrícula . Crea árboles k -d implícitos bastante equilibrados mediante el uso de hiperrectángulos enteros de dimensión k hyprec[2][k] que pertenecen a cada nodo del árbol k -d implícito. Los hiperrectángulos definen qué celdas de la cuadrícula de la cuadrícula rectilínea pertenecen a su nodo correspondiente. Si el volumen de este hiperrectángulo es igual a uno, el nodo correspondiente es una celda de cuadrícula única y, por lo tanto, no se subdivide más y se marca como nodo hoja. De lo contrario, la extensión más larga del hiperrectángulo se elige como orientación o . El plano de división correspondiente p se coloca sobre el plano de cuadrícula que está más cerca de la mediana de la cuadrícula del hiperrectángulo a lo largo de esa orientación.
Orientación del plano dividido o :
o = min{argmax(i = 1 ... k : (hyprec[1][i] - hyprec[0][i]))}Posición del plano dividido p :
p = redondearAbajo((hyprec[0][o] + hyprec[1][o]) / 2)
Una ventaja de los árboles k -d implícitos es que las orientaciones y posiciones de sus planos divididos no necesitan almacenarse explícitamente.
Pero algunas aplicaciones requieren, además de las orientaciones y posiciones del plano de división, otros atributos en los nodos del árbol interno. Estos atributos pueden ser, por ejemplo, bits individuales o valores escalares individuales que definen si las subcuadrículas que pertenecen a los nodos son de interés o no. Para árboles k- d implícitos completos, es posible preasignar una matriz de atributos de tamaño correcto y asignar cada nodo interno del árbol a un elemento único en esa matriz asignada.
La cantidad de celdas de la cuadrícula es igual al volumen del hiperrectángulo entero que pertenece a la cuadrícula. Como un árbol k- d implícito completo tiene un nodo interno menos que celdas de la cuadrícula, se sabe de antemano cuántos atributos se deben almacenar. La relación " Volumen del hiperrectángulo entero con respecto a los nodos internos " define, junto con la función de división completa, una fórmula recursiva que asigna a cada plano de división un elemento único en la matriz asignada. El algoritmo correspondiente se proporciona en el código pseudo C a continuación.
// Asignación de atributos a los nodos internos de un árbol kd implícito completo// crea un hiperrectángulo entero de ayuda hyprec (su volumen vol(hyprec) es igual a la cantidad de hojas) int hyprec [ 2 ][ k ] = { { 0 , ..., 0 }, { length_1 , ..., length_k } }; // asigna una vez la matriz de atributos para todo el árbol kd implícito attr * a = new attr [ volume ( hyprec ) - 1 ]; attr implicitKdTreeAttributes ( int hyprec [ 2 ][ k ], attr * a ) { if ( vol ( hyprec ) > 1 ) // el nodo actual es un nodo interno { // evalúa la orientación o del plano de división y su posición p usando la función de división completa subyacente int o , p ; completeSplittingFunction ( hyprec , & o , & p ); // evalúa los hiperrectángulos enteros de los hijos hyprec_l y hyprec_r int hyprec_l [ 2 ][ k ], hyprec_r [ 2 ][ k ]; hyprec_l = hyprec ; hyprec_l [ 1 ][ o ] = p ; hyprec_r = hyprec ; hyprec_r [ 0 ][ o ] = p ; // evalúa la ubicación de memoria de los hijos a_l y a_r attr * a_l = a + 1 ; attr * a_r = a + vol ( hyprec_l ); // evaluar recursivamente los atributos de los hijos c_l y c_r attr c_l = implicitKdTreeAttributes ( hyprec_l , a_l ); attr c_r = implicitKdTreeAttributes ( hyprec_r , a_r ); // fusionar los atributos de los hijos con el atributo actual c attr c = merge ( c_l , c_r ); // almacenar el atributo actual y retornarlo a [ 0 ] = c ; return c ; } // El nodo actual es un nodo hoja. Devuelve el atributo que pertenece a la celda de la cuadrícula correspondiente return attribute ( hyprec ); } Cabe mencionar que este algoritmo funciona para todas las cuadrículas rectilíneas. El hiperrectángulo entero correspondiente no necesariamente tiene que tener lados que sean potencias de dos.
Los árboles implícitos max- k -d se utilizan para la proyección de isosuperficies de rayos /MIP ( proyección de intensidad máxima ). El atributo asignado a cada nodo interno es el valor escalar máximo dado en la subcuadrícula que pertenece al nodo. Los nodos no se recorren si sus valores escalares son menores que el valor iso buscado/intensidad máxima actual a lo largo del rayo. Los bajos requisitos de almacenamiento del árbol implícito max- k -d y la favorable complejidad de visualización de la proyección de rayos permiten proyectar rayos (e incluso cambiar la isosuperficie) en campos escalares muy grandes a velocidades de cuadros interactivas en PC de consumo. De manera similar, se puede utilizar un árbol implícito min/max kd para evaluar de manera eficiente consultas como la línea de visión del terreno . [4]
Dado un árbol k -d implícito distribuido en una cuadrícula k -dimensional con n celdas de cuadrícula.
