三维散乱数据的k个最近邻域快速搜索算法  

Algorithm for Finding ~k^-Nearest Neighbors of Scattered Points in Three Dimensions

作　　者：熊邦书[1] 何明一[1] 俞华璟[1] 

机构地区：[1]西北工业大学电子与信息学院

出　　处：《计算机辅助设计与图形学学报》2004年第7期909-912,917,共5页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金 ( 60 172 0 40 );江西省测试技术与控制工程研究中心开放基金 ( 2 0 0 2 14 )资助

摘　　要：提出一种新的快速搜索算法 首先 ,采用空间分块策略 ,把数据空间分成许多大小相同的立方体子空间 ,立方体的大小决定了最近点的搜索速度 ;然后 ,综合考虑了数据集的范围、点的总数及最近点数目k,给出了一种新的估算立方体边长的方法 大量真实数据的实验结果表明A new and simple algorithm is presented At first, the min max box of the data set is divided into a set of uniform grids, and then the indexes of points are sorted into appropriate cell for finding nearest neighbors A method of estimating the size of grid is introduced by overall considering the range of data set, the total numbers of points and the numbers of nearest neighbors Simulated experiments showed that it is very easy to obtain the size of grids for a nearly optimal searching speed

关 键 词：最近邻域 范围搜索 曲面重建 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]