KD 트리를 통해 가장 가까운 지점을 검색하는 C# 예제 분석

이 글에서는 KD 트리를 통해 가장 가까운 지점을 찾는 C#을 주로 소개합니다. 관심 있는 친구들은 참고해 보세요.

이 글에서는 먼저 Kd-Tree의 구성 방법을 소개하고 검색 과정을 소개합니다. Kd-Tree의 코드 구현, 그리고 마지막으로 C# 언어를 사용하여 제가 구현한 2차원 KD 트리 코드입니다. 이것은 제가 직접 구현한 최초의 트리 형태의 데이터 구조이기도 합니다. 필연적으로 이해의 차이가 있을 수 있으니 정정해 주시기 바랍니다.

1. KD 트리 소개

K-차원 트리라고도 알려진 Kd-Tree(KD 트리)는 대규모 최근접 이웃 분석을 수행하는 데 자주 사용되는 고차원 인덱스 트리 데이터 구조입니다. -고차원 데이터 공간을 검색하고 가장 가까운 이웃 검색을 근사화합니다. 제가 구현한 KD 트리는 2차원 Kd-트리입니다. 목적은 포인트 세트에서 가장 가까운 포인트를 찾는 것입니다. 참고 자료는 Kd-Tree의 Baidu Encyclopedia입니다. 그리고 코드는 Baidu Encyclopedia의 논리에 따라 구성됩니다.

2. KD 트리의 수학적 설명

3. KD 트리 구성 방법

다음은 Kd-트리 구성에 사용되는 2차원 점 집합입니다. 입체감도 비슷해요.
트리에 있는 각 노드의 데이터 유형:

public class KDTreeNode
  {
    /// <summary>
    /// 分裂点
    /// </summary>
    public Point pisionPoint { get; set; }

    /// <summary>
    /// 分裂类型
    /// </summary>
    public EnumpisionType pisionType { get; set; }

    /// <summary>
    /// 左子节点
    /// </summary>
    public KDTreeNode LeftChild { get; set; }

    /// <summary>
    /// 右子节点
    /// </summary>
    public KDTreeNode RightChild { get; set; }
  }

3.1 KD 트리 구성 논리 프로세스

• 모든 점을 집합 a에 넣습니다.

• 집합에 있는 모든 점의 X 좌표의 분산 xv를 계산합니다. , Y 좌표는 분산 yv

• 를 찾습니다. xv > yv이면 X 좌표에 따라 집합 a를 정렬합니다. yv > xv이면 집합 a는 y 좌표에 따라 정렬됩니다.

• 정렬된 집합 a의 중앙값 m을 구합니다. 그런 다음 m을 중단점으로 사용하고 [0,m-2]로 인덱스된 점을 a1 세트에 넣습니다. [m,a.count]로 인덱스된 포인트를 a2 집합에 넣습니다(포인트 m의 인덱스는 m-1입니다).

• 노드를 구성합니다. 노드의 값은 a[m-1]입니다. 작업 집합의 노드 수가 1보다 크면 왼쪽 노드는 [0, m에 대해 2~5단계를 반복합니다. -2], 오른쪽 노드는 [m,a.count]입니다. 그렇지 않으면 노드는 리프 노드입니다.
  

3.2 코드 구현

private KDTreeNode CreateTreeNode(List<Point> pointList)
{
  if (pointList.Count > 0)
  {
    // 计算方差
    double xObtainVariance = ObtainVariance(CreateXList(pointList));
    double yObtainVariance = ObtainVariance(CreateYList(pointList));

    // 根据方差确定分裂维度
    EnumpisionType pisionType = SortListByXOrYVariances(xObtainVariance,    yObtainVariance, ref pointList);

    // 获得中位数
    Point medianPoint = ObtainMedian(pointList);
    int medianIndex = pointList.Count / 2;

    // 构建节点
    KDTreeNode treeNode = new KDTreeNode()
    {
      pisionPoint = medianPoint,
      pisionType = pisionType,
      LeftChild = CreateTreeNode(pointList.Take(medianIndex).ToList()),
      RightChild = CreateTreeNode(pointList.Skip(medianIndex + 1).ToList())
    };
    return treeNode;
  }
  else
  {
    return null;
  }
}

4. KD 트리 검색 방법

Kd-Tree의 전체 검색 과정은 먼저 일반 검색을 기반으로 가장 가까운 리프 노드를 찾습니다. 하지만 이 리프 노드가 반드시 가장 가까운 지점은 아닙니다. 그런 다음 역추적 작업을 수행하여 가장 가까운 지점을 찾습니다.

4.1 KD 트리 검색 논리 프로세스

• 포인트 세트를 기반으로 구축된 트리 t와 검색 포인트 p에 대해 루트 노드를 노드 t로 사용하여 다음 작업을 수행합니다.

• t가 리프 노드. 그런 다음 가장 가까운 점 n의 값이 t인 분할 점의 값을 얻고, t가 리프 노드가 아니면 3단계로 진행합니다.

• 그런 다음 t의 분할 방법을 결정합니다. x축을 따라 분할됩니다. 그런 다음 p의 x 값을 노드 분할 지점의 x 값과 비교합니다. 그렇지 않으면 Y 좌표를 비교합니다.

• p의 비교 값이 t의 비교 값보다 작으면 t는 t의 왼쪽 자식 노드로 지정됩니다. 그렇지 않으면 t를 t의 오른쪽 하위 노드로 지정하고 2

• 단계를 수행하여 검색 지점 m을 정의하고 m을 n

• 으로 설정하고 m과 p 사이의 거리 d1과 n 사이의 거리 d2를 계산합니다. 그리고 m.

• d1 >= d2이고 상위 노드가 있는 경우 m의 상위 노드를 m의 값으로 사용하고 상위 노드가 없으면 d1인 경우 실제 가장 가까운 지점 TN을 가져옵니다. < d2는 n을 의미합니다. 해당 지점이 가장 가까운 지점이 아닙니다. n에 형제 노드가 있으면 n = n의 형제 노드이고, n에 형제 노드가 없으면 n = n의 상위 노드입니다. 원래 n개 노드를 삭제합니다. m 값을 새로운 n 노드로 설정합니다. 6단계를 수행합니다.

• 
  4.2 코드 구현

public Point FindNearest(Point searchPoint)
{
  // 按照查找方式寻找最近点
  Point nearestPoint = DFSSearch(this.rootNode, searchPoint);
  
  // 进行回溯
  return BacktrcakSearch(searchPoint, nearestPoint);
}


private Point DFSSearch(KDTreeNode node,Point searchPoint,bool pushStack = true)
{
  if(pushStack == true)
  {
    // 利用堆栈记录查询的路径，由于树节点中没有记载父节点的原因
    backtrackStack.Push(node);
  }
  if (node.pisionType == EnumpisionType.X)
  {
    return DFSXsearch(node,searchPoint);
  }
  else
  {
    return DFSYsearch(node, searchPoint);
  }
}

private Point BacktrcakSearch(Point searchPoint,Point nearestPoint)
{
  // 如果记录路径的堆栈为空则表示已经回溯到根节点，则查到的最近点就是真正的最近点
  if (backtrackStack.IsEmpty())
  {
    return nearestPoint;
  }
  else
  {
    KDTreeNode trackNode = backtrackStack.Pop();
    
    // 分别求回溯点与最近点距查找点的距离
    double backtrackDistance = ObtainDistanFromTwoPoint(searchPoint,     trackNode.pisionPoint);
    double nearestPointDistance = ObtainDistanFromTwoPoint(searchPoint, nearestPoint);
    
    if (backtrackDistance < nearestPointDistance)
    {
      // 深拷贝节点的目的是为了避免损坏树
      KDTreeNode searchNode = new KDTreeNode()
      {
        pisionPoint = trackNode.pisionPoint,
        pisionType = trackNode.pisionType,
        LeftChild = trackNode.LeftChild,
        RightChild = trackNode.RightChild
      };
      nearestPoint = DFSBackTrackingSearch(searchNode, searchPoint);
   }
   // 递归到根节点
   return BacktrcakSearch(searchPoint, nearestPoint);
  }
}

위 내용은 KD 트리를 통해 가장 가까운 지점을 검색하는 C# 예제 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!