Home  >  Article  >  Backend Development  >  C# example analysis of searching for the nearest point through KD tree

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

黄舟
黄舟Original
2017-10-05 15:32:021996browse

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!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn