2D KD 트리와 가장 가까운 이웃 검색

Question

나는 현재 여기에 설명 된 알고리즘 다음하는 KD 트리와 가장 가까운 이웃 검색을 구현 ​​해요 : 나는 KD 트리를 구현하기 위해 서로 다른 몇 가지 방법을 통해 온 http://ldots.org/kdtree/

, 하나 포인트는 내부 노드에 저장되며, 리프 노드에만 저장됩니다. 매우 간단한 유스 케이스가 있으므로 (트리를 한 번만 구성하면 수정해야 할 필요가 없습니다), 구현하기가 단순한 것처럼 보이는 잎 전용 접근 방식으로갔습니다. 성공적으로 모든 것을 구현했으며 트리는 항상 성공적으로 생성되며 대부분의 경우 가장 가까운 이웃 검색은 올바른 값을 반환합니다. 그러나 일부 데이터 집합과 검색 지점에서 알고리즘이 잘못된 값을 반환한다는 문제가 있습니다. 점을 고려 : 이런 식으로 뭔가를 찾고 트리를 구성

[[6, 1], [5, 5], [9, 6], [3, 81], [4, 9], [4, 0], [7, 9], [2, 9], [6, 74]] 

이 (내 나쁜 다이어그램을 변명) : 사각형 잎 노드가 포인트를 포함하는 것들, 그리고 원형 노드입니다 가

포함 해당 깊이에서 목록을 분할하는 중간 값. 이 데이터 세트에서 가장 가까운 이웃 검색을 호출하고 가장 가까운 이웃을 [6, 74]으로 찾으면 알고리즘은 [7, 9]을 반환합니다. 이 알고리즘이 올바르게 수행되었지만 실제로는 [6, 74]과 가장 가까운 지점이 아닙니다. 가장 가까운 점은 실제로 [3, 81]이고 거리가 7.6 인 경우 [7, 9]은 65의 거리에 있습니다.

여기에 점을 찍으면 시각화를 위해 가장 가까운 이웃을 찾으려고 시도하는 점이 표시됩니다 를 위해 : 도움이된다면 다음과 같이

내 검색 방법은 다음과 같습니다 그래서 내 질문은

private LeafNode search(int depth, Point point, KDNode node) { 
     if(node instanceof LeafNode) 
      return (LeafNode)node; 
     else { 
      MedianNode medianNode = (MedianNode) node; 

      double meanValue = medianNode.getValue(); 
      double comparisonValue = 0; 
      if(valueEven(depth)) { 
       comparisonValue = point.getX(); 
      } 
      else { 
       comparisonValue = point.getY(); 
      } 

      KDNode nextNode; 
      if(comparisonValue < meanValue) { 
       if (node.getLeft() != null) 
        nextNode = node.getLeft(); 
       else 
        nextNode = node.getRight(); 
      } 
      else { 
       if (node.getRight() != null) 
        nextNode = node.getRight(); 
       else 
        nextNode = node.getLeft(); 
      } 

      return search(depth + 1, point, nextNode); 
     } 
    } 

같습니다

1. KD 트리에서 가장 가까운 이웃 검색에서 기대할 수있는 것입니까, 아니면 내가 검색하고있는 포인트에 가장 가까운 포인트를 가져야합니까 (이 것이 트리를 사용하는 유일한 이유입니다)?

2. 이 문제는 KD Tree의이 형식에서만 발생합니다. 이것을 해결하기 위해 내부 노드에 점을 저장해야합니까?

Answer 1

올바른 KD 트리 구현은 항상 가장 가까운 점을 찾습니다 (점이 잎에만 저장되어 있는지 여부는 중요하지 않음). 그러나 검색 방법이 올바르지 않습니다.

bestDistance = INF 

def getClosest(node, point) 
    if node is null 
     return 
    // I will assume that this node splits points 
    // by their x coordinate for the sake of brevity. 
    if node is a leaf 
     // updateAnswer updates bestDistance value 
     // and keeps track of the closest point to the given one. 
     updateAnswer(node.point, point) 
    else 
     middleX = node.median 
     if point.x < middleX 
      getClosest(node.left, point) 
      if node.right.minX - point.x < bestDistance 
       getClosest(node.right, point) 
     else 
      getClosest(node.right, point) 
      if point.x - node.left.maxX < bestDistance 
       getClosest(node.left, point) 

Answer 2

ldots.org에 주어진 설명은 (KD 나무를 검색에 많은 다른 최고 Google 결과와 함께) 그냥 일반 잘못 : 여기처럼 보이게하는 방법입니다.

올바르게 구현하려면 https://stackoverflow.com/a/37107030/591720을 참조하십시오.