C#通过KD树进行距离最近点的查找
本文首先介绍Kd-Tree的构造方法,然后介绍Kd-Tree的搜索流程及代码实现,最后给出本人利用C#语言实现的二维KD树代码。这也是我自己动手实现的第一个树形的数据结构。理解上难免会有偏差,敬请各位多多斧正。 1. KD树介绍 Kd-Tree(KD树),即K-dimensional tree,是一种高维索引树形数据结构,常用于在大规模的高维数据空间进行最邻近查找和近似最邻近查找。我实现的KD树是二维的Kd - tree。目的是在点集中寻找最近点。参考资料是Kd-Tree的百度百科。并且根据百度百科的逻辑组织了代码。 2. KD树的数学解释 3. KD树的构造方法 这里是用的二维点集进行构造Kd-tree。三维的与此类似。 public class KDTreeNode { /// <summary> /// 分裂点 /// </summary> public Point DivisionPoint { get; set; } /// <summary> /// 分裂类型 /// </summary> public EnumDivisionType DivisionType { get; set; } /// <summary> /// 左子节点 /// </summary> public KDTreeNode LeftChild { get; set; } /// <summary> /// 右子节点 /// </summary> public KDTreeNode RightChild { get; set; } } 3.1 KD树构造逻辑流程
3.2 代码实现 private KDTreeNode CreateTreeNode(List<Point> pointList) { if (pointList.Count > 0) { // 计算方差 double xObtainVariance = ObtainVariance(CreateXList(pointList)); double yObtainVariance = ObtainVariance(CreateYList(pointList)); // 根据方差确定分裂维度 EnumDivisionType divisionType = SortListByXOrYVariances(xObtainVariance,yObtainVariance,ref pointList); // 获得中位数 Point medianPoint = ObtainMedian(pointList); int medianIndex = pointList.Count / 2; // 构建节点 KDTreeNode treeNode = new KDTreeNode() { DivisionPoint = medianPoint,DivisionType = divisionType,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树搜索逻辑流程
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.DivisionType == EnumDivisionType.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.DivisionPoint); double nearestPointDistance = ObtainDistanFromTwoPoint(searchPoint,nearestPoint); if (backtrackDistance < nearestPointDistance) { // 深拷贝节点的目的是为了避免损坏树 KDTreeNode searchNode = new KDTreeNode() { DivisionPoint = trackNode.DivisionPoint,DivisionType = trackNode.DivisionType,LeftChild = trackNode.LeftChild,RightChild = trackNode.RightChild }; nearestPoint = DFSBackTrackingSearch(searchNode,searchPoint); } // 递归到根节点 return BacktrcakSearch(searchPoint,nearestPoint); } } 5. 源码交流 https://github.com/CreamMilk/C-Kd-Tree 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持编程小技巧。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |