使用KDtree的最近鄰居

Question

我知道如何構建kd樹。但是我面臨的問題是如何使用KD Tree找到最近的鄰居。我已經在谷歌上搜索，但無法找到尋找最近鄰居的代碼，雖然算術給出。但是由於語言的原因，我很難將算法轉換爲代碼。

你能否給我提供一些可以理解的用於java的NNSearch代碼？

Answer 1

這是假定目標點未存儲在樹中的僞代碼。 （如果是，只需添加邏輯忽略它）：

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

這種運行後，nearest_point包含最近點的目標。請注意，將邊界框計算爲nn_search的參數非常簡單，而不是將它們存儲在此代碼似乎要做的節點內。在生產代碼中，您希望這樣做以節省每個節點4個浮點的空間。爲簡單起見，我省略了參數。

謂詞contains_point_closer_than返回true，如果存在任何點的邊界框比給定的距離更接近目標。令人高興的是，僅僅考慮一個方框就足夠了。例如，如果當前節點將搜索空間分成左右兩半X，那麼您只需考慮點(X, Y_target)及其與目標的距離。那距離只是abs(X - X_target)！我會讓你不需要進一步討論就能說服你自己

Answer 2

我知道兩個支持kNN搜索的Java kd-tree實現，here和here。他們的表現似乎大致相同。