vecino más cercano - árbol k-d - prueba de wikipedia

Question

En el wikipedia entry for k-d trees, se presenta un algoritmo para realizar una búsqueda de vecino más cercano en un árbol k-d. Lo que no entiendo es la explicación del paso 3.2. ¿Cómo se puede saber que no hay un punto más cercano solo porque la diferencia entre la coordenada de división del punto de búsqueda y el nodo actual es mayor que la diferencia entre la coordenada de división del punto de búsqueda y la mejor corriente?

EDITAR: Agregó el texto del artículo de Wikipedia en cuestión en caso de que se cambie más tarde en Wikipedia.

más cercano Animación búsqueda del vecino de NN búsqueda con un árbol kd en 2D

El vecino más cercano (NN) algoritmo tiene como objetivo encontrar el punto en el árbol que está más próxima a una entrada punto dado . Esta búsqueda se puede hacer de manera eficiente utilizando las propiedades de árbol para eliminar rápidamente porciones grandes del espacio de búsqueda. La búsqueda de un vecino más cercano en un procede kd-árbol de la siguiente manera:

1. Comenzando con el nodo raíz, el algoritmo se mueve hacia abajo el árbol de forma recursiva, de la misma manera que sería si el punto de búsqueda se siendo insertado (es decir, va a la derecha o izquierda dependiendo de si el punto es mayor o menor que el nodo actual en la dimensión dividida).
2. Una vez que el algoritmo llega a un nodo hoja, se ahorra ese punto nodo como la "corriente mejor"
3. El algoritmo desenrolla la recursividad del árbol, realizando los siguientes pasos en cada nodo: 1. Si la corriente el nodo está más cerca que el mejor actual, entonces se convierte en el mejor actual. 2. El algoritmo comprueba si podría haber puntos en del otro lado del plano de división que están más cerca del punto de búsqueda que los mejores actuales. En concepto, esto se hace al intersectar el hiperplano de división con una hiperesfera alrededor del punto de búsqueda que tiene un radio igual a la distancia más cercana a . Dado que los hiperplanos son todos los ejes alineados este se implementa como una simple comparación para ver si la diferencia entre coordinar la división del punto de búsqueda y el nodo actual es menor que la distancia (coordenadas globales) partir de la búsqueda apunte a la actual mejor. 1. Si el hiperesfera cruza el plano, podría haber más cercanas puntos en el otro lado del plano , por lo que el algoritmo debe moverse hacia abajo la otra rama del árbol del nodo actual buscando estrechar puntos, siguiendo el mismo proceso recursivo como toda la búsqueda. 2. Si la hiperesfera no se cruza con el plano de división, , el algoritmo continúa caminando en el árbol y la rama completa en al otro lado de ese nodo es eliminada.
4. Cuando el algoritmo finaliza este proceso para el nodo raíz, se completa la búsqueda .

En general los usos de algoritmo cuadrados distancias para la comparación de computación para evitar raíces cuadradas. Además, puede guardar el cálculo manteniendo la mejor distancia al cuadrado actual en una variable para comparar.

Answer 1

Mire con atención el 6º fotograma del animation on that page.

Como el algoritmo está volviendo a la recursión, es posible que haya un punto más cercano en el otro lado del hiperplano en el que se encuentra. Hemos marcado la mitad, pero podría haber un punto aún más cercano en la otra mitad.

Bueno, resulta que a veces podemos hacer una simplificación. Si es imposible para que haya un punto en la otra mitad más cerca que nuestro mejor punto actual (más cercano), entonces podemos omitir ese hiperplano la mitad por completo. Esta simplificación es la que se muestra en el 6º cuadro.

Averiguar si esta simplificación es posible se hace comparando la distancia desde el hiperplano a nuestra ubicación de búsqueda. Debido a que el hiperplano está alineado con los ejes, la línea más corta desde este hasta cualquier otro punto será una línea a lo largo de una dimensión, por lo que podemos comparar solo la coordenada de la dimensión que divide el hiperplano.

Si está más lejos del punto de búsqueda al hiperplano que del punto de búsqueda al punto más cercano actual, entonces no hay razón para buscar más allá de esa coordenada de división.

Incluso si mi explicación no ayuda, el gráfico lo hará. ¡Buena suerte en tu proyecto!

Answer 2

Sí, la descripción de la búsqueda NN (vecino más cercano) en un árbol KD en Wikipedia es un poco difícil de seguir. ¡No ayuda que un lote de los mejores resultados de búsqueda de Google en las búsquedas de NN KD Tree sean simplemente incorrectos!

Aquí hay algo de código C++ para mostrar cómo hacer las cosas bien:

template <class T, std::size_t N> 
void KDTree<T,N>::nearest (
    const const KDNode<T,N> &node, 
    const std::array<T, N> &point, // looking for closest node to this point 
    const KDPoint<T,N> &closest, // closest node (so far) 
    double &minDist, 
    const uint depth) const 
{ 
    if (node->isLeaf()) { 
     const double dist = distance(point, node->leaf->point); 
     if (dist < minDist) { 
      minDist = dist; 
      closest = node->leaf; 
     } 
    } else { 
     const T dim = depth % N; 
     if (point[dim] < node->splitVal) { 
      // search left first 
      nearest(node->left, point, closest, minDist, depth + 1); 
      if (point[dim] + minDist >= node->splitVal) 
       nearest(node->right, point, closest, minDist, depth + 1); 
     } else { 
      // search right first 
      nearest(node->right, point, closest, minDist, depth + 1); 
      if (point[dim] - minDist <= node->splitVal) 
       nearest(node->left, point, closest, minDist, depth + 1); 
     } 
    } 
} 

API para NN buscar en un árbol de KD:

// Nearest neighbour 
template <class T, std::size_t N> 
const KDPoint<T,N> KDTree<T,N>::nearest (const std::array<T, N> &point) const { 
    const KDPoint<T,N> closest; 
    double minDist = std::numeric_limits<double>::max(); 
    nearest(root, point, closest, minDist); 
    return closest; 
} 

defecto de la función distancia:

template <class T, std::size_t N> 
double distance (const std::array<T, N> &p1, const std::array<T, N> &p2) { 
    double d = 0.0; 
    for (uint i = 0; i < N; ++i) { 
     d += pow(p1[i] - p2[i], 2.0); 
    } 
    return sqrt(d); 
} 

Editar: algunas personas también piden ayuda con las estructuras de datos (no solo con el algoritmo NN), así que aquí está lo que tengo ve usado. Dependiendo de su propósito, es posible que desee modificar ligeramente las estructuras de datos. (Nota: pero es casi seguro que no desea modificar el algoritmo NN.)

clase

KDPoint:

template <class T, std::size_t N> 
class KDPoint { 
    public: 
     KDPoint<T,N> (std::array<T,N> &&t) : point(std::move(t)) { }; 
     virtual ~KDPoint<T,N>() = default; 
     std::array<T, N> point; 
}; 

clase KDNode:

template <class T, std::size_t N> 
class KDNode 
{ 
    public: 
     KDNode() = delete; 
     KDNode (const KDNode &) = delete; 
     KDNode & operator = (const KDNode &) = delete; 
     ~KDNode() = default; 

     // branch node 
     KDNode (const T      split, 
       std::unique_ptr<const KDNode> &lhs, 
       std::unique_ptr<const KDNode> &rhs) : splitVal(split), left(std::move(lhs)), right(std::move(rhs)) { }; 
     // leaf node 
     KDNode (std::shared_ptr<const KDPoint<T,N>> p) : splitVal(0), leaf(p) { }; 

     bool isLeaf (void) const { return static_cast<bool>(leaf); } 

     // data members 
     const T         splitVal; 
     const std::unique_ptr<const KDNode<T,N>> left, right; 
     const std::shared_ptr<const KDPoint<T,N>> leaf; 
}; 

clase KDTree: (Nota:. Tendrá que añadir una función miembro para construir/llenar su árbol)

template <class T, std::size_t N> 
class KDTree { 
    public: 
     KDTree() = delete; 
     KDTree (const KDTree &) = delete; 
     KDTree (KDTree &&t) : root(std::move(const_cast<std::unique_ptr<const KDNode<T,N>>&>(t.root))) { }; 
     KDTree & operator = (const KDTree &) = delete; 
     ~KDTree() = default; 

     const KDPoint<T,N> nearest (const std::array<T, N> &point) const; 

     // Nearest neighbour search - runs in O(log n) 
     void nearest (const std::unique_ptr<const KDNode<T,N>> &node, 
         const std::array<T, N> &point, 
         std::shared_ptr<const KDPoint<T,N>> &closest, 
         double &minDist, 
         const uint depth = 0) const; 

     // data members 
     const std::unique_ptr<const KDNode<T,N>> root; 
};