Abstract:In view of the traditional sampling method of the on-machine measurement that the sampling points are too centralized and the sampling areas are omitted to influence surface profile, MacQueen K-means (MK) algorithm and simulated annealing (SA) algorithm were combined and the adaptive sampling method of complex surfaces for the on-machine measurement system based on MKSA algorithm was proposed. Through the absolute value of Gaussian curvature of the complex surface’s discrete point cloud data as the density function and the variance function as the convergence criterion, MK algorithm was used to generate centroidal voronoi tessellation(CVT). Besides, annealing criterion of the global algorithm of SA was used as cooling coefficient to improve the ability of the global optimization of the MK algorithm and the global optimal CVT was generated. The centroid of CVT was regarded as the measuring point and the distribution of measuring point on complex surfaces was accomplished which can fully reflects the curvature of the surface information. The simulation and experimental results showed that the distribution of sampling points of MKSA algorithm was more reasonable whose maximum deviation and average deviation of the fitting surface and the CAD model were less than the traditional methods. Therefore, the fitting surface of MKSA algorithm was more approximate to the theoretical surface of the CAD model.