C# example analysis of searching for the nearest point through KD tree

This article mainly introduces C# to find the nearest point through KD tree in detail. It has certain reference value. Interested friends can refer to it.

This article first introduces Kd-Tree. The construction method, then introduces the search process and code implementation of Kd-Tree, and finally gives the two-dimensional KD tree code that I implemented using C# language. This is also the first tree-shaped data structure I have implemented myself. There will inevitably be deviations in understanding, so please correct me.

1. Introduction to KD tree

Kd-Tree (KD tree), that is, K-dimensional tree, is a high-dimensional index tree data structure , often used for nearest neighbor search and approximate nearest neighbor search in large-scale high-dimensional data spaces. The KD tree I implemented is a two-dimensional Kd-tree. The purpose is to find the closest point in the point set. The reference material is Kd-Tree’s Baidu Encyclopedia. And the code is organized according to the logic of Baidu Encyclopedia.

2. Mathematical explanation of KD tree

3. Construction method of KD tree

Here, a two-dimensional point set is used to construct a Kd-tree. The three-dimensional one is similar.
Data type of each node in the tree:

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 tree construction logical process

• Convert all points Put it into set a

• Find the variance xv for the X coordinates of all points in the set, and find the variance yv for the Y coordinate

• If xv > ; yv, then sort the set a according to the X coordinate. If yv > xv, then the set a is sorted according to the y coordinate.

• Get the median m of the sorted set a. Then use m as the breakpoint and put the point indexed by [0,m-2] into the a1 set. Put the point indexed by [m,a.count] into the set of a2 (the index of point m is m-1).

• Build a node, the value of the node is a[m-1], if the number of nodes in the operation set is greater than 1, then the left node pair [0, m-2] repeats 2 -5 steps, the right node repeats steps 2-5 for [m,a.count]; otherwise, the node is a leaf node.
  

3.2 Code implementation

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 tree search method

The overall search process of Kd-Tree first finds a nearest leaf node based on ordinary search. But this leaf node is not necessarily the nearest point. Then perform a backtracking operation to find the closest point.

4.1 KD tree search logic process

• For the tree t constructed based on the point set and the search point p. Use the root node as the node t to perform the following operations

• If t is a leaf node. Then get the value of the split point where the value of the nearest point n is t, jump to step 5; if t is not a leaf node, proceed to step 3

• to determine the splitting method of t, If the split is along the x-axis, compare the x value of p with the x value of the split point of the node. Otherwise, compare the Y coordinate.

• If the comparison value of p is less than If the comparison value of t is specified, t is designated as the left child node of t. Otherwise, specify t as the right child node of t, perform step 2

• to define the retrieval point m, and set m to n

• to calculate The distance d1 between m and p, the distance d2 between n and m.

• If d1 >= d2 and there is a parent node, then use the parent node of m as the value of m and execute 5 steps. If there is no parent node, get the real closest point TN; If d1 < d2, it means that point n is not the closest point, perform step 8

• If n has sibling nodes, then n = sibling node of n; if n has no sibling node, then n = the parent node of n. Delete the original n nodes. Set the value of m to the new n node; perform step 6.
  

4.2 Code Implementation

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);
  }
}

The above is the detailed content of C# example analysis of searching for the nearest point through KD tree. For more information, please follow other related articles on the PHP Chinese website!