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

提出一种新的k邻近的获取方法，将测量数据点的x, y和z坐标按照空间坐标系x轴、y轴和z轴的方向进行三维排序。找到所求点在三维排序中的位置，得到一个动态的网格，并在该网格内搜索k邻近。与传统的包容盒搜索k邻近方法相比，该文算法避免了包容盒法在划分空间网格时，由于网格内点数的不确定性所带来的缺陷。该算法的创新性是根据点的密度，随意扩大或缩小该网格，从而可以快速求得k邻近点。

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

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.