C#如何通过KD树进行距离最近点实现查找
这篇文章主要为大家展示了“C#如何通过KD树进行距离最近点实现查找”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“C#如何通过KD树进行距离最近点实现查找”这篇文章吧。
成都创新互联长期为上1000+客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为信宜企业提供专业的成都网站制作、网站建设，信宜网站改版等技术服务。拥有10多年丰富建站经验和众多成功案例,为您定制开发。
1. KD树介绍
Kd-Tree（KD树），即K-dimensional tree，是一种高维索引树形数据结构，常用于在大规模的高维数据空间进行最邻近查找和近似最邻近查找。我实现的KD树是二维的Kd - tree。目的是在点集中寻找最近点。参考资料是Kd-Tree的百度百科。并且根据百度百科的逻辑组织了代码。
2. KD树的数学解释
3. KD树的构造方法
这里是用的二维点集进行构造Kd-tree。三维的与此类似。
树中每个节点的数据类型：
public class KDTreeNode
{
///
/// 分裂点
///
public Point DivisionPoint { get; set; }
///
/// 分裂类型
///
public EnumDivisionType DivisionType { get; set; }
///
/// 左子节点
///
public KDTreeNode LeftChild { get; set; }
///
/// 右子节点
///
public KDTreeNode RightChild { get; set; }
}3.1 KD树构造逻辑流程
将所有的点放入集合a中
对集合所有点的X坐标求得方差xv,Y坐标求得方差yv
如果xv > yv,则对集合a根据X坐标进行排序。如果 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]重复2-5步，右节点为对[m,a.count]重复2-5步；反之，则该节点为叶子节点。
3.2 代码实现
private KDTreeNode CreateTreeNode(ListpointList) { 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树搜索逻辑流程
对于根据点集构建的树t,以及查找点p.将根节点作为节点t进行如下的操作
如果t为叶子节点。则得到最近点n的值为t的分裂点的值，跳到第5步;如果t不是叶子节点,进行第3步
则确定t的分裂方式，如果是按照x轴进行分裂，则用p的x值与节点的分裂点的x值进行比较，反之则进行Y坐标的比较
如果p的比较值小于t的比较值，则将t指定为t的左孩子节点。反之将t指定为t的右孩子节点，执行第2步
定义检索点m，将m设置为n
计算m与p的距离d1,n与m的距离d2。
如果d1 >= d2且有父节点,则将m的父节点作为m的值执行5步，若没有父节点，则得到真正的最近点TN; 如果d1 < d2就表示n点不是最近点，执行第8步
若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.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);
}
}以上是“C#如何通过KD树进行距离最近点实现查找”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联行业资讯频道！
分享题目：C#如何通过KD树进行距离最近点实现查找
分享路径：http://pwwzsj.com/article/ppjged.html
