Nächster Nachbar mit KDtree

Question

Ich weiß, wie man einen kd-Baum bauen. Aber das Problem, das ich gegenüberstelle, ist, wie man nächsten Nachbarn mit KD Tree.Ich habe auf Google gesucht, aber nicht in der Lage, Code zum Finden der nächsten Nachbarn zu finden Algos sind gegeben. Aber ich habe Schwierigkeiten, diesen Algo aufgrund der Sprache in Code umzuwandeln.

Können Sie mir bitte verständlich Code für NNSearch in Java zur Verfügung stellen?

Answer 1

Hier ist Pseudocode, der davon ausgeht, dass der Zielpunkt nicht im Baum gespeichert ist. (Wenn ja, fügen Sie einfach Logik, es zu ignorieren):

nearest_point = NULL 
nearest_distance = INFINITE; 
target_point = <set to the target point> 

void nn_search(KD_NODE node) { 
    FLOAT d = node->point.distance_to(target_point); 
    if (d < nearest_distance) { 
    nearest_distance = d; 
    nearest_point = node->point; 
    } 
    BOX left_bb = node->left.bounding_box(); 
    BOX right_bb = node->right.bounding_box(); 
    if (left_bb.contains(target)) { 
    search_children(node->left, node->right, right_bb); 
    else { // right_bb must contain target 
    search_children(node->right, node->left, left_bb); 
    } 
} 

void search_children(KD_NODE a, KD_NODE b, BOX b_bb) { 
    nn_search(a); 
    // This condition makes the search expected O(log n) time rather than O(n). 
    // Skip searching the other child unless it might improve the answer. 
    if (b_bb.contains_point_closer_than(target, nearest_distance)) { 
    nn_search(b); 
    } 
} 

Danach ausgeführt wird, nearest_point enthält den nächsten Punkt zum Ziel. Beachten Sie, dass es einfach ist, die Begrenzungsrahmen als Parameter von nn_search zu berechnen, anstatt sie innerhalb der Knoten zu speichern, die dieser Code zu tun scheint. Im Produktionscode möchten Sie das tun, um den Platz von 4 Floats pro Knoten zu speichern. Ich habe die Parameter zur Vereinfachung weggelassen.

Das Prädikat contains_point_closer_than gibt "true" zurück, wenn irgendein Punkt in der Bounding Box existiert, der näher am Ziel ist als der angegebene Abstand. Zum Glück ist es genug, nur einen Punkt in der Box zu berücksichtigen. Wenn z. B. der aktuelle Knoten das Suchfeld bei X in linke und rechte Hälften teilt, müssen Sie nur den Punkt (X, Y_target) und seine Entfernung zum Ziel berücksichtigen. Diese Entfernung ist nur abs(X - X_target)! Lassen Sie sich davon ohne weitere Diskussion überzeugen

Answer 2

Ich kenne zwei Java kd-tree-Implementierungen, die die kNN-Suche unterstützen, here und here. Ihre Leistung scheint in etwa gleich zu sein.