vizinho mais próximo - k-d árvore - prova wikipedia

Question

Na data de entrada wikipedia para árvores kd , um algoritmo é apresentado para fazendo uma pesquisa vizinho mais próximo em uma árvore kd. O que eu não entendo é a explicação do passo 3.2. Como você sabe que não há um ponto mais próximo só porque a diferença entre a divisão coordenada do ponto de busca e o nó atual é maior do que a diferença entre a divisão coordenada do ponto de busca e o atual melhor?

vizinho mais próximo busca Animação busca NN com uma árvore de KD em 2D

O vizinho mais próximo (NN) algoritmo visa encontrar o ponto na árvore que é mais próxima para uma dada entrada ponto. Esta pesquisa pode ser feito eficientemente usando a árvore Propriedades para eliminar rapidamente grande porções do espaço de busca. Procurando por um vizinho mais próximo em um kd-árvores prossegue da seguinte forma:

1. Começando com o nó raiz, o algoritmo move-se para baixo da árvore recursiva, da mesma forma que faria se o ponto de busca estavam sendo inserido (isto é, que vai para a direita ou esquerda dependendo se o ponto é maior ou menor que o nó atual na dimensão split).
2. Uma vez que o algoritmo atinge um nó folha, ele salva nesse ponto nó como o "atual melhor"
3. O algoritmo desenrola a recursividade da árvore, realizando a seguindo os passos em cada nó: 1. Se o nó atual está mais perto do que o atual melhor, então ele torna-se o atual melhor. 2. O algoritmo verifica se poderia haver quaisquer pontos sobre o outro lado do plano de divisão que estão mais perto do ponto de pesquisa que o atual melhor. Em conceito, isso é feito cruzando o hiperplana divisão com um hiperesfera em torno do ponto de pesquisa que tem um raio igual à corrente distância mais próxima. Desde o hiperplanos são todos eixo alinhado este é implementado como uma simples comparação para ver se a diferença entre a divisão de coordenadas da pesquisa ponto e nó atual é inferior a a distância (coordenadas globais) do ponto de busca para a corrente melhor. 1. Se o hiperesfera cruza o plano, pode haver pontos mais próximos do outro lado do avião, de modo que o algoritmo deve mover para baixo o outro ramo da árvore do nó atual procurando mais perto pontos, seguindo a mesma recursiva processar como toda a pesquisa. 2. Se o hiperesfera não interceptam o plano de divisão, em seguida, o algoritmo continua curta a árvore, e todo o ramo do outro lado do nó que é eliminadas.
4. Quando o algoritmo termina este processo para o nó raiz, em seguida, o pesquisa for concluída.

Geralmente, o algoritmo usa quadrado distâncias para comparação Para evitar computar raízes quadradas. Além disso, ele pode salvar computação mantendo o quadrado melhor distância atual em um variável para comparação.

Answer 1

Olhe atentamente para a 6ª quadro do animação nessa página .

Como o algoritmo vai voltar até a recursividade, é possível que haja um ponto mais próximo do outro lado do hiperplano que ele está ligado. Checamos um meio, mas poderia haver um ponto ainda mais perto na outra metade.

Bem, acontece que às vezes podemos fazer uma simplificação. Se é impossível para que haja um ponto sobre a outra metade mais perto do nosso melhor ponto (mais próximo) atual, então podemos ignorar que metade hyperplane inteiramente. Esta simplificação é o mostrado no 6º quadro.

Descobrir se esta simplificação é possível é feito comparando a distância do hiperplano para o nosso local de pesquisa. Porque o hiperplano está alinhado aos eixos, a linha mais curta do que a qualquer outro ponto será uma linha ao longo de uma dimensão, para que possamos comparar apenas a coordenada da dimensão que os splits hiperplano.

Se é mais distante do ponto de pesquisa para o hiperplano que do ponto de pesquisa para o seu ponto mais próximo atual, então não há nenhuma razão para procurar passado que a divisão de coordenadas.

Mesmo que a minha explicação não ajuda, a vontade gráfico. Boa sorte em seu projeto!

Answer 2

Sim, a descrição da pesquisa em uma árvore KD na Wikipedia NN (vizinho mais próximo) é um pouco difícil de seguir. Não ajuda que a muito do topo Search Google resultados em pesquisas NN KD árvore está errado simplesmente!

Eis alguns C ++ código para mostrar-lhe como obtê-lo direito:

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 busca em uma árvore 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;
}

função de distância padrão:

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: algumas pessoas estão pedindo ajuda com as estruturas de dados também (não apenas o algoritmo NN), então aqui é o que eu usei. Dependendo da sua finalidade, você pode querer modificar as estruturas de dados ligeiramente. (Nota:. Mas você quase certamente fazer não quiser modificar o algoritmo NN)

classe 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;
};

classe 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;
};

classe KDTree: (Nota:. Você precisa adicionar uma função membro para construir / encher seu árvores)

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;
};