Algorithms And Systems For Roundness Evalution Based On Voronoi Diagram

In industrial production and manufacturing, roundness error evaluation is one of the key measures to detect the product quality and guarantee the machining precision. At present, the existing algorithms for roundness error evaluation mainly include the linear algebra approach, the nonlinear optimization method, the random optimization algorithm, the genetic algorithm, the stochastic optimization approach, the exhaustive approach, and the computational geometry based approachs. However, none of the above mentioned methods can rapidly and simply find the roundness error according to the definition given by the ISO.In this paper, the characteristics of the Voronoi diagram, as well as the roundness error evaluation utilizing the Voronoi diagram, are studied. According to the analysis, for a given measured point set in a plane, it can be found that (1) the radius of the circumscribed circle decreases monotonously when its center moves from any point on the farthest Voronoi diagram to the minimum circumscribed circle center along the farthest Voronoi edges, (2) the radius of the inscribed circle increases monotonously when its center moves from any point on the nearest Voronoi diagram to the centre of the local maximum inscribed circle along the nearest Voronoi edges, and (3) the radius difference of the zone ring decreases monotonously when its center moves from the minimum circumscribed circle center to the centre of the local minimum zone circle along the nearest or the farthest Voronoi edges. On this basis, an algorithm accessing the minimum circumscribed circle for roundness based on the farthest Voronoi diagram, an algorithm accessing the maximum inscribed circle for roundness based on the nearest Voronoi diagram and an algorithm accessing the minimum zone circle for roundness based on the nearest and the farthest Voronoi diagram are proposed. In addition, the detailed flow charts of the algorithms and the corresponding software with Visual C++ 6.0 in Windows XP environment are presented. Furthermore, the examples to evaluate the roundness error with the developed software based on the algorithms proposed in this paper as well as the comparision with the exhaustive approach are shown.At present, the grating displacement sensors, widely used in the field of measurement, display the result through separating digital readout. Based on the traditional readout of the grating displacement sensors, not only the system flexibility is poor, but also the interface with other equipments is inconvenient. Keep this in mind, a virtual grating digital readout based on USB 2.0 is presented.The research results show that not only the algorithms proposed in this thesis can access the roundness error according with the definition, but also the time complexity is linear without error accumulation. The larger the scale of the sampling points of the measured point set is, the more apparent the predominance of the computing speed of the algorithm proposed in this thesis is. The virtual grating digital readout system based on USB 2.0 can meet the need of data acquisition.