本文摘自PHP中文网,作者黄舟,侵删。
这篇文章主要为大家详细介绍了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 |
|
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 |
|
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 |
|
以上就是C#通过KD树进行距离最近点的查找的实例分析的详细内容!
相关阅读 >>
使用 vscode 编写 .net core 项目的实例教程
更多相关阅读请进入《csharp》频道 >>
C#高级编程(第11版) C# 7 & .NET Core 2.0(.NET开发经典名著)
作者:[美]克里斯琴·内格尔(Christian Nagel)著。出版时间:2019年3月。