查找具有特定距離的第一個元素

Question

我正在嘗試編寫一個方法，該方法將返回距離3D空間中另一個點最近的點的索引。這些點存儲在KD樹中，我將它們與作爲我的方法參數的點p進行比較。下面是方法：

public int NearestPointWithDistance(KDnnTreeNode node, Point p, Double distance){ 
    int index = -1; 
    if(node == null){ 
    return -1; 
    }else{ 
     double[] point_coordinates = data[node.eltIndex]; 
     Point q = new Point(point_coordinates[0],point_coordinates[1], point_coordinates[2]); 
     if(KDnnTree.distance(p, q) == distance){ 
      return index; 
     } 

     if(node.left != null){ 
      final int left_child = NearestPointWithDistance(node.left, p, distance); 
     } 
     if(node.right != null){ 
      final int right_child = NearestPointWithDistance(node.right, p, distance); 
     } 
    } 
    return index; 

}

的問題是，可能有多個百分點的距離相同。我得到的結果是點的索引列表（見下文），但我只想要列表的第一個元素（在下面的例子中，這將是數字54510）。

54510 
54511 
54512 
54514 
54518 
54526 
54543 
54577 
65355 
76175 
54482 
54416 
54278 
21929 
54001 
74323 

我知道這不是在KD樹中搜索兩個關閉點的方法，但我想先嚐試這種方法。

Answer 1

請勿使用java.lang.Double作爲參數。使用double。

原因是，如果您的KDNTree.distance()也將返回Double您將最終在比較對象的引用，而不是它們的值。

你有非常不方便的API。無論如何，讓一個輔助函數：

public Point getNodePoint(Node node) 
{ 
    double[] point_coordinates = data[node.eltIndex]; 
    return new Point(point_coordinates[0],point_coordinates[1], point_coordinates[2]); 
} 

使用最佳距離availabale選擇：

double result = KDnnTree.distance(p, q); 
if (result == distance) 
{ 
    return node.eltIndex; 
} 
index = node.eltIndex; // assume given node is best 
if (node.left != null) 
{ 
    final int left_child = NearestPointWithDistance(node.left, p, distance); 
    double left_distance = KDnnTree.distance(p, getNodePoint(left_child); 

    if (Math.abs(distance - result) > Math.abs(distance - left_distance)) 
    { 
     // result given is closer to wanted point 
     result = left_distance; 
     index = left_child; 
    } 
} 
if (node.right != null) 
{ 
    final int right_child = NearestPointWithDistance(node.right, p, distance); 
    double right_distance = KDnnTree.distance(p, getNodePoint(right_child); 

    if (Math.abs(distance - result) > Math.abs(distance - right_distance)) 
    { 
     // result given is closer to wanted point 
     result = right_distance; 
     index = right_child; 
    } 
} 
return index;