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. То, что я пытаюсь сделать, - найти расстояние между текущим узлом и любым другим значением в структуре. Все эти работы, проблема, с которой я сталкиваюсь, заключается в понимании того, когда и как вызывать рекурсивные вызовы near_neighbor (T-> left/T-> right, K) Я знаю, что я намерен обрезать вызовы с правой стороны, Не знаю, как это сделать. Между прочим, это многомерное дерево KD. Любое руководство к лучшим примерам будет очень оценено.

Answer 1

Я бы посоветовал вам реализовать как Wikipedia говорит, где для вашего конкретного вопроса, это:

Начиная с корневого узла, алгоритм движется вниз по дереву рекурсивно, таким же образом, что это будет если точка поиска была вставлена ​​в (т.е. она идет влево или вправо в зависимости от того, меньше ли точка , чем текущий узел в раздроблении ).

отвечает на вопрос. Конечно, вы можете иметь это изображение в виде:

где, если у вас есть еще два измерения, как в примере, вы просто разделить в первом измерении, то во второй, а затем в третьем, затем в четвертом и т. д., а затем вы следуете циклической политике, так что, когда вы достигнете финального измерения, вы снова начнете с первого измерения.

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-дерева NN. После того, как вы получите эту работу, вы можете использовать ее в качестве базовой реализации, чтобы выжать дополнительные сравнения.