Home > Article > Backend Development > 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!