java - 使用 KDtree 的最近邻

Question

我知道如何构建 kd 树。但是我面临的问题是如何使用 KD 树查找最近邻居。我在 google 上搜索过，但无法找到查找最近邻居的代码，尽管给出了算法。但由于语言的原因，我在将该算法转换为代码时遇到了困难。

您能为我提供可以理解的 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 个 float 的空间。为了简单起见，我省略了参数。

如果边界框中存在距离目标比给定距离更近的点，则谓词 contains_point_closer_than 返回 true。令人高兴的是，只考虑框中的一点就足够了。例如，如果当前节点在X处将搜索空间分成左右两半，那么您只需要考虑点(X, Y_target)及其到目标的距离。这个距离就是 abs(X - X_target)!我会让你相信这一点，无需进一步讨论