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

Question

Sul numero wikipedia entry for k-d trees, viene presentato un algoritmo per eseguire una ricerca vicino più vicino su un albero k-d. Quello che non capisco è la spiegazione del passo 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 corrente migliore?

MODIFICA: testo aggiunto dell'articolo di Wikipedia in questione nel caso in cui venga successivamente modificato su Wikipedia.

più vicina di ricerca vicino Animazione di NN ricerca con un albero di KD in 2D

Il più vicino (NN) algoritmo ha lo scopo di trovare il punto nell'albero che è più vicino ad un ingresso determinato punto . Questa ricerca può essere effettuata in modo efficiente tramite utilizzando le proprietà dell'albero per eliminare rapidamente le grandi porzioni dello spazio di ricerca . Ricerca di un vicino più prossimo in un procede KD-albero come segue:

1. A partire dal nodo radice, l'algoritmo sposta verso il basso l'albero in modo ricorsivo, nello stesso modo in cui sarebbe se il punto di ricerca sono stati inserito inserito (vale a dire va a destra o sinistra a seconda se il punto è maggiore o minore del nodo corrente nella dimensione divisa).
2. volta che l'algoritmo raggiunge un nodo foglia, si salva quel punto nodo come "corrente migliore"
3. L'algoritmo svolge la ricorsione dell'albero, effettuare le seguenti operazioni ad ogni nodo: 1. Se la corrente il nodo è più vicino del migliore attuale, quindi lo diventa il migliore corrente. 2. L'algoritmo controlla se ci possono essere dei punti su sull'altro lato del piano di divisione più vicini al punto di ricerca . Nel concetto, interseca l'iperpiano splittato con un'ipersfera intorno al punto di ricerca che ha un raggio uguale all'attuale distanza più vicina. Poiché le iperpiani degli assi allineati questo è implementato come un semplice confronto per vedere se la differenza tra coordinata scissione del punto di ricerca e nodo corrente è inferiore la distanza (coordinate globali) dalla ricerca puntare all'attuale migliore. 1. Se l'ipersfera attraversa il piano, ci potrebbero essere più vicini punti sull'altro lato del piano , quindi l'algoritmo deve spostare verso il basso l'altro ramo dell'albero al nodo corrente cerchi più stretti punti, seguendo lo stesso processo ricorsivo come l'intera ricerca. 2. Se l'ipersfera non interseca il piano di divisione, , l'algoritmo continua a camminare su nell'albero e l'intero ramo su l'altro lato del nodo è eliminato.
4. Quando l'algoritmo termina questo processo per il nodo radice, la ricerca è completa.

Generalmente gli usi algoritmo quadrati distanze per il confronto, per evitare calcolo radici quadrate. Inoltre, è possibile salvare il calcolo tenendo la distanza migliore corrente quadrata in una variabile per il confronto.

Answer 1

Osservare attentamente il sesto fotogramma di animation on that page.

Mentre l'algoritmo sta eseguendo il backup della ricorsione, è possibile che ci sia un punto più vicino sull'altro lato dell'iperplano su cui si trova. Abbiamo controllato la metà, ma potrebbe esserci un punto ancora più vicino nell'altra metà.

Bene, a volte si può fare una semplificazione. Se è impossibile perché ci sia un punto nell'altra metà più vicino del nostro attuale punto migliore (più vicino), possiamo saltare l'iperpiano per metà. Questa semplificazione è quella mostrata sul sesto frame.

Determinare se questa semplificazione è possibile viene eseguita confrontando la distanza dall'iperplano alla posizione di ricerca. Poiché l'iperpiano è allineato agli assi, la linea più corta da essa a qualsiasi altro punto sarà una linea lungo una dimensione, in modo da poter confrontare solo la coordinata della dimensione che l'iperpiano si divide.

Se è più lontano dal punto di ricerca verso l'iperpiano che dal punto di ricerca al punto corrente più vicino, 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 (Nearest Neighbor) in un albero KD su Wikipedia è un po 'difficile da seguire. Non aiuta che un lotto dei primi risultati di ricerca di Google sulle ricerche dell'albero NN KD sia semplicemente sbagliato!

Ecco po 'di codice C++ per mostrare come farlo bene:

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 NN ricerca su un albero asciutto:

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

predefinito funzione di distanza:

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 stanno chiedendo aiuto anche con le strutture dati (non solo l'algoritmo NN), quindi ecco cosa ho ho usato A seconda del tuo scopo, potresti voler modificare leggermente le strutture dei dati. (Nota: ma quasi certamente fai 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:. Avrete bisogno di aggiungere una funzione membro per costruire/riempire il vostro 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; 
};