一种基于计算几何方法的最小包容圆求解算法  

Algorithm for Minimum Circumscribed Circle Detection Based on Computational Geometry Technique

作　　者：张勇[1] 陈强[1] 

机构地区：[1]清华大学机械工程系先进成形制造重点实验室,北京100084

出　　处：《工程图学学报》2007年第3期97-101,共5页Journal of Engineering Graphics

基　　金：国家自然科学基金资助项目(50275083);高校博士点基金资助项目(20020003053)

摘　　要：为实现点集最小包容圆(最小外接圆)的求解,将计算几何中的α-壳的概念应用到最小包容圆的计算过程,提出了一种精确有效的最小包容圆求解算法。根据α-壳定义及最小包容圆性质,证明当1/α等于最小包容圆半径时点集的α-壳顶点共圆,1/α小于最小包容圆半径时α-壳不存在,1/α大于最小包容圆半径时随着1/α减小α-壳顶点数逐渐减小的规律。将α-壳顶点数目作为搜索最小包容圆半径的依据,实现了最小包容圆半径的搜索和最小包容圆的求解。α-hulls are applied to calculate the minimum circumscribed circle （MCC） of point set and an accurate and effective method for MCC detection is established through finding the least squares circle of the point set and iteratively approaching the MCC with recursive subdivision. Several theorems concerning the properties of α-hulls are presented. If 1/α is equal to the radius of points＇ MCC, all vertices of the α-hull will be on the same circle. When 1/α is larger than the MCC＇s radius, the number of vertices of α-hulls will decrease with decreasing of 1/α, and the number of vertices＇ number will reach zero when 1/α is smaller than MCC＇s radius. From the above rules, an algorithm for detecting MCC is developed, and experimental results show this algorithm is reliable.

关 键 词：计算机应用 优化算法 计算几何 最小包容圆 α-壳 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]