摘要: 提出一种新的k邻近的获取方法,将测量数据点的x, y和z坐标按照空间坐标系x轴、y轴和z轴的方向进行三维排序。找到所求点在三维排序中的位置,得到一个动态的网格,并在该网格内搜索k邻近。与传统的包容盒搜索k邻近方法相比,该文算法避免了包容盒法在划分空间网格时,由于网格内点数的不确定性所带来的缺陷。该算法的创新性是根据点的密度,随意扩大或缩小该网格,从而可以快速求得k邻近点。
关键词:
最近邻近,
动态网格,
散乱点
Abstract: 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.
Key words:
nearest neighbors,
dynamic grid,
scattered points
中图分类号:
马骊溟;徐 毅;李泽湘. 基于动态网格划分的散乱点k邻近快速搜索算法[J]. 计算机工程, 2008, 34(8): 10-11.
MA Li-ming; XU Yi; LI Ze-xiang. Fast k-nearest Neighbors Searching Algorithm for Scattered Points Based on Dynamic Grid Decomposition[J]. Computer Engineering, 2008, 34(8): 10-11.