java - KdTree 最近邻搜索算法无法正常工作

Question

我正在用 java 实现 KdTree。我已经完成了程序的大部分其余部分，但我似乎无法让我的最近邻搜索算法正常​​工作。无论如何，它总是返回根节点的值。这是我的代码:

public Point2D nearest(Point2D p) {

    if (root == null) //if there are no nodes in the tree
        return null;
    else
        return nearest(p, root, root.point);            

}

• rect 是一个 RectHV 对象，对应于节点点的边界。

  public Point2D nearest(Point2D p, Node n, Point2D nearest) {
  
  if (n == null) {
      return nearest;
  }
  
  if (p.distanceSquaredTo(nearest) > p.distanceSquaredTo(n.point)) {
      nearest = n.point;
  }
  if (n.xAxis) { //the xaxis value is a boolean, if it is true,
                 //the node splits on the x axis, false it splits on y
  
      if (p.x() < n.point.x() && p.distanceSquaredTo(nearest) < n.rect.distanceTo(p)) {
          nearest = nearest(p, n.leftnode, nearest);
          System.out.println("look left 1");
      } else {
          nearest = nearest(p, n.rightnode, nearest);
          System.out.println("look right 1");
      }
  } else {
      if (p.y() < n.point.y() && p.distanceSquaredTo(nearest) < n.rect.distanceTo(p)) {
          nearest = nearest(p, n.leftnode, nearest);
          System.out.println("look left 2");
      } else {
          nearest = nearest(p, n.rightnode, nearest);
          System.out.println("look right 2");
      }
  }
  return nearest;
  

我认为我的算法对于这项任务来说太简单了。我的理由是，如果查询点和候选点的矩形之间的 distanceSquared 大于已经建立的最近点，则不要搜索该树。

Answer 1

问题是 (1) 从查询点到定义子树的点的距离不是到该子树中所有点的距离的下限，以及 (2) 最近的点可能位于“其他” " child 。

要获得下界，您可以在下降时跟踪子树中点的边界框，并使用查询点到框的距离。更简单地说，您可以使用点到最近一次分割定义的半平面的距离。您需要探索这两个 child (除非被修剪)。