gpt4 book ai didi

C#通过KD树进行距离最近点的查找

转载 作者:qq735679552 更新时间:2022-09-28 22:32:09 45 4
gpt4 key购买 nike

CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章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。三维的与此类似。 树中每个节点的数据类型:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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树构造逻辑流程 。

  • 将所有的点放入集合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 代码实现 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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树搜索逻辑流程 。

  • 对于根据点集构建的树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 代码实现 。

  。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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 。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我.

原文链接:http://www.cnblogs.com/MaFeng0213/archive/2017/09/26/7598886.html 。

最后此篇关于C#通过KD树进行距离最近点的查找的文章就讲到这里了,如果你想了解更多关于C#通过KD树进行距离最近点的查找的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

45 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com