kd树相关资料调研 -ag凯发k8国际

https://blog.csdn.net/pipisorry/article/details/52186307（包含kd树的改良版本）
https://blog.csdn.net/app_12062011/article/details/51986805（值得细看！！！）
https://blog.csdn.net/qing101hua/article/details/53228668（已经阅读）
https://blog.csdn.net/u012423865/article/details/77488920(没啥新东西，已经阅读)
https://www.cnblogs.com/zxh1210603696/p/3491254.html（c 版本的kd树，可看可不看）
https://blog.csdn.net/qq_36346262/article/details/77920325（c 版本的kd树，可看可不看）
https://blog.csdn.net/hu694028833/article/details/78166338（c 实现kd树）
https://blog.csdn.net/wisedoge/article/details/78860513（c 实现kd树）

kd树相关的算法主要是两个：一个是构建kd树算法，一个是基于kd树的搜索算法

下面是kd树和k维空间的对应方法
偶数层是x，
奇数层看y，
二叉树上左小右大，
x轴左小右大，
所以偶数层，向左侧划分的就对应x轴左边节点； 
同样地，y轴下小上大，所以奇数层，左边节点对应k维空间的向下划分。
不停地比较x，y轴的值的过程就是kd树搜索的过程

--------------------------------------------------------------------
关于选定那个维作为切割维，目前看到有三种方式，
一种是l=j(mod k) 1,以x^l作为切分轴
第二种是哪个维度的方差大，就选择哪个维度作为切分轴
第三种是哪个维度的数据范围大，就作为切分轴
--------------------------------------------------------------------

每个分支都是一个子空间

搜索的时候需要回溯，这个是因为，按照“先后比大小”的策略的并不能保证树上的某个节点与被查找值的单维的节点之间的距离最短，
也不能保证是最近点，也就是说，这种搜索策略的毛病在于，他把“寻找最近距离点”近似处理为“寻找各个坐标分别进行二分查找”
所以最终需要回溯作为弥补。

总结这里的圆是在查询到最后一个节点的时候，半径=（被查询点-树的最下面的叶子节点的差值）2，
然后再在回溯的时候，看看被回溯的样本点会不会落在这个圆里面，如果落在里面，那么修改圆半径，否则就认为当前最短

☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
什么是sift算法以及为何使用到了kd树

下面这个暂时没有搞懂，毕竟也不关心r树啊
根据划分的空间是否有混叠可以分为clipping和overlapping两种。
前者划分空间没有重叠，其代表就是k-d树；
后者划分空间相互有交叠，其代表为r树。（这里只介绍k-d树）

 

总结

以上是ag凯发k8国际为你收集整理的kd树相关资料调研的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得ag凯发k8国际网站内容还不错，欢迎将ag凯发k8国际推荐给好友。