vicino più vicino - albero k-d - prova wikipedia

Question

Sulla voce wikipedia per alberi kd , viene presentato un algoritmo per facendo una ricerca del vicino più vicino su un albero kd. Quello che non capisco è la spiegazione del passaggio 3.2. Come fai a sapere che non esiste un punto più vicino solo perché la differenza tra la coordinata di divisione del punto di ricerca e il nodo corrente è maggiore della differenza tra la coordinata di divisione del punto di ricerca e la migliore corrente?

  

Ricerca vicino più vicino Animazione di   NN cerca con un albero KD in 2D

     

L'algoritmo del vicino più vicino (NN)   mira a trovare il punto nell'albero   che è il più vicino a un dato input   punto. Questa ricerca può essere fatta   in modo efficiente usando l'albero   proprietà per eliminare rapidamente grandi   porzioni dello spazio di ricerca.   Alla ricerca del vicino più vicino in a   kd-tree procede come segue:

     

  
1. A partire dal nodo radice, l'algoritmo si sposta verso il basso dell'albero   ricorsivamente, nello stesso modo in cui   sarebbe se il punto di ricerca fosse   inserito (cioè va a destra o a sinistra   a seconda che il punto sia   maggiore o minore del nodo corrente   nella dimensione divisa).
  
2. Una volta che l'algoritmo raggiunge un nodo foglia, salva quel punto nodo come   il "meglio corrente"
  
3. L'algoritmo svolge la ricorsione dell'albero, eseguendo il file   seguenti passaggi in ciascun nodo:        1. Se il nodo corrente è più vicino del migliore attuale, allora   diventa il migliore attuale.        2. L'algoritmo controlla se potrebbero esserci dei punti   l'altro lato del piano di scissione   che sono più vicini al punto di ricerca   rispetto al meglio attuale. Nel concetto,   questo viene fatto intersecando il   suddivisione dell'iperpiano con a   ipersfera attorno al punto di ricerca   che ha un raggio uguale alla corrente   distanza più vicina. Dal momento che il   gli iperpiani sono tutti allineati sugli assi   è implementato come un semplice confronto   per vedere se la differenza tra   la coordinata di divisione della ricerca   punto e nodo corrente è inferiore a   la distanza (coordinate generali)   dal punto di ricerca alla corrente   migliore.              1. Se l'ipersfera attraversa il piano, potrebbe esserci   punti più vicini dall'altra parte del   piano, quindi l'algoritmo deve spostarsi verso il basso   l'altro ramo dell'albero dal   nodo corrente in cerca di più vicino   punti, seguendo lo stesso ricorsivo   processo come l'intera ricerca.              2. Se l'ipersfera non interseca il piano di divisione,   quindi l'algoritmo continua a camminare   sull'albero e su tutto il ramo   l'altro lato di quel nodo è   eliminato.
  
4. Quando l'algoritmo termina questo processo per il nodo radice, quindi il   la ricerca è completa.
  

     

Generalmente l'algoritmo utilizza il quadrato   distanze da confrontare per evitare   calcolo radici quadrate. Inoltre,   può salvare il calcolo tenendo premuto il tasto   distanza migliore corrente quadrata in a   variabile per il confronto.

Answer 1

Guarda attentamente il sesto fotogramma dell'animazione in quella pagina .

Mentre l'algoritmo sta risalendo la ricorsione, è possibile che ci sia un punto più vicino sull'altro lato dell'iperpiano su cui si trova. Abbiamo verificato la metà, ma potrebbe esserci un punto ancora più vicino sull'altra metà.

Bene, a volte possiamo fare una semplificazione. Se è impossibile che ci sia un punto sull'altra metà più vicino del nostro punto migliore (più vicino) attuale, allora possiamo saltare completamente quella metà dell'iperpiano. Questa semplificazione è quella mostrata nel sesto frame.

Capire se questa semplificazione è possibile viene confrontato la distanza dall'iperpiano alla nostra posizione di ricerca. Poiché l'iperpiano è allineato agli assi, la linea più corta da esso a qualsiasi altro punto sarà una linea lungo una dimensione, in modo da poter confrontare solo le coordinate della dimensione che l'iperpiano divide.

Se è più lontano dal punto di ricerca sull'iperpiano che dal punto di ricerca al punto più vicino attuale, non c'è motivo di cercare oltre quella coordinata di divisione.

Anche se la mia spiegazione non aiuta, la grafica lo farà. Buona fortuna per il tuo progetto!

Answer 2

Sì, la descrizione della ricerca NN (prossimo più vicino) in un albero KD su Wikipedia è un po 'difficile da seguire. Non aiuta che un lotto dei migliori risultati di ricerca di Google nelle ricerche di NN KD Tree sia semplicemente sbagliato!

Ecco un po 'di codice C ++ per mostrarti come farlo nel modo giusto:

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 per la ricerca NN su un albero 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;
}

Funzione di distanza predefinita:

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

Modifica: alcune persone chiedono aiuto anche con le strutture dati (non solo con l'algoritmo NN), quindi ecco quello che ho usato. A seconda del tuo scopo, potresti voler modificare leggermente le strutture dei dati. (Nota: ma quasi certamente non vuoi modificare l'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: dovrai aggiungere una funzione membro per compilare / riempire il tuo albero.)

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