基于新型凸包法的平面度误差评定

柴光耀，孙长敬，单越康

(1.中国计量大学 质量与安全工程学院，杭州 310018；2.萧山工业研究院，杭州　311200)



基于新型凸包法的平面度误差评定

柴光耀1，孙长敬1，单越康2

(1.中国计量大学 质量与安全工程学院，杭州 310018；2.萧山工业研究院，杭州311200)

在传统凸包法计算平面度误差的基础上，结合测点空间分布特点，提出了一种新的三维点集的凸包构建方法。通过将测点向xy平面投影，快速确定首轮凸包顶点，然后由本轮的相邻凸包顶点建立棱线，在剩余点中如果有一点使得该点和棱线构成的平面为凸包平面，则该点即为下一轮凸包顶点之一。通过这种方式，由本轮顶点，得到下轮顶点，依轮循环搜索直至无法得到新的凸包顶点，从而实现凸包的构建。在进一步利用凸包进行平面度误差评定过程中，对所有测点进行拟合得到最小二乘平面，利用构建凸包过程中得到的凸包平面方向向量及棱线向量数据，计算其与最小二乘平面的夹角，夹角较小的元素优先进行最小包容区域判别，以提高平面度误差的计算效率，最后通过与相关文献的数据进行比较，验证了该方法的正确性。

三维凸包；平面度误差；计算几何；最小包容区域

0　引言

平面与直线一起构成了保证几何精度的基础，例如，机床的全部几何精度是以平面为基础的。平面度误差作为表示零件形状的主要几何要素之一，在许多场合下是影响仪器和机器精度、性能、质量的重要因素[1]。国内标准和国际标准对平面度误差的定义是一致的，认为包容实际平面，且具有最小宽度的两平行平面的距离值[2-3]即为平面度误差值,两平行平面之间的区域即为最小包容区域。虽然基于最小二乘拟合和三远点的平面度误差评定方法已得到了广泛应用，但由于其是一种近似计算，不符合最小条件判定原则，得到的结果往往偏大，会对生产活动造成不良影响。

凸包法是基于凸壳理论的平面度误差评定方法，由Traband等[4]首次提出，测得的工件表面数据实际上是一组空间点集S，基于空间点集S可构建一多面体凸包，该凸包完全包覆所有空间点，且凸包的所有顶点S′为S的真子集。基于此，Traband等提出了凸包在应用于平面度误差评定时的三个特性：特性1，S的最小包容区域与基于该点集构建的凸包的最小包容区域是一致的；特性2，最小包容平面应当与凸包上的一条棱平行；特性3，最小包容区域必将穿过凸包上的一对对踵点。根据以上特性Traband认为遍历所有凸包顶点S′和凸包棱线L，其中点到棱距离的最大值即为所要求得的平面度误差。Moon-Kyu Lee论述了这种算法的不足，并提出了基于旋转凸包棱的平面度误差计算方法，使之完全符合最小条件判别准则[5-6]。凸包法作为一种计算几何方法，相较于最小二乘法、旋转法、逼近搜索、目标规划和智能算法等平面度评定方法具有结果唯一，理论明确，易于编程实现等优点。本文针对凸包的构建以及基于凸包的平面度误差计算上提出了一些新的思路。

1　凸包的构建

设需要进行平面度误差计算的数据为空间点集S，那么S对应凸包的基本组成要素是分布在其表面的顶点集合S′，其中S′是S的子集。则构建凸包的过程即为在S中搜索S′的过程。

1.1凸包顶点S′的初始化

图1　原始数据点集向xy平面投影

图2　凸包投影与Sxy关系示意

1.2次轮凸包顶点的确定

图3　由相邻的首轮顶点搜索得到次轮顶点

图4　基于提取S的特殊子集S1上和S1下

在P上或P下的搜索过程中，可以利用以下方式提高程序的运行效率，如在对P上的搜索中，在S1上中任选一点P′(x′,y′,z′)，设基于两相邻的首轮凸包顶点P1(x1,y1,z1)、P2(x2,y2,z2)和P′建立的平面F方程为Ax+By+Cz+D=0(法线方向为倾斜向上)，遍历S1上中的剩余点，根据点到直线距离方程：

得到每点到F的距离Kx，由几何学知识可知，当该点处在沿着F的法向量方向上时，其距离值为正，反之为负。而在P上的搜索中，法线方向为斜向上，因此F为凸包平面的充要条件即为所有距离值Kx≤0。为了更快的搜索到目标点P使F为凸包平面，在得到Kx后，S1上中的点可分为两部分，其中Kx≥0的点为S1上上，而Kx≤0的点为S1上下，目标点P必然可在S1上上中搜索得到。选择S1上中距离F最大的点Pmax，根据该点和相邻凸包点P1、P2得到新的平面Fn。根据距离公式，求取S1上上中各点到Fn的距离Kxn，然后根据Kxn的正负再继续划分S1上上，再根据S1上上中距离Fn最大的点和P1、P2建立新平面，循环直至所有求得的距离值不大于零为止，此时的最远点即为目标点P。距离值K在整个计算过程中，仅需要知道其符号及与其它点求得的距离值的相对大小即可，因此仅需计算Ax0+By0+Cz0+D即可完成上述判定和比较过程。

1.3搜索终点的确定

图5　基于搜索

1.4凸包的闭合

图6　上侧凸包闭合示意

图7　构建成功的完整凸包

2　平面度误差计算

通过上述凸包的构建过程，可以获得凸包的顶点S′，凸包的所有棱线L以及所有凸包平面F。通常情况下，在建立完凸包平面后，文献[8]选择遍历S′和F，求取所有顶点到凸包平面的距离绝对值，并认为最大的距离值即为所求的平面度误差。但实际上这种计算方法，仅符合平面度误差最小条件判定准则中的三角形准则，当所计算的数据点的最小条件符合交叉准则或直线准则时，通过这种方法得到的结果就会偏离实际值，Moon-Kyu Lee就这一点在文献[6]中进行了相关论证。因此，若使得最终的评定结果更加可靠，则必须严格按照最小条件判定准则对数据进行评定。

在依据三原则进行最小条件判定时，传统的判定过程需要遍历所有采样点予以判别，由于点的遍历过程是随机的，没有目的性，所以搜索效率较低。于是，张之江等[9]提出有序判别法，该法以最小二乘平面为分界面, 将采样点区分为高点和低点，并按距离最小二乘面的远近，赋予高点和低点不同的搜索优先级，大大提升了程序的搜索效率，在其介绍的实例中，第一轮搜索便成功获得了符合最小条件判定准则的数据点。此后，岳武陵等[10]也在最后的最小条件判定中运用此法以提高搜索效率。

有序判别法的原理是认为最小二乘面与实际的包容平面近似平行，所以距离最小二乘中心面越远的测点，理论上较为接近最小区域的包容平面，这些点有较大的可能性符合最小条件的判定原则。而判定原则对应的采样点组合模式分别是3-1(三角形模式)、2-2(交叉模式)和2-1(直线模式)，所以该法依据采样点优先级先后选取采样点按照三模式之一进行组合，再对组合后的数据进行最小条件判定，如果当前组合符合判定原则之一，则可运用对应公式，求解出平面度误差值。

图8　平面度误差计算流程

3　实例验证

基于上述平面度误差评定方法，笔者用C++开发了相应的计算软件。为验证该算法的正确性，下面将文献[12-14]中的几组实测数据导入计算机进行平面度误差计算，并与原文结果进行比较，结果如表1所示。

表1　计算结果比较

注1：该数据来源于文献[12]的表5-6，在计算时发现一数据点(1543.5，5796，80)的Z坐标异常偏高，后改为(1543.5，5796，8)后计算得到28.9357μm，结果与原文相符。

4　结论

从表1的对比结果可以看出，本算法的计算结果与其它方法相符，证明了该算法的正确性。由于本算法属于计算几何方法，最后的结果按标准规定进行最小条件判别，因此相较于智能算法，结果唯一，精确可靠。在实际运行中该算法的计算效率也得到了充分体现，如对文献[12]的三组数据进行评定时，各耗时38ms、10ms、60ms，相较于迭代的智能算法动辄上百毫秒的计算时间有很大优势。

[1] 张善踵, 于瀛洁. 直线度平面度测量技术[M]. 北京: 中国计量出版社, 1997.

[2] GB/T 11337-2004，平面度误差检测[S].

[3] ISO 1101-2012，Geometrical product specificat-ions (GPS) — Geometrical tolerancing — Tole-rances of form, orientation, location and run-out[S].

[4] Traband M T, Joshi S, Wysk R A, et al. Evalua-tion of straightness and flatness tolerances using the minimum zone[J]. Manufacturing Revi-ew, 1989, 2(3): 189-195.

[5] Lee M K. A new convex-hull based approach to evaluating flatness tolerance[J]. Computer-Ai-ded Design, 1997, 29(12): 861-868.

[6] Lee M K. An enhanced convex-hull edge method for flatness tolerance evaluation[J]. Computer-Aided Design, 2009, 41(12): 930-941.

[7] Barber C B, Dobkin D P, Huhdanpaa H. The quic-khull algorithm for convex hulls[J]. ACM Tran-sactions on Mathematical Software (TOMS), 1996, 22(4): 469-483.

[8] 罗英俊,李彬. 最小区域平面度的计算几何评定算法研究[J]. 制造技术与机床,2009(1):92-94.

[9] 张之江,于瀛洁,张善钟. 平面度误差最小区域新算法——有序判别法[J]. 计量学报,1998,19(1):16-22.

[10] 岳武陵,吴勇,苏俊. 基于最小包容区域法的平面度误差的快速评定法——新测点分类法[J]. 计量技术,2007(7):25-28.

[11] 岳武陵,吴勇,苏俊. 平面度误差的快速评定法——测点分类法[J]. 计量学报,2007,28(1):29-33.

[12] 王时礼. 大尺寸平面度的智能评定[D].广州:华南理工大学,2010.

[13] Tseng H Y. A genetic algorithm for assessing flatness in automated manufacturing systems[J]. Journal of Intelligent Manufacturing, 2006,17(3): 301-306.

[14] Huang S T, Fan K C, Wu J H. A new minimum zo-ne method for evaluating flatness errors[J].Precision Engineering, 1993, 15(93):25-32.

(编辑赵蓉)

The Evaluation of Flatness Error Based on a New Convex Hull Method

CHAI Guang-yao1，SUN Chang-jing1，SHAN Yue-kang2

(1.College of Quality and Safety Engineering，China Jiliang University，Hangzhou 310018，China；2.Xiaoshan Industrial Research Institute，Hangzhou 311200，China)

Take into account the spatial distribution of data points, a new algorithm to construct 3D convex hull is proposed for the evaluation of flatness error based on the traditional method. The first round convex hull vertices can be obtained by project all data points to the xy-plan. Create an edge by connect adjacent vertices of current round, and search one point in data points. If the plan based on the point and edge is a convex hull plan, the new point will be identified as one of the next round vertices. The next round vertices can be find based on the current round vertices by using this method. Circular search round by round until new vatic cannot fined, so a complete convex hull will be obtained. During the evaluation of flatness error by using convex hull method, the least square plan is obtained by fitting all of the data points. To enhance the computational efficiency, the included angle between LS plan and convex hull plan or edge are calculated, the smaller the angle the higher the priority that take into minimum zone distinguish. To test the validity of the method, a number of test data sets of some published in the literature were solved.

3D convex hull; flatness error; computational geometry; minimum zone

1001-2265(2016)04-0097-04DOI:10.13462/j.cnki.mmtamt.2016.04.026

2015-06-01；

2015-07-05

柴光耀(1990—)，男，河南信阳人，中国计量大学硕士研究生，研究方向为检测技术与自动化装置，(E-mail)kychai@cjlu.edu.cn；通讯作者：孙长敬(1968—)，男，安徽六安人，中国计量大学硕士生导师，博士，研究方向为光机电一体化，光电检测、微机电系统，(E-mail)scj@cjlu.edu.cn。

TH161;TG801

A