曲線等誤差直線擬合的算法研究及其應(yīng)用

趙玉剛 于光偉 張 健 劉 肖

(山東理工大學(xué)機(jī)械工程學(xué)院，山東淄博 255049)

目前，多數(shù)機(jī)床的數(shù)控系統(tǒng)只具備直線插補(bǔ)和圓弧插補(bǔ)功能，而實(shí)際生產(chǎn)加工中常常會(huì)遇到零件輪廓為非圓曲線。此時(shí)就需要在給定的精度范圍內(nèi)，用一系列直線或圓弧來(lái)逼近它們。直線擬合法因其簡(jiǎn)單直觀而應(yīng)用較多。直線擬合曲線的方法有：等間距法，等弦長(zhǎng)法，等誤差法等。等間距法和等弦長(zhǎng)法計(jì)算較簡(jiǎn)單但在曲線曲率變化較大的場(chǎng)合不易控制插補(bǔ)精度和節(jié)點(diǎn)數(shù)。而等誤差法能盡可能地減少節(jié)點(diǎn)數(shù)，適用于曲率變化較大的曲線輪廓［1］。曲線等誤差直線擬合節(jié)點(diǎn)計(jì)算的一般方法是：在已知節(jié)點(diǎn)處建立允差圓，聯(lián)立允差圓與曲線的斜率關(guān)系解高次方程組求得切線斜率，后據(jù)此斜率建立擬合直線的方程，聯(lián)立曲線方程求得擬合直線與曲線的交點(diǎn)做為下一個(gè)擬合節(jié)點(diǎn)。但此算法的弊端有二，一是對(duì)高次曲線(如橢圓弧)而言，應(yīng)用該方法時(shí)往往陷入高次方程組的求解中，而確定高次方程組的唯一解往往很復(fù)雜；二是該算法沒(méi)有充分考慮到實(shí)際數(shù)控加工中，曲線的拐點(diǎn)(如正弦曲線)應(yīng)該作為擬合節(jié)點(diǎn)。據(jù)此本文提出了一種基于羅爾定理與二分法的曲線等誤差直線擬合新算法，該算法通過(guò)將擬合區(qū)間適當(dāng)劃分成為多個(gè)凹凸性一致的單值區(qū)間(若擬合區(qū)間已經(jīng)是凹凸性一致的單值區(qū)間則不必劃分)，在各個(gè)單值區(qū)間內(nèi)運(yùn)用羅爾定理與二分法迭代求解擬合直線與曲線上對(duì)應(yīng)的弧之間的誤差來(lái)逐步逼近程序所要求的允許誤差。該算法避免了高次方程組的求解，容易控制插補(bǔ)精度，易于實(shí)現(xiàn)程序編制和數(shù)控加工應(yīng)用。

1 基于羅爾定理與二分法的曲線等誤差直線擬合新算法思想

1.1 曲線等誤差直線擬合的一般算法

如圖1所示，設(shè)零件輪廓曲線的數(shù)學(xué)方程為y=f(x)。節(jié)點(diǎn)坐標(biāo)計(jì)算步驟如下［2］：

(1)以起點(diǎn) A(xa，ya)為圓心，以允差 δ為半徑作圓。其圓方程為

(2)作允差圓與曲線y=f(x)的公切線MN，則可求公切線MN的斜率k

為求 yn、ym、xn、xm，需要解下面的方程組

式中y=F(x)為允差圓方程。

(3)過(guò)A點(diǎn)作斜率為k的直線，則得到直線插補(bǔ)段AB，其方程為

(4)求直線插補(bǔ)節(jié)點(diǎn)B點(diǎn)的坐標(biāo)，解方程組

求得交點(diǎn)B(xb，yb)的坐標(biāo)值，便是第一個(gè)直線插補(bǔ)節(jié)點(diǎn)。

(5)按以上步驟順次求得C，D等各節(jié)點(diǎn)坐標(biāo)。

此算法先求得允差圓與曲線的公切線斜率k，后聯(lián)立方程組(5)求解得到下一插補(bǔ)點(diǎn)。當(dāng)要擬合高次曲線時(shí)，方程組(3)為四元高次方程組，其求解過(guò)程非常復(fù)雜且確定唯一解也需要更多的判斷條件。另外在實(shí)際數(shù)控加工中，若曲線有拐點(diǎn)，則拐點(diǎn)應(yīng)視為擬合節(jié)點(diǎn)。

1.2 基于羅爾定理與二分法的曲線等誤差直線擬合新算法

如圖2所示，設(shè)在曲線y=f(x)的一個(gè)凹凸性一致的單值閉合區(qū)間AB上，用直線段連接曲線的兩個(gè)端點(diǎn)A、B，則它與曲線形成一個(gè)弓形，我們稱這條直線為曲線的弦。只要該曲線上的點(diǎn)到弦AB的最大距離hmax小于程序設(shè)定的允許誤差res，我們就可以用直線段AB來(lái)擬合曲線段 AB［3］。而當(dāng) hmax大于允許誤差res時(shí)，就需要運(yùn)用二分法將區(qū)間AB進(jìn)行劃分以找到下一個(gè)擬合點(diǎn)F。再連接直線段FB，在曲線段FB上再次進(jìn)行同樣流程操作，最終可得到所有擬合點(diǎn)。

本小節(jié)先推導(dǎo)曲線上的點(diǎn)到它對(duì)應(yīng)的弦之間的最大距離公式，后詳述二分法迭代求解擬合點(diǎn)的應(yīng)用過(guò)程。

設(shè)直線AB的斜率為k，因曲線的AB段為凹凸性一致的單值區(qū)間，則由羅爾定理知，在曲線AB上有且僅有一點(diǎn)D，使得曲線AB在該點(diǎn)的斜率kd，有：

而D 點(diǎn)的坐標(biāo)(xd，yd)可通過(guò)方程(7)求得：

弦AB所在直線方程為：

則點(diǎn) D(xd，yd)到弦 AB 的距離為

由導(dǎo)數(shù)的性質(zhì)及意義可知，曲線AB上的點(diǎn)中，D弦AB的距離最大，且D到弦AB的距離h就是弦AB逼近曲線AB時(shí)的擬合誤差。

在單值閉合區(qū)間AB上，弦AB擬合曲線AB的擬合誤差hAB往往大于程序設(shè)定的允許誤差res，這時(shí)就需要在區(qū)間AB上運(yùn)用二分法迭代多次求解弦的擬合誤差來(lái)逼近允許誤差res。二分法應(yīng)用過(guò)程如下：

(1)初始化A點(diǎn)坐標(biāo)為擬合區(qū)間起點(diǎn)坐標(biāo)(xa，ya)，B點(diǎn)坐標(biāo)為擬合區(qū)間終點(diǎn)坐標(biāo)(xb，yb)。A點(diǎn)為當(dāng)前已知擬合點(diǎn)，動(dòng)點(diǎn)。

(2)將A點(diǎn)賦值給S1點(diǎn)，B點(diǎn)賦值給S2點(diǎn)。S1、S2點(diǎn)為區(qū)間二分迭代時(shí)用到的點(diǎn)，動(dòng)點(diǎn)。

(3)計(jì)算弦AB擬合曲線AB的擬合誤差hAB，賦值h=hAB。

(4)比較擬合誤差h與允差res的大小：如果h＞res，轉(zhuǎn)(5)步；如果 h≤res，則區(qū)間終點(diǎn) B作為最終擬合節(jié)點(diǎn)，等誤差直線擬合過(guò)程結(jié)束。

(5)取直線段S1S2的中點(diǎn)C橫坐標(biāo)之值xm=(xs1+xs2)/2，計(jì)算ym=f(xm)，得到直線段S1S2中點(diǎn)C在橢圓弧上對(duì)應(yīng)的二分點(diǎn)M(xm，ym)。

(6)計(jì)算弦AB擬合曲線AM的擬合誤差hAM，賦值h=hAM。

(7)比較擬合誤差h與允差res的大?。喝绻鹔＞res，M 點(diǎn)賦值給 S2；如果 h≤res，M 點(diǎn)賦值給 S1。

(8)計(jì)算|fres-h|之值，如果小于或等于指定的誤差值，尋找插補(bǔ)點(diǎn)結(jié)束，得到新擬合節(jié)點(diǎn)F，轉(zhuǎn)(9)；如果大于指定的誤差值，返回步驟(5)繼續(xù)查找。

(9)F賦值給A點(diǎn)，轉(zhuǎn)步驟(2)。

2 凹凸性一致的單值區(qū)間的劃分

設(shè)曲線方程為y=f(x)，擬合區(qū)間為x∈［a，b］，允許誤差為res。為高質(zhì)量地?cái)M合曲線，滿足數(shù)控加工的實(shí)際需要，應(yīng)先判斷曲線是否存在拐點(diǎn)，若存在，則拐點(diǎn)應(yīng)直接作為曲線的擬合點(diǎn)。

若在開區(qū)間x∈(a，b)求得y=f(x)的一系列拐點(diǎn)橫坐標(biāo)為 a1＜a2＜… ＜an，則整個(gè)閉區(qū)間 x∈［a，b］可劃分為 n+1 個(gè)小區(qū)間［a，a1］，［a1，a2］，…［an-1，an］，［an，b］，在這n+1個(gè)小區(qū)間內(nèi)可按上一小節(jié)的算法求得所有擬合節(jié)點(diǎn)。

如正弦曲線y=asin(wx+t)+y0，易知其拐點(diǎn)坐標(biāo)(xd，yd)滿足方程

對(duì)有些高次隱式非線性方程f(x，y)=0，在其要求的擬合區(qū)間內(nèi)往往為非單值函數(shù)，此時(shí)也需要通過(guò)適當(dāng)方法將整個(gè)擬合區(qū)間劃分為多個(gè)凹凸性一致的單值區(qū)間。以橢圓為例，分析此類函數(shù)曲線的單值區(qū)間劃分方法，如圖3所示，設(shè)橢圓方程為x2/a2+y2/b2=1，擬合方向?yàn)槟鏁r(shí)針。不妨設(shè)當(dāng)前已知節(jié)點(diǎn)為A(xa，ya)，位于第一象限。當(dāng)下一節(jié)點(diǎn)B出現(xiàn)在弧S1S2上時(shí)，則AB直線段擬合誤差范圍是(0，b-ya)，誤差上限是在AB平行于X軸時(shí)取得的；當(dāng)下一節(jié)點(diǎn)B出現(xiàn)在弧S2S3上時(shí)，則AB直線段擬合誤差范圍是(b-ya，)，誤差上限是在 AB關(guān)于橢圓圓心對(duì)稱時(shí)取得的，此時(shí)直線AB斜率為k=ya/xa。再結(jié)合程序設(shè)定的允許誤差res，可進(jìn)行如下判別：

表1 橢圓逆圓弧等誤差直線擬合區(qū)間劃分

(2)如果0＜res＜b-ya，則下一擬合點(diǎn)一定出現(xiàn)在弧S1S2上，此區(qū)間y相對(duì)于x的單值函數(shù)，可在此區(qū)間二分迭代多次求得擬合點(diǎn)；

(3)如果b-ya≤res＜，則下一擬合點(diǎn)一定出現(xiàn)在弧S2S3上，此區(qū)間x相對(duì)于y的單值函數(shù)，可在此區(qū)間二分迭代多次求得擬合點(diǎn)。

若當(dāng)前已知節(jié)點(diǎn)位于其它象限，討論過(guò)程同上。橢圓逆圓弧等誤差直線擬合區(qū)間劃分及擬合誤差表達(dá)式見表(1)。

3 曲線等誤差直線擬合算法流程

基于羅爾定理與二分法的曲線等誤差直線擬合算法框圖見圖4。該算法先判斷曲線是否存在拐點(diǎn)，若存在，則應(yīng)以拐點(diǎn)為邊界進(jìn)行擬合區(qū)間的第一次劃分；后判斷曲線的擬合區(qū)間是否是單值區(qū)間，若不是，則可通過(guò)適當(dāng)方法進(jìn)行區(qū)間的再一次劃分，是整個(gè)擬合區(qū)間被劃分成為多個(gè)凹凸性一致的單值區(qū)間。在每個(gè)單值區(qū)間內(nèi)就可以運(yùn)用二分法迭代求解擬合誤差以逼近允許誤差，以此求得擬合點(diǎn)。若函數(shù)的整個(gè)區(qū)間較長(zhǎng)且已經(jīng)是單值區(qū)間，則為了加快擬合節(jié)點(diǎn)的計(jì)算速度，可適當(dāng)增加附加條件來(lái)劃分區(qū)間以減少迭代次數(shù)(如限定擬合直線的長(zhǎng)度)。

4 曲線等誤差直線擬合的軌跡仿真實(shí)例

基于本文算法，以C++Builder 6.0為開發(fā)工具，編程實(shí)現(xiàn)了幾種常見曲線的等誤差直線擬合，如橢圓弧、正弦曲線、拋物線、雙曲線等。

當(dāng)橢圓圓心坐標(biāo)為(100，0)，半軸長(zhǎng) a=300，b=200，起始角度 startangle=30，終止角度 endangle=300，插補(bǔ)方向?yàn)槟婊?，允差res=8時(shí)，其仿真效果如圖5，節(jié)點(diǎn)計(jì)算結(jié)果見圖6。

仿真結(jié)果表明，由于該算法避免了高次方程組的求解，代之以迭代多次線性求解擬合誤差以逼近允許誤差，使得節(jié)點(diǎn)計(jì)算簡(jiǎn)單可靠，處理速度較快，在線切割，輪廓銑削加工上有較大應(yīng)用價(jià)值。

5 結(jié)語(yǔ)

曲線等誤差直線擬合的一般解法是設(shè)定允差圓的方程后解高次方程組，而確定其唯一解往往很復(fù)雜。本文提出了一種基于羅爾定理與二分法的擬合方法，其思想是先將整個(gè)擬合區(qū)間適當(dāng)劃分成為多個(gè)凹凸性一致的單值區(qū)間，后在這多個(gè)單值區(qū)間內(nèi)二分迭代多次求解弦與對(duì)應(yīng)的曲線弧之間的擬合誤差來(lái)逼近允許誤差，體現(xiàn)了正難則反的逆向思維。該算法避免了高次方程組的求解，容易控制擬合精度，易于實(shí)現(xiàn)程序編制，在數(shù)控加工中有較大應(yīng)用價(jià)值。

［1］于洋，魏娟.等誤差直線逼近非圓曲線節(jié)點(diǎn)計(jì)算新方法［J］.組合機(jī)床與自動(dòng)化加工技術(shù)，2005(5)：32-33.

［2］趙玉剛，宋現(xiàn)春主編.數(shù)控技術(shù)［M］.北京：機(jī)械工業(yè)出版社，2003.

［3］周曉銘，陶俊才，等.基于二分法的曲線等誤差圓弧擬合算法及其應(yīng)用［J］.南昌大學(xué)學(xué)報(bào)，2008(1)：100-102.

［4］王麗萍，孫國(guó)防，等.非圓曲線數(shù)控編程的等誤差逼近及其實(shí)現(xiàn)［J］.現(xiàn)代制造工程，2006(10)：30-32.