基于α-壳的圆度误差评定无关点删除算法

　　1 前言

　　圆度误差是评价类圆形工件横截面形状和尺寸误差的一个重要参数,常用的圆度误差评定方法包括[1]:最小区域圆法(MZC)、最小二乘圆法(LSC)、最小外接圆法(MCC)、最大内接圆法(MIC)等。当各种方法评定结果不一致时,采用最小区域法的评定结果作为最终结果。最小区域法是指寻找包容待测轮廓、且半径差最小的两个同心圆,将这两同心圆的半径差作为待测轮廓的圆度误差。

　　在圆度误差评定过程中,采样点越多则评定结果越接近于真实值。但是,对于几乎所有的圆度误差评定方法而言,采样点越多算法就会越复杂,计算复杂度越高。研究证明[2],采用最小区域圆法进行圆度误差评定时,最小区域圆的内圆和外圆至少分别通过轮廓采样点集中的两个点,最终的圆度误差决定于这四个点的相对位置,而与其它点的坐标无关。为此,如果能在计算圆度误差前有效删除那些无关点便可在保证不会对圆度误差的评定结果产生影响的情况下减小计算复杂度[3,4]。

　　计算几何是二十世纪七十年代出现的一个研究领域[5],部分学者已将计算几何方法应用到圆度误差的评定中[3,6,7]。文献[3]提出了一种采用计算几何方法删除圆度误差评定无关点的算法,该算法引入了α-壳的概念,并给出了最小区域圆法评定圆度误差时无关点的删除准则和算法:若点集P被一组同心圆A包容,同心圆A的内、外圆半径分别为R和R+ω,那么,包容点集P的最小区域圆A0的内圆通过P的α1-壳(1PA1=X-R)的两个顶点,α0的外圆通过P的α2-壳(1Pα2=R+2ω)的两个顶点。

　　本文研究发现,采用较文献[3]中更严格的准则可以更为有效的对圆度误差评定无关点进行删除。因而,本文对最小区域圆圆度误差评定中无关点的删除准则和删除算法作进一步研究,提出了一则关于α-壳的定理及无关点删除算法。

　　2 α-壳

　　文献[5]中给出了平面点集P的α-壳的定义。α-壳是凸壳概念的延伸。在定义α-壳之前,这里首先给出α-盘(α-disc)的定义(如图1)。

　　定义1:对于任意实数α:

　　当α>0时,α-盘定义为平面内半径为1/α的圆包容的所有区域;

　　当α=0时,α-盘定义为一条直线一侧的半平面;

　　当α<0时,α-盘定义为平面内半径为-1/α的圆外及圆上的所有区域。

　　结合α-盘定义给出α-壳的定义如下.

　　定义2:对于平面点集P及实数α,所有包容P的α-盘的交集定义为点集P的α-壳,P中位于α-壳边界上的点称为α-壳的顶点。