のKdツリー欠陥K最近傍

Question

が

免責事項：いくつかの悪い習慣は、この次のコード

こんにちはであり、私はちょうど正しく私のKDツリーK最近傍探索をフォーマットする方法についていくつかの質問を持っていました。私の関数の例を次に示します。

void nearest_neighbor(Node *T, int K) { 
    if (T == NULL) return; 
    nearest_neighbor(T->left, K); 
    //do stuff find dist etc 
    if(?)nearest_neighbor(T->right, K); 
} 

このコードは混乱するので、私はそれを説明しようとします。私の関数は、k値とノードTだけをとります。私がしようとしているのは、現在のノードと構造内の他のすべての値との距離を見つけることです。これらはすべて動作します、私が持っている問題は、いつ、どのように再帰呼び出しnearest_neighbor（T-> left/T-> right、K）を呼び出すかを理解することです。私は右辺へのコールを切り取ることを意図していますが、これを行う方法がわかりません。これは、多次元KDツリーです。より良い例へのガイダンスは非常に高く評価されます。

Answer 1

Wikipediaがあなたの特定の質問のために、この場所を、と言うように私は実装でき助言する：

ルートノードから開始は、このアルゴリズムは、それがあろうと同じように、再帰的にツリー を下に移動検索ポイントが である場合（すなわち、 ポイントが現在のノードよりも小さいか大きいかに応じて左右に移動する場合は、 ディメンション）。

が質問に答えます。もちろん、あなたが心の中でこのイメージを持つことができます。

あなたは例のように多くの2次元を持っている場合、あなたは、単に第3に、そして第二に、最初の次元に分割

、その後、最後に、最終的な次元に到達すると、再び最初の次元から始めます。

Answer 2

一般的な考え方は、ターゲットに最も近いグローバルポイントを維持し、新たに発見されたポイントで更新し、すでに見つかったターゲットに最も近いポイントを含むことができないnゴンに降下しないことです。 C++ではなくC言語で表示します。オブジェクト指向のフォームに簡単に変換できます。

#define N_DIM <k for the k-D tree> 

typedef float COORD; 

typedef struct point_s { 
    COORD x[N_DIM]; 
} POINT; 

typedef struct node_s { 
    struct node_s *lft, *rgt; 
    POINT p[1]; 
} NODE; 

POINT target[1]; // target for nearest search 
POINT nearest[1]; // nearest found so far 
POINT b0[1], b1[1]; // search bounding box 

bool prune_search() { 
    // Return true if no point in the bounding box [b0..b1] is closer 
    // to the target than than the current value of nearest. 
} 

void search(NODE *node, int dim); 

void search_lft(NODE *node, int dim) { 
    if (!node->lft) return; 
    COORD save = b1->p->x[dim]; 
    b1->p->x[dim] = node->p->x[dim]; 
    if (!prune_search()) search(node->lft, (dim + 1) % N_DIM); 
    b1->p->x[dim] = save; 
} 

void search_rgt(NODE *node, int dim) { 
    if (!node->rgt) return; 
    COORD save = b0->p->x[dim]; 
    b0->p->x[dim] = node->p->x[dim]; 
    if (!prune_search()) search(node->rgt, (dim + 1) % N_DIM); 
    b0->p->x[dim] = save; 
} 

void search(NODE *node, int dim) { 
    if (dist(node->p, target) < dist(nearest, target)) *nearest = *node->p; 
    if (target->p->x[dim] < node->p->x[dim]) { 
    search_lft(node, dim); 
    search_rgt(node, dim); 
    } else { 
    search_rgt(node, dim); 
    search_lft(node, dim); 
    } 
} 

/** Set *nst to the point in the given kd-tree nearest to tgt. */ 
void get_nearest(POINT *nst, POINT *tgt, NODE *root) {  
    *b0 = POINT_AT_NEGATIVE_INFINITY; 
    *b1 = POINT_AT_POSITIVE_INFINITY; 
    *target = *tgt; 
    *nearest = *root->p; 
    search(root, 0); 
    *nst = *nearest; 
} 

注これは最も経済的な実装ではありません。単純化のため、不要な最新の更新とプルーニングの比較を行います。しかし、その漸近的な性能は、kd-tree NNに期待される通りです。これを有効にしたら、それを基本実装として使用して余分な比較を絞り出すことができます。