基于动态网格划分的散乱点k邻近快速搜索算法  

Fast k-nearest Neighbors Searching Algorithm for Scattered Points Based on Dynamic Grid Decomposition

作　　者：马骊溟[1] 徐毅[1] 李泽湘[1] 

机构地区：[1]哈尔滨工业大学深圳研究生院,深圳518055

出　　处：《计算机工程》2008年第8期10-11,21,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(50505009)

摘　　要：提出一种新的k邻近的获取方法,将测量数据点的x,y和z坐标按照空间坐标系x轴、y轴和z轴的方向进行三维排序。找到所求点在三维排序中的位置,得到一个动态的网格,并在该网格内搜索k邻近。与传统的包容盒搜索k邻近方法相比,该文算法避免了包容盒法在划分空间网格时,由于网格内点数的不确定性所带来的缺陷。该算法的创新性是根据点的密度,随意扩大或缩小该网格,从而可以快速求得k邻近点。This paper proposes a novel k-nearest neighbor searching algorithm.The coordinates of origninal point data sets are sorted along x,y and z axis individually.The position of desired point is computed in the sequence of rearranged points,from which it can obtain a dynamic grid where the k-nearest points are searched.Compared to the conventional bounding box-based k-nearest neighbor searching method,the scheme can overcome the drawback of the uncertainty of the amount of points with the bounding box space subdivision.A outstanding innovation of the method is arbitrarily increasing or decreasing the grid,according to the density of the point set.So the k-nearest neighbor can be calculated efficiently.

关 键 词：最近邻近 动态网格 散乱点 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]