KdTree最近鄰居搜索算法無法正常工作

我在java中實現KdTree。我完成了大部分程序的其餘部分，但似乎無法使我的最近鄰居搜索算法正常工作。無論如何，它始終返回根節點的值。這裏是我的代碼：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;

}

我在想，我的算法是任務太簡單了。我的理由是，如果查詢點與候選點矩形之間的距離平方大於已建立的最近點，則不要搜索該樹。

來源

2014-03-07 Kestrel

問題是（1）從查詢點到定義子樹的點的距離不是到該子樹中所有點的距離的下限，以及（2）最近點可能位於「其他「的孩子。

要獲得下限，可以跟蹤下降子樹中點的邊界框，並使用查詢點與框的距離。更簡單地說，您可以使用從最近分割定義的點到半平面的距離。你需要探索兩個孩子（除非修剪）。

來源

2014-03-07 00:42:15

KdTree最近鄰居搜索算法無法正常工作

回答

相關問題