核心思想
利用高维的二分查找,建立KD树,减小查找最近点的时间复杂度
算法内容
建立KD树
while(所有点挂载完){
1、每一层按逐个维度排序本层的点(什么叫逐个维度,就比如二维的点就x、y轮流替换)
2、取中位数作为本层根节点,左子树的放小的,右子树放大的
}
搜索
已知点 = input()
路径列表 = 空
while(true){
1、按照上面逐层按其维度向下搜寻路径,加入路径列表
if (叶子节点加入路径列表){break}
}
最小距离 = 空
while(路径列表不为空){
1、计算已知点到路径列表最后一个点的距离,给最小距离一直存储最小距离
2、该点从路径列表移除
3、比较最小距离和到路径列表最后一个点的维度距离
4、if(相交){将另一侧的点加入路径列表}
}
参考
【KD树 - CSDN App】http://t.csdnimg.cn/tzUtp