计算几何在测试计量技术中的应用-求解最小外接圆

提供一种在机械科学中评定最小外接圆柱形状误差的高效、高精度算法。该算法的核心是提出了一种删除对求解最小外接圆不会起任何作用的无关样本点的有效方法。交替运用计算几何中的最远点Voronoi图的性质和统计分析方法撮小二乘法原理，可使最后参与求解最小外接圆的样本点数减至少量几个，相应算法的运算时间比以往的最优化快10倍以上。

EVALUATION OF MINIMUM CIRCUMSCRIBED CIRCLE FORM ERROR BY COMPUTATIONAL GEOMETRY APPROACH

An efficient and accurate algorithm to determine the minimum circumscribed circle (MCC) for a set of sampling data points has been proposed. The principle of the algorithm is based on the farthest Voronoi diagram of the computational geometry. To achieve higher computational efficiency, an effective approach eliminating the useless data points, which will never contribute anything to the establishment of the minimum circumscribed circle, has been proposed. The number of data points can be reduced down to only several points by applying a comparison operation with a radius of least square circle to the data set prior to the construction of the farthest Voronoi diagram. The algorithm has been tested and the results have been compared with those obtained by optimization methods. It has been found that the computation speed by the method presented in this article is at least 10 times faster than that by optimization algorithms. The developed program can be installed in the coordinate measuring machines (CMMs) and other computer aided measuring instruments for practical use.