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

本文介绍了采用计算几何知识求解最大内接圆的新方法，该方法摆脱了传统的用坐标及函数处理几何问题的常规，从图形的崭新思路分析了最大内接圆的准确中心，并且提出了一种删除无关数据点的原则、可将采样点数减至十分之一以下。相应算法的运算时间比以往的算法快１５倍以上。

Study on Maximum Inscribed Circle by Computational Geometry Approach

This paper describes an efficient and accurate algorithm to determine the maximum inscribed circle (MIC) for a set of measured data points on a circle in a computer aided automatic inspection environment.The principle of the algorithm is based on the nearest 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 maximum inscribed circle,has been proposed.The number of data points can be reduced below one tenth of the original by applying a comparison operation with a pre selected radius to the data set prior to the construction of the nearest 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 15 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.