两种空间分块策略K近邻搜索算法的比较研究

空间分块策略是K近邻搜索算法研究中的有效方法，然而现有算法进行空间划分时给出的子立方体大小主要取决于K值的大小，K值变化时需重新进行空间划分，影响了时间效率和稳定性。利用空间分块策略的优点，提出一种以建立离散数据空间索引为空间划分目标的K近邻搜索新算法。该算法预先对空间包围盒进行微分块，形成的子立方体结构仅与离散数据和预设参数相关，同一点云数据只需进行一次空间分配。搜索过程中，以计算点为球心建立空间动态球，判定符合条件的子立方体，进行K近邻搜索。测试结果表明，新算法较现有算法点云分配和遍历时间效率、随机点搜索时间稳定性及对不同K值的适应性等方面更具有优势。