基于新型凸包法的平面度誤差評定

柴光耀，孫長敬，單越康

(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