第三章_曲線擬合算法的研究

1、第三章 曲線擬合算法的研究3.1 引言隨著航空、汽車等現(xiàn)代工業(yè)與計算機(jī)技術(shù)的發(fā)展，圓錐曲線與列表點曲線已經(jīng)成為形狀數(shù)學(xué)描述的常用方法，得到了廣泛的應(yīng)用。為了滿足激光切割加工任務(wù)的需要，自動編程系統(tǒng)集成了多種曲線擬合算法，這樣利用現(xiàn)有的激光切割機(jī)，即可實現(xiàn)特殊曲線的插補(bǔ)功能，極大地豐富系統(tǒng)的插補(bǔ)能力，滿足復(fù)雜的生產(chǎn)要求。3.2 圓錐曲線擬合算法的研究在經(jīng)濟(jì)型數(shù)控系統(tǒng)中，對于圓錐曲線即平面二次曲線的加工是數(shù)控加工中經(jīng)常遇到的問題，隨著數(shù)控加工對圓錐曲線插補(bǔ)的需求，近年來有關(guān)各種圓錐曲線的插補(bǔ)算法應(yīng)運(yùn)而生26。常用的解決方法是先用低次的有理參數(shù)曲線擬合或?qū)⑵潆x散，再用直線、圓弧逼近，然后才能進(jìn)行數(shù)控

2、加工28。本章從一個新的視角利用雙圓弧方法，提出先對圓錐曲線進(jìn)行標(biāo)準(zhǔn)化處理，再用雙圓弧擬合逼近，然后再進(jìn)行數(shù)控加工。這樣的優(yōu)點是：圓弧樣條的等距曲線還是圓??；雙圓弧樣條能達(dá)到C1連續(xù)，基本上能滿足要求；所有數(shù)控系統(tǒng)都具有直線插補(bǔ)和圓弧插補(bǔ)功能，無需增加額外負(fù)擔(dān)。由于工程應(yīng)用不同，對曲線擬合的要求也不同。有的只要求擬合曲線光滑，有的要求光順9-10。本章中開發(fā)的軟件要求是：支持多種常用圓錐曲線的擬合；擬合曲線要求光滑；擬合曲線與函數(shù)曲線間的誤差應(yīng)控制在允許的范圍之內(nèi)，且擬合圓弧段數(shù)較少。本章提出的對圓錐曲線的插補(bǔ)，是建立在對平面任意二次曲線可以進(jìn)行分類的基礎(chǔ)上，先將二次曲線進(jìn)行分類，然后對各類曲

3、線分別進(jìn)行雙圓弧擬合，這樣就可以直接利用數(shù)控系統(tǒng)的圓弧插補(bǔ)功能進(jìn)行插補(bǔ)。3.2.1 圓錐曲線的一般理論9在平面直角坐標(biāo)系中，二元二次方程所表示的曲線稱為二次曲線。其中系數(shù)、為實常數(shù)，且、不同時為零。 (3.1)式（3.1）稱為圓錐曲線的隱式方程。令 （3.2）稱上式為二元二次方程（3.1）的判別式。時，（3.1）式為橢圓型曲線（包括圓、橢圓和虛橢圓）；時，（3.1）式為拋物線型曲線（包括兩平行直線和虛直線）；時，（3.1）式為雙曲型曲線（包括兩相交直線）。在不同的坐標(biāo)系下，平面上一點的坐標(biāo)、一條曲線的方程是不同的。通過利用坐標(biāo)變換（即坐標(biāo)軸的平移和旋轉(zhuǎn)），可以將一般二次曲線方程化成最簡形式，借

4、以確定曲線的形狀和位置。一、坐標(biāo)軸的平移只改變坐標(biāo)原點的位置，而不改變坐標(biāo)軸的方向和長度單位，這樣的坐標(biāo)變換叫做坐標(biāo)軸的平移，簡稱平移或移軸。將舊坐標(biāo)系平移到,那么平面上任一點在舊坐標(biāo)系與新坐標(biāo)系的坐標(biāo)和具有關(guān)系： （3.3）其中是新坐標(biāo)系中的原點在舊坐標(biāo)系里的坐標(biāo)。公式（3.3）叫做平移變換公式。二、坐標(biāo)軸的旋轉(zhuǎn)坐標(biāo)原點的位置和長度單位都不改變，讓坐標(biāo)軸繞原點按同一方向旋轉(zhuǎn)同一個角度，這種坐標(biāo)變換叫做坐標(biāo)軸的旋轉(zhuǎn)，簡稱旋轉(zhuǎn)或轉(zhuǎn)軸。把舊坐標(biāo)系繞原點旋轉(zhuǎn)同一個角度到，那么平面上的任一點在舊坐標(biāo)系與新坐標(biāo)系下的坐標(biāo)和之間具有關(guān)系： （3.4）公式（3.4）叫做旋轉(zhuǎn)變換公式。適當(dāng)選擇坐標(biāo)系，二次曲線

5、方程經(jīng)過坐標(biāo)系的旋轉(zhuǎn)和平移變換，可簡化成幾種標(biāo)準(zhǔn)方程。1中心二次曲線方程可以簡化成下面5種標(biāo)準(zhǔn)方程之一：a) （橢圓）；b) （虛橢圓）；c) （點橢圓或稱變態(tài)橢圓）；d) （雙曲線）；e) （兩相交直線，或稱變態(tài)雙曲線）。2無心二次曲線的標(biāo)準(zhǔn)方程為： （拋物線）3線心二次曲線方程可化簡成下面3種標(biāo)準(zhǔn)方程之一：a) （兩平行直線）；b) （兩平行共軛虛直線）；c) （兩重合直線）。由實際的工程應(yīng)用可知，在實際的加工中只有橢圓、雙曲線、拋物線和直線具有工程價值。數(shù)控機(jī)床具有直線和圓弧的插補(bǔ)功能，所以在本章中只考慮橢圓、雙曲線和拋物線的擬合算法。實現(xiàn)橢圓、雙曲線、拋物線的擬合算法主要步驟為：1）參

6、數(shù)輸入表1 平面圓錐曲線輸入?yún)?shù)列表遵照數(shù)控NC程序編程規(guī)范，以最少輸入?yún)?shù)唯一定義曲線為準(zhǔn)則，設(shè)計了曲線的輸入?yún)?shù)，見表1。曲線類型參數(shù)說明拋物線順逆方向、起點、終點、焦點坐標(biāo)橢圓順逆方向、起點、終點、中心坐標(biāo)、長軸相對于X軸的轉(zhuǎn)角雙曲線順逆方向、起點、終點、中心坐標(biāo)、長軸相對于X軸的轉(zhuǎn)角2）曲線標(biāo)準(zhǔn)化利用坐標(biāo)系平移、旋轉(zhuǎn)變換，將曲線變換到可以利用最簡方程表示的坐標(biāo)系下，并求解方程，詳見附錄1。為了便于計算，最后確定采用下列形式作為各曲線的標(biāo)準(zhǔn)方程式。拋物線：橢圓：雙曲線：3）求取曲線的極值點、拐點，對曲線進(jìn)行分割，建立有序的型值點序列。型值點的排序規(guī)則為：拋物線：以為標(biāo)準(zhǔn)，按遞增順序排列；

7、橢圓：以為標(biāo)準(zhǔn)，按遞增順序排列；雙曲線：以為標(biāo)準(zhǔn)，按遞增順序排列； 注：為起點橫坐標(biāo)，為第i個點橫坐標(biāo)；為起點極角，第i個極角。4）取，兩個型值點，進(jìn)行雙圓弧曲線擬合。5）如果擬合結(jié)果的法向誤差滿足規(guī)定誤差，則轉(zhuǎn)6）,否則，則轉(zhuǎn)7）。6）將擬合結(jié)果送入輸出鏈表中，如果曲線全部擬合完成，則結(jié)束，否則轉(zhuǎn)4）。7）在，之間按照0.618,0.382的比率插入新的型值點，再轉(zhuǎn)4）。上述，為曲線擬合的主要步驟，下面詳細(xì)的介紹一下雙圓弧擬合算法。3.2.2 曲線的常用雙圓弧擬合算法17-25按平面曲線給定一列有序型值點（節(jié)點），每相鄰節(jié)點之間由兩條相切圓弧構(gòu)成，兩圓弧分別通過一個節(jié)點，且節(jié)點處的切線斜率與

8、曲線在節(jié)點處的斜率相等，叫做曲線的雙圓弧擬合。雙圓弧擬合有六個參數(shù)需要確定：兩節(jié)點，；兩節(jié)點，處的切線斜率；雙圓弧的切點；雙圓弧切點處的公切線斜率。前四個參數(shù)可由曲線的參數(shù)方程按給定參數(shù)值求得。雙圓弧擬合方法主要根據(jù)后兩個參數(shù)的求法而不同，但不難證明兩圓弧相切點位置結(jié)論：相切點位置有無窮多個；相切點的軌跡是一個圓弧軌跡?。ㄟ^相鄰兩節(jié)點的弧，且在兩節(jié)點處切線夾角等于曲線在兩節(jié)點處切線夾角）。為確保雙圓弧的正確擬合，要求：1) 兩擬合圓弧應(yīng)滿足保凸要求，即兩相鄰節(jié)點，處切線需有實交點（沿某切線方向前進(jìn)時，與另一切線的反向延長線的交點，稱為實交點，反之為虛交點）；2) 擬合的圓弧段需要采用劣弧，即兩

9、節(jié)點連線與兩切線構(gòu)成的三角形中（見圖8，圖9，圖10）。O1O2P1P2MT圖8 垂直平分線法擬合雙圓弧原曲線O1O2P1P2MT圖9 平行弦線法擬合雙圓弧原曲線O2P1P2MT圖10 平均轉(zhuǎn)角法擬合雙圓弧原曲線/2/2O13.2.3 公切線確定方法1.常用的公切線確定方法有以下三種：1) 垂直平分線法：相鄰兩節(jié)點連線的垂直平分線與軌跡弧的交點作為兩擬合圓弧的切點（圖8）；2) 平行弦法：兩圓弧的公切線平行于相鄰兩節(jié)點連線，兩圓弧的公切點顯然是的內(nèi)心（圖9）；3) 平均轉(zhuǎn)角法：兩圓弧的公切線平行于曲線在相鄰兩節(jié)點處切線交角的平分線（圖10）；2.三種方法的特點比較如下：1) 保凸條件：a) 垂

10、直平分線法：；b) 平行弦法：；c) 平均轉(zhuǎn)角法：。2) 兩圓半徑比（在保凸條件下）：a) 垂直平分線法：；b) 平行弦法：；c) 平均轉(zhuǎn)角法：。3.2.4 雙圓弧擬合算法8圖11，設(shè)節(jié)點A和B為在第個區(qū)間上的相鄰節(jié)點，經(jīng)坐標(biāo)變換后AB為橫軸，A為原點，垂直于AB為縱軸。有向直線和為擬合曲線在A和B上的有向切線。設(shè)C是直線和的交點，和分別是和與橫軸的夾角，逆時 針方向為正;，T為的內(nèi)心。圖11 雙圓弧曲線O2AB> 0CP> 0(b) 反向雙圓弧公切點軌跡弧O1gAgB-XY=-O2AB> 0CP< 0(a) 同向雙圓弧公切點軌跡弧O1gAgB-XYT如果C在橫軸的上方

11、，且和的方向分別與有向直線AC和CB的方向相同，那么，彼此相切且分別以和為切線的雙圓弧公切點軌跡是過三點A，T，B且內(nèi)部的圓弧，圖11（a）。如果的方向與CB的方向相反，則雙圓弧公切點軌跡是過A點和B點且弧度為（）在AB下方的圓弧，圖11（b）。在當(dāng)（保凸）時，雙圓弧同向，為C形雙圓弧。當(dāng)時，雙圓弧反向，為S 形雙圓弧。在局部坐標(biāo)系下，雙圓弧圓心和半徑可以統(tǒng)一地由下式給出：左圓半徑：, (3.5)圓心坐標(biāo)：， 。 (3.6)右圓半徑：， (3.7)圓心坐標(biāo)：， 。 (3.8)公切點的坐標(biāo)： (3.9) (3.10)其中；是左圓弧的圓心角，是右圓弧的圓心角；逆時針方向為正；正圓對應(yīng)正圓

12、心角，負(fù)圓對應(yīng)負(fù)圓心角，是AB的長度。3.2.5 誤差分析方法利用法向誤差判斷方法，步驟如下：（1）計算二次曲線在節(jié)點，間n等分的各分點坐標(biāo)。1）對于拋物線，在節(jié)點，間將橫軸值x等分為n份：，計算出拋物線上各對應(yīng)分點坐標(biāo)： r=1,2,n-1。2）對于橢圓、雙曲線，在節(jié)點，間將參數(shù)等分為n份：，計算出橢圓或雙曲線上各對應(yīng)分點坐標(biāo)： r=1,2,n-1（2）判斷分點所對應(yīng)的圓弧，過兩圓心的直線（必過公切點）方程： (3.11)其中：；。將節(jié)點坐標(biāo)代入式(3.11)左邊，將有（或） (3.12)將二次曲線上分點坐標(biāo)代入式(3.11)左邊計算值，如果，則點對應(yīng)第一段圓弧，否則對應(yīng)第二段圓弧。（3）計

13、算法向誤差對應(yīng)第一段圓弧的誤差公式是： , (3.13)其中是對應(yīng)第一段圓弧的最后一個分點號。對應(yīng)第二段圓弧的誤差公式是： , (3.14)（4）判斷最大誤差設(shè)如果（為指定的最大的允許誤差），則雙圓弧擬合結(jié)果為所求。如果，則對節(jié)點間用0.618法縮小區(qū)間，重新進(jìn)行雙圓弧擬合，直到滿足誤差要求。3.2.6 雙圓弧的最佳逼近算法如何利用雙圓弧樣條對平面二次曲線進(jìn)行逼近呢？簡單的辦法就是先將曲線插值出型值點，再對型值點進(jìn)行擬合27-29，這樣做的缺點是：增加了插值誤差；型值點過密會增加圓弧的段數(shù)。為了很好地解決這個問題，在本章中另外提出的一種方法是先將平面二次曲線進(jìn)行合適的分割，再用雙圓弧擬合，計算

14、逼近誤差，如果超過允許誤差，再對曲線進(jìn)行分割、擬合，直至滿足要求。這樣能夠得到在逼近誤差允許范圍內(nèi)圓弧段數(shù)最少的圓弧樣條。O1O2P1P2PC1C2圖12 分割后的平面二次曲線曲線曲線的分割是指在曲線的拐點和奇點處將曲線分成幾段，每一段分別處理。另外，為了算法的簡捷，要求分割后的曲線兩端點的切線角小于90º。如圖12所示曲線為分割后的平面二次曲線，在兩端點、之間無奇點、無拐點。要求過兩點、分別作圓弧、，與曲線相切于點、同時公切于點。已知P1、P2兩點坐標(biāo)，曲線最佳逼近算法為：（1）計算 、兩點的切線、在直角坐標(biāo)系下，任意二次曲線的方程為：過二次曲線上點的切線方程為：同理可以得出過的切

15、線方程。（2）確定公切點公切點的選擇直接影響到雙圓弧逼近曲線的光順性和逼近效果，可以證明雙圓弧公切點軌跡是一圓弧，考慮到雙圓弧樣條與平面二次曲線要取得最好的逼近效果，將公切點取作公切點圓弧與平面二次曲線的交點，這樣雙圓弧與被逼近的二次曲線段有5個交點（端點相切算兩個交點），因而基本上是最佳的雙圓弧逼近。11P1P2PST1T2S122C0圖13 確定公切點O如圖13所示，過、作切線、交點為，夾角為。作等腰三角形，使，則公切點圓弧必然與直線、相切?？梢宰C明公切點的軌跡為過、的圓弧25，其圓心及半徑分別為： 其中： ，當(dāng) 時成立。求公切點轉(zhuǎn)化為求公切點圓弧軌跡與二次曲線的交點，設(shè)交點坐標(biāo)為，則有：

16、解此二元二次方程組，即可求出交點P坐標(biāo)。下面證明公切點圓弧軌跡與二次曲線在、之間只有一個交點。從圖13可以看出，因此存在三種情況：a) ，則與曲線有一個交點，而與曲線無交點；b) ，則與曲線有交點，而與曲線無交點；c) 。由于對曲線進(jìn)行了分割，分割后的曲線段與圓弧應(yīng)是同向凸的，假設(shè)為上凸，如圖13所示，屬情況b)，在附近位于曲線的下方，在附近位于曲線的上方，因此與曲線必有唯一的交點。情況a)同理可證。情況c)是一種特殊情況，即為所求的雙圓弧。（3）求雙圓弧 、已知兩端點、及其斜率，另外又已知兩圓弧的公共切點，很容易找到兩圓弧的圓心及半徑-、。（4）誤差估計逼近的雙圓弧與原曲線的誤差計算，是算法

17、的重要組成部分。按曲線C的法線誤差計算，可以得出雙圓弧 、與原曲線的誤差、： 點在和之間 點在和之間如何找到、的最大值呢？直接求導(dǎo)很復(fù)雜，本章中提出一種區(qū)域逼近的方法求最大值。首先將區(qū)域十等分，求每點的誤差及其最大值，由于曲線是單峰的，所以真正的誤差一定在附近，將區(qū)域縮小至的鄰近區(qū)域，重復(fù)以上過程，直至兩次所得max的很接近，已經(jīng)逼近最大值。如果、超過允許誤差，則在點處將原曲線進(jìn)行分割，對超差段重新進(jìn)行雙圓弧逼近，直至滿足要求。3.2.7 圓錐曲線擬合算法處理流程 根據(jù)實際開發(fā)的要求，分別對三種曲線應(yīng)用上述的原理進(jìn)行了雙圓弧擬合處理，其實現(xiàn)方案圖14所示。圖14 圓錐曲線擬合算法流程圖3.2.

18、8 應(yīng)用實例 例如對于橢圓曲線的加工，由用戶輸入：G91 G02.2 X30 Y20 I0 J20 A0；XY圖15 橢圓的雙圓弧擬合后曲線3020該G代碼表示的含義是順時針加工橢圓，以橢圓的起點坐標(biāo)作為橢圓加工的相對坐標(biāo)系的原心，橢圓中心相對于起點的矢量坐標(biāo)為（0，20），橢圓加工的終點相對于起點的坐標(biāo)為（30，20），橢圓加工的長軸與橫軸的角度為0。通過橢圓的雙圓弧擬合，擬合后的曲線如圖15所示。擬合后的數(shù)據(jù)為：18%ellipse.GN0 M54 M50 M20 N5 G91 F100.000N10 S50 M3N15 G02 X-6.204 Y0.430 I0.000 J44.990N

19、20 G02 X-5.803 Y1.242 I5.649 J40.575N25 G02 X-1.407 Y0.439 I10.812 J37.135N30 G02 X-1.354 Y0.481 I11.607 J34.857N35 G02 X-1.664 Y0.676 I12.553 J33.294N40 G02 X-1.565 Y0.731 I13.144 J30.155N45 G02 X-1.897 Y1.031 I14.011 J28.028N50 G02 X-1.715 Y1.097 I14.150 J24.014N55 G02 X-1.627 Y1.223 I14.895 J21.5

20、16N60 G02 X-1.427 Y1.264 I14.494 J17.803N65 G02 X-0.340 Y0.334 I15.274 J15.866N70 G02 X-0.327 Y0.336 I15.099 J15.020N75 G02 X-1.228 Y1.414 I14.783 J14.072N80 G02 X-1.020 Y1.428 I14.061 J11.116N85 G02 X-0.233 Y0.373 I14.520 J9.327N90 G02 X-0.220 Y0.373 I14.320 J8.693N95 G02 X-0.261 Y0.474 I14.305 J8.

21、185N100 G02 X-0.241 Y0.474 I14.071 J7.449N105 G02 X-1.107 Y3.096 I13.447 J6.554N110 G02 X-0.361 Y3.084 I12.982 J3.084N115 G02 X0.611 Y3.995 I13.362 J-0.000N120 G02 X1.897 Y4.010 I15.366 J-4.814N125 G02 X0.647 Y0.923 I14.955 J-9.797N130 G02 X0.732 Y0.918 I15.533 J-11.638N135 G02 X0.989 Y1.085 I15.523

22、 J-13.169N140 G02 X1.122 Y1.068 I16.175 J-15.863N145 G02 X1.498 Y1.227 I15.984 J-17.978N150 G02 X1.694 Y1.180 I16.474 J-21.842N155 G02 X1.777 Y1.054 I15.714 J-24.476N160 G02 X1.952 Y0.982 I15.598 J-28.573N165 G02 X0.498 Y0.225 I14.094 J-30.526N170 G02 X0.508 Y0.220 I13.937 J-31.523N175 G02 X2.589 Y0

23、.979 I13.919 J-32.900N180 G02 X2.793 Y0.821 I12.531 J-37.469N185 G02 X0.706 Y0.173 I9.988 J-39.273N190 G02 X0.716 Y0.162 I9.456 J-40.190N195 G02 X4.546 Y0.730 I9.019 J-41.637N200 G02 X4.725 Y0.249 I4.725 J-44.748N205 G02 X6.204 Y-0.430 I0.000 J-44.990N210 G02 X5.803 Y-1.242 I-5.649 J-40.575N215G02 X

24、1.407 Y-0.439 I-10.812 J-37.135N220G02 X1.354 Y-0.481 I-11.607 J-34.857N225G02 X1.664 Y-0.676 I-12.553 J-33.294N230G02 X1.565 Y-0.731 I-13.144 J-30.155N235G02 X1.897 Y-1.031 I-14.011 J-28.028N240G02 X1.715 Y-1.097 I-14.150 J-24.014N245G02 X1.627 Y-1.223 I-14.895 J-21.516N250G02 X1.427 Y-1.264 I-14.4

25、94 J-17.803N255G02 X0.340 Y-0.334 I-15.274 J-15.866N260G02 X0.327 Y-0.336 I-15.099 J-15.020N265G02 X1.228 Y-1.414 I-14.783 J-14.072N270G02 X1.020 Y-1.428 I-14.061 J-11.116N275 G02 X0.233 Y-0.373 I-14.520 J-9.327N280 G02 X0.220 Y-0.373 I-14.320 J-8.693N285 G02 X0.261 Y-0.474 I-14.305 J-8.185N290 G02

26、X0.241 Y-0.474 I-14.071 J-7.449N295 G02 X1.107 Y-3.096 I-13.447 J-6.554N300 G02 X0.361 Y-3.084 I-12.982 J-3.084N305 S0 M3N310 M51 M21N315 M303.3 列表點曲線擬合算法的研究除了圓錐曲線以外，列表點曲線也是形狀數(shù)學(xué)描述的標(biāo)準(zhǔn)形式。其中，最常用的列表點描述方法有：1. 貝齊爾（Bezier）曲線；2. B樣條曲線；通過對這兩種方法的比較，找出適合列表曲線擬合的方法。3.3.1 貝齊爾曲線11 給定一組有序的數(shù)據(jù)點，這些點可以是從某個形狀上測量得到，也可以是設(shè)

27、計員給出。要求構(gòu)造一條曲線順序通過這些數(shù)據(jù)點，稱為對這些數(shù)據(jù)點進(jìn)行插值，所構(gòu)造的曲線稱為插值曲線。這些數(shù)據(jù)點若原來位于某曲線上，則稱該曲線為被插曲線。在某種情況下，測量所得或者設(shè)計員給出的數(shù)據(jù)點本身就很粗糙，要求構(gòu)造一條曲線嚴(yán)格通過給定的一組數(shù)據(jù)點就沒有什么意義。更合理的提法應(yīng)是，構(gòu)造一條曲線使之在某種意義下最為接近給定的數(shù)據(jù)點，稱之為對這些數(shù)據(jù)點進(jìn)行逼近，所構(gòu)造的曲線稱為逼近曲線。插值和逼近統(tǒng)稱為擬合。貝齊爾（Bezier）曲線以數(shù)據(jù)點表示，其伯恩斯坦（Bernstein）基表示式為：， （3.15）其中，基函數(shù) ，稱為伯恩斯坦基函數(shù)。用控制頂點定義的伯恩斯坦（Bernstein）基表示的貝齊爾曲線是一種獨(dú)特的參數(shù)樣條曲線，它不僅具有優(yōu)良的控制性質(zhì)，而且?guī)缀沃庇^，又驚人的簡單，使它特別適合于交互地設(shè)計形狀，但它不具有局部修改性質(zhì)且不能解決在描述復(fù)雜形狀時帶來的連接問題。3.3.2 B樣條曲線11B樣條理論早在1946年由舍恩伯格（Schoenberg）提出，但論文直到1967年才發(fā)表。1972年，德布爾（de Boor）與考克斯(Cox)分別獨(dú)立地給出B樣條計算的標(biāo)準(zhǔn)算法。但作為CAGD