基于新型凸包法的平面度誤差評(píng)定

柴光耀，孫長(zhǎng)敬，單越康

(1.中國(guó)計(jì)量大學(xué) 質(zhì)量與安全工程學(xué)院，杭州 310018；2.蕭山工業(yè)研究院，杭州　311200)

?

基于新型凸包法的平面度誤差評(píng)定

柴光耀1，孫長(zhǎng)敬1，單越康2

(1.中國(guó)計(jì)量大學(xué) 質(zhì)量與安全工程學(xué)院，杭州 310018；2.蕭山工業(yè)研究院，杭州311200)

在傳統(tǒng)凸包法計(jì)算平面度誤差的基礎(chǔ)上，結(jié)合測(cè)點(diǎn)空間分布特點(diǎn)，提出了一種新的三維點(diǎn)集的凸包構(gòu)建方法。通過(guò)將測(cè)點(diǎn)向xy平面投影，快速確定首輪凸包頂點(diǎn)，然后由本輪的相鄰?fù)拱旤c(diǎn)建立棱線，在剩余點(diǎn)中如果有一點(diǎn)使得該點(diǎn)和棱線構(gòu)成的平面為凸包平面，則該點(diǎn)即為下一輪凸包頂點(diǎn)之一。通過(guò)這種方式，由本輪頂點(diǎn)，得到下輪頂點(diǎn)，依輪循環(huán)搜索直至無(wú)法得到新的凸包頂點(diǎn)，從而實(shí)現(xiàn)凸包的構(gòu)建。在進(jìn)一步利用凸包進(jìn)行平面度誤差評(píng)定過(guò)程中，對(duì)所有測(cè)點(diǎn)進(jìn)行擬合得到最小二乘平面，利用構(gòu)建凸包過(guò)程中得到的凸包平面方向向量及棱線向量數(shù)據(jù)，計(jì)算其與最小二乘平面的夾角，夾角較小的元素優(yōu)先進(jìn)行最小包容區(qū)域判別，以提高平面度誤差的計(jì)算效率，最后通過(guò)與相關(guān)文獻(xiàn)的數(shù)據(jù)進(jìn)行比較，驗(yàn)證了該方法的正確性。

三維凸包；平面度誤差；計(jì)算幾何；最小包容區(qū)域

0　引言

平面與直線一起構(gòu)成了保證幾何精度的基礎(chǔ)，例如，機(jī)床的全部幾何精度是以平面為基礎(chǔ)的。平面度誤差作為表示零件形狀的主要幾何要素之一，在許多場(chǎng)合下是影響儀器和機(jī)器精度、性能、質(zhì)量的重要因素[1]。國(guó)內(nèi)標(biāo)準(zhǔn)和國(guó)際標(biāo)準(zhǔn)對(duì)平面度誤差的定義是一致的，認(rèn)為包容實(shí)際平面，且具有最小寬度的兩平行平面的距離值[2-3]即為平面度誤差值,兩平行平面之間的區(qū)域即為最小包容區(qū)域。雖然基于最小二乘擬合和三遠(yuǎn)點(diǎn)的平面度誤差評(píng)定方法已得到了廣泛應(yīng)用，但由于其是一種近似計(jì)算，不符合最小條件判定原則，得到的結(jié)果往往偏大，會(huì)對(duì)生產(chǎn)活動(dòng)造成不良影響。

凸包法是基于凸殼理論的平面度誤差評(píng)定方法，由Traband等[4]首次提出，測(cè)得的工件表面數(shù)據(jù)實(shí)際上是一組空間點(diǎn)集S，基于空間點(diǎn)集S可構(gòu)建一多面體凸包，該凸包完全包覆所有空間點(diǎn)，且凸包的所有頂點(diǎn)S′為S的真子集?；诖?，Traband等提出了凸包在應(yīng)用于平面度誤差評(píng)定時(shí)的三個(gè)特性：特性1，S的最小包容區(qū)域與基于該點(diǎn)集構(gòu)建的凸包的最小包容區(qū)域是一致的；特性2，最小包容平面應(yīng)當(dāng)與凸包上的一條棱平行；特性3，最小包容區(qū)域必將穿過(guò)凸包上的一對(duì)對(duì)踵點(diǎn)。根據(jù)以上特性Traband認(rèn)為遍歷所有凸包頂點(diǎn)S′和凸包棱線L，其中點(diǎn)到棱距離的最大值即為所要求得的平面度誤差。Moon-Kyu Lee論述了這種算法的不足，并提出了基于旋轉(zhuǎn)凸包棱的平面度誤差計(jì)算方法，使之完全符合最小條件判別準(zhǔn)則[5-6]。凸包法作為一種計(jì)算幾何方法，相較于最小二乘法、旋轉(zhuǎn)法、逼近搜索、目標(biāo)規(guī)劃和智能算法等平面度評(píng)定方法具有結(jié)果唯一，理論明確，易于編程實(shí)現(xiàn)等優(yōu)點(diǎn)。本文針對(duì)凸包的構(gòu)建以及基于凸包的平面度誤差計(jì)算上提出了一些新的思路。

1　凸包的構(gòu)建

設(shè)需要進(jìn)行平面度誤差計(jì)算的數(shù)據(jù)為空間點(diǎn)集S，那么S對(duì)應(yīng)凸包的基本組成要素是分布在其表面的頂點(diǎn)集合S′，其中S′是S的子集。則構(gòu)建凸包的過(guò)程即為在S中搜索S′的過(guò)程。

1.1凸包頂點(diǎn)S′的初始化

圖1　原始數(shù)據(jù)點(diǎn)集向xy平面投影

圖2　凸包投影與Sxy關(guān)系示意

1.2次輪凸包頂點(diǎn)的確定

圖3　由相鄰的首輪頂點(diǎn)搜索得到次輪頂點(diǎn)

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

在P上或P下的搜索過(guò)程中，可以利用以下方式提高程序的運(yùn)行效率，如在對(duì)P上的搜索中，在S1上中任選一點(diǎn)P′(x′,y′,z′)，設(shè)基于兩相鄰的首輪凸包頂點(diǎn)P1(x1,y1,z1)、P2(x2,y2,z2)和P′建立的平面F方程為Ax+By+Cz+D=0(法線方向?yàn)閮A斜向上)，遍歷S1上中的剩余點(diǎn)，根據(jù)點(diǎn)到直線距離方程：

得到每點(diǎn)到F的距離Kx，由幾何學(xué)知識(shí)可知，當(dāng)該點(diǎn)處在沿著F的法向量方向上時(shí)，其距離值為正，反之為負(fù)。而在P上的搜索中，法線方向?yàn)樾毕蛏希虼薋為凸包平面的充要條件即為所有距離值Kx≤0。為了更快的搜索到目標(biāo)點(diǎn)P使F為凸包平面，在得到Kx后，S1上中的點(diǎn)可分為兩部分，其中Kx≥0的點(diǎn)為S1上上，而Kx≤0的點(diǎn)為S1上下，目標(biāo)點(diǎn)P必然可在S1上上中搜索得到。選擇S1上中距離F最大的點(diǎn)Pmax，根據(jù)該點(diǎn)和相鄰?fù)拱c(diǎn)P1、P2得到新的平面Fn。根據(jù)距離公式，求取S1上上中各點(diǎn)到Fn的距離Kxn，然后根據(jù)Kxn的正負(fù)再繼續(xù)劃分S1上上，再根據(jù)S1上上中距離Fn最大的點(diǎn)和P1、P2建立新平面，循環(huán)直至所有求得的距離值不大于零為止，此時(shí)的最遠(yuǎn)點(diǎn)即為目標(biāo)點(diǎn)P。距離值K在整個(gè)計(jì)算過(guò)程中，僅需要知道其符號(hào)及與其它點(diǎn)求得的距離值的相對(duì)大小即可，因此僅需計(jì)算Ax0+By0+Cz0+D即可完成上述判定和比較過(guò)程。

1.3搜索終點(diǎn)的確定

圖5　基于搜索

1.4凸包的閉合

圖6　上側(cè)凸包閉合示意

圖7　構(gòu)建成功的完整凸包

2　平面度誤差計(jì)算

通過(guò)上述凸包的構(gòu)建過(guò)程，可以獲得凸包的頂點(diǎn)S′，凸包的所有棱線L以及所有凸包平面F。通常情況下，在建立完凸包平面后，文獻(xiàn)[8]選擇遍歷S′和F，求取所有頂點(diǎn)到凸包平面的距離絕對(duì)值，并認(rèn)為最大的距離值即為所求的平面度誤差。但實(shí)際上這種計(jì)算方法，僅符合平面度誤差最小條件判定準(zhǔn)則中的三角形準(zhǔn)則，當(dāng)所計(jì)算的數(shù)據(jù)點(diǎn)的最小條件符合交叉準(zhǔn)則或直線準(zhǔn)則時(shí)，通過(guò)這種方法得到的結(jié)果就會(huì)偏離實(shí)際值，Moon-Kyu Lee就這一點(diǎn)在文獻(xiàn)[6]中進(jìn)行了相關(guān)論證。因此，若使得最終的評(píng)定結(jié)果更加可靠，則必須嚴(yán)格按照最小條件判定準(zhǔn)則對(duì)數(shù)據(jù)進(jìn)行評(píng)定。

在依據(jù)三原則進(jìn)行最小條件判定時(shí)，傳統(tǒng)的判定過(guò)程需要遍歷所有采樣點(diǎn)予以判別，由于點(diǎn)的遍歷過(guò)程是隨機(jī)的，沒(méi)有目的性，所以搜索效率較低。于是，張之江等[9]提出有序判別法，該法以最小二乘平面為分界面, 將采樣點(diǎn)區(qū)分為高點(diǎn)和低點(diǎn)，并按距離最小二乘面的遠(yuǎn)近，賦予高點(diǎn)和低點(diǎn)不同的搜索優(yōu)先級(jí)，大大提升了程序的搜索效率，在其介紹的實(shí)例中，第一輪搜索便成功獲得了符合最小條件判定準(zhǔn)則的數(shù)據(jù)點(diǎn)。此后，岳武陵等[10]也在最后的最小條件判定中運(yùn)用此法以提高搜索效率。

有序判別法的原理是認(rèn)為最小二乘面與實(shí)際的包容平面近似平行，所以距離最小二乘中心面越遠(yuǎn)的測(cè)點(diǎn)，理論上較為接近最小區(qū)域的包容平面，這些點(diǎn)有較大的可能性符合最小條件的判定原則。而判定原則對(duì)應(yīng)的采樣點(diǎn)組合模式分別是3-1(三角形模式)、2-2(交叉模式)和2-1(直線模式)，所以該法依據(jù)采樣點(diǎn)優(yōu)先級(jí)先后選取采樣點(diǎn)按照三模式之一進(jìn)行組合，再對(duì)組合后的數(shù)據(jù)進(jìn)行最小條件判定，如果當(dāng)前組合符合判定原則之一，則可運(yùn)用對(duì)應(yīng)公式，求解出平面度誤差值。

圖8　平面度誤差計(jì)算流程

3　實(shí)例驗(yàn)證

基于上述平面度誤差評(píng)定方法，筆者用C++開(kāi)發(fā)了相應(yīng)的計(jì)算軟件。為驗(yàn)證該算法的正確性，下面將文獻(xiàn)[12-14]中的幾組實(shí)測(cè)數(shù)據(jù)導(dǎo)入計(jì)算機(jī)進(jìn)行平面度誤差計(jì)算，并與原文結(jié)果進(jìn)行比較，結(jié)果如表1所示。

表1　計(jì)算結(jié)果比較

注1：該數(shù)據(jù)來(lái)源于文獻(xiàn)[12]的表5-6，在計(jì)算時(shí)發(fā)現(xiàn)一數(shù)據(jù)點(diǎn)(1543.5，5796，80)的Z坐標(biāo)異常偏高，后改為(1543.5，5796，8)后計(jì)算得到28.9357μm，結(jié)果與原文相符。

4　結(jié)論

從表1的對(duì)比結(jié)果可以看出，本算法的計(jì)算結(jié)果與其它方法相符，證明了該算法的正確性。由于本算法屬于計(jì)算幾何方法，最后的結(jié)果按標(biāo)準(zhǔn)規(guī)定進(jìn)行最小條件判別，因此相較于智能算法，結(jié)果唯一，精確可靠。在實(shí)際運(yùn)行中該算法的計(jì)算效率也得到了充分體現(xiàn)，如對(duì)文獻(xiàn)[12]的三組數(shù)據(jù)進(jìn)行評(píng)定時(shí)，各耗時(shí)38ms、10ms、60ms，相較于迭代的智能算法動(dòng)輒上百毫秒的計(jì)算時(shí)間有很大優(yōu)勢(shì)。

[1] 張善踵, 于瀛潔. 直線度平面度測(cè)量技術(shù)[M]. 北京: 中國(guó)計(jì)量出版社, 1997.

[2] GB/T 11337-2004，平面度誤差檢測(cè)[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] 羅英俊,李彬. 最小區(qū)域平面度的計(jì)算幾何評(píng)定算法研究[J]. 制造技術(shù)與機(jī)床,2009(1):92-94.

[9] 張之江,于瀛潔,張善鐘. 平面度誤差最小區(qū)域新算法——有序判別法[J]. 計(jì)量學(xué)報(bào),1998,19(1):16-22.

[10] 岳武陵,吳勇,蘇俊. 基于最小包容區(qū)域法的平面度誤差的快速評(píng)定法——新測(cè)點(diǎn)分類(lèi)法[J]. 計(jì)量技術(shù),2007(7):25-28.

[11] 岳武陵,吳勇,蘇俊. 平面度誤差的快速評(píng)定法——測(cè)點(diǎn)分類(lèi)法[J]. 計(jì)量學(xué)報(bào),2007,28(1):29-33.

[12] 王時(shí)禮. 大尺寸平面度的智能評(píng)定[D].廣州:華南理工大學(xué),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—)，男，河南信陽(yáng)人，中國(guó)計(jì)量大學(xué)碩士研究生，研究方向?yàn)闄z測(cè)技術(shù)與自動(dòng)化裝置，(E-mail)kychai@cjlu.edu.cn；通訊作者：孫長(zhǎng)敬(1968—)，男，安徽六安人，中國(guó)計(jì)量大學(xué)碩士生導(dǎo)師，博士，研究方向?yàn)楣鈾C(jī)電一體化，光電檢測(cè)、微機(jī)電系統(tǒng)，(E-mail)scj@cjlu.edu.cn。

TH161;TG801

A