关键词: 逆向工程, 海量数据, K 邻近, 邻近点搜索, 算法

Abstract:

In the reverse engineering , the first thing for processing the measured data is to build up the topology of the point cloud , which is generally implemented by calculating the K-nearest neighbors. In this paper , the existing algorithms of K-nearest neighbors are analyzed , and a new algorithm for K-nearest neighbors of massive data based on spacial partition is proposed. In the proposed algorithm , the effects of K value and point-cloud density and number on the side length of small sub-cubes are considered , and the most suitable searching range is obtained by finding the suitable side length of small sub-cubes and by excluding small sub-cubes without point cloud inside. Thereby , the searching speed is raised and the correctness of searched results is ensured. The proposed algorithm is finally verified by the second exploiting programming of reverse engineering software.

Key words: reverse engineering, massive data, K-nearest neighbor, neighbor point searching, algorithm