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

Question

En la entrada de wikipedia para árboles kd , se presenta un algoritmo para haciendo una búsqueda de vecino más cercano en un árbol kd. Lo que no entiendo es la explicación del paso 3.2. ¿Cómo sabe 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 actual?

  

Búsqueda de vecino más cercano Animación de   NN buscando con un árbol KD en 2D

     

El algoritmo vecino más cercano (NN)   tiene como objetivo encontrar el punto en el árbol   que está más cerca de una entrada dada   punto. Esta búsqueda puede hacerse   eficientemente usando el árbol   propiedades para eliminar rápidamente grandes   porciones del espacio de búsqueda.   Buscando un vecino más cercano en un   kd-tree procede de la siguiente manera:

     

  
1. Comenzando con el nodo raíz, el algoritmo se mueve hacia abajo en el árbol   recursivamente, de la misma manera que   lo haría si el punto de búsqueda estuviera 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, guarda ese punto de nodo como   el " mejor actual "
  
3. El algoritmo desenrolla la recursividad del árbol, realizando el   siguientes pasos en cada nodo:        1. Si el nodo actual está más cerca que el mejor actual, entonces   se convierte en el mejor actual.        2. El algoritmo verifica si podría haber algún punto en   el otro lado del plano de división   que están más cerca del punto de búsqueda   que el mejor actual. En concepto,   esto se hace intersectando el   dividir el hiperplano con un   hiperesfera alrededor del punto de búsqueda   que tiene un radio igual al actual   distancia más cercana Desde el   hiperplanos están todos alineados este eje   se implementa como una simple comparación   para ver si la diferencia entre   la coordenada divisoria de la búsqueda   punto y nodo actual es menor que   la distancia (coordenadas generales)   desde el punto de búsqueda hasta el actual   mejor.              1. Si la hiperesfera cruza el avión, podría haber   puntos más cercanos al otro lado de la   plano, por lo que el algoritmo debe moverse hacia abajo   la otra rama del árbol de la   nodo actual buscando más cerca   puntos, siguiendo el mismo recursivo   proceso como toda la búsqueda.              2. Si la hiperesfera no se cruza con el plano de división,   entonces el algoritmo continúa caminando   arriba del árbol, y toda la rama en   el otro lado de ese nodo es   eliminado.
  
4. Cuando el algoritmo finaliza este proceso para el nodo raíz, entonces el   la búsqueda está completa.
  

     

Generalmente el algoritmo usa cuadrado   distancias de comparación para evitar   calcular raíces cuadradas Adicionalmente,   puede guardar la computación manteniendo presionada la tecla   mejor distancia al cuadrado actual en un   variable para comparación.

Answer 1

Mire cuidadosamente el sexto cuadro de la animación en esa página .

A medida que el algoritmo vuelve a subir la recursividad, es posible que haya un punto más cercano al otro lado del hiperplano en el que se encuentra. Hemos verificado una 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 que haya un punto en la otra mitad más cerca que nuestro mejor punto (el más cercano) actual, entonces podemos omitir esa mitad del hiperplano por completo. Esta simplificación es la que se muestra en el sexto cuadro.

Averiguar si esta simplificación es posible se realiza 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 él a 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 de 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 principales resultados de búsqueda de Google en las búsquedas de NN KD Tree sean simplemente incorrectos!

Aquí hay un código C ++ para mostrarle cómo hacerlo 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 buscando en un árbol 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;
}

Función de distancia predeterminada:

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 están pidiendo ayuda con las estructuras de datos (no solo el algoritmo NN), así que esto es lo que he 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: necesitará agregar 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;
};