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) 가장 가까운 지점이 " 다른 "아이.

하한값을 얻으려면 하강시 하위 트리의 점 경계 상자를 추적하고 상자에 쿼리 지점 거리를 사용합니다. 더 단순하게, 가장 최근의 분할로 정의 된 반 평면으로부터 점까지의 거리를 사용할 수 있습니다. 두 아이를 모두 탐색해야합니다 (정리하지 않은 경우).