圆度误差评定中α-壳的删点效率分析

　　在删点技术的研究中,文献[1]提出了用最小二乘圆将误差圆分成正域和负域两部分,在此基础上再利用一些优化算法,进一步减少计算量.计算几何是20世纪70年代出现的一个研究领域,部分学者已将计算几何方法应用到圆度误差的评定中[2-3],其中,主要有两种方法:凸壳算法[4]和α-壳算法[5-6],文中采用α-壳进行删点.

　　1 α-壳删点技术及其优化

　　1.1 α-壳的定义

　　文献[4]给出了α-壳的定义:对于平面点集P及实数α,所有包容P的α-盘的交集定义为点集P的α-壳,P中位于α-壳边界上的点称为α-壳的顶点.根据该定义得出了以下结论:

　　1)当α>0时,对于点集P内的某一点,若能够找到一个通过该点且半径为1/α的圆包容点集P的所有点,那么该点必为点集P的α-壳顶点;

　　2)当α<0时,对于点集P内的某一点,若能够找到一个通过该点且半径为O1/α的圆使得P的所有点均在圆外或者在圆上,那么该点必为点集P的α壳顶点.

　　3)当α=0时,α-壳顶点即为凸壳顶点.

　　1.2 删除准则

　　基于1.1提出的定义和结论,文献[4]提出了α-壳的最小区域圆法评定圆度误差时无关点的删除准则:若点集P被一组同心圆α包容,同心圆α的内、外圆半径分别为R和R+X,那么,包容点集P的最小区域圆α0的内圆通过P的α1-壳(1/α1=XOR)的两个顶点,α0的外圆通过P的α2-壳(1/α2=R+2X)的两个顶点.即文献[4]的算法是:用半径为(XOR)的α-内壳去筛选最小区域内包容圆的特征点;用半径为(R+2X)的α-外壳去筛选最小区域外包容圆的特征点.

　　1.3 在最小外接圆评定中的应用

　　根据文献[4]的删点准则可得:只要α-外壳半径大于最小外接圆半径,就可用该半径的α-外壳筛选最小外接圆的特征点.由于最小外接圆的半径在所有的外包容圆中是最小的,因此,可用任意外包容圆的半径作为α-外壳半径.

　　1.4 在最大内接圆评定中的应用

　　与1.2同理:只要α-内壳半径小于最大内接圆半径,就可用该半径的α-内壳筛选最大内接圆的特征点.由于最大内接圆的半径在所有的内包容圆中是最大的,因此,可用任意内包容圆的半径作为α-内壳半径.

　　1.5 在最小区域圆评定中的应用

　　1.5.1经过最小二乘处理的删除准则

　　1)偏心量的估计

　　假设已经找到最小区域圆心及其内外包容圆如图1所示.

　　图中,最小区域内圆半径为RZ,最小区域圆度误差为εz,以最小区域圆心为原点建立直角坐标系,最小二乘圆心在x轴上,坐标为(δ,0),这里假设最小二乘圆心相对最小区域圆心向右偏.设采样n个点坐标为(X1,Y1),(X2,Y2),,(Xn,Yn),根据最小二乘算法有最小二乘圆心坐标