三次樣條曲線算法的改進(jìn)及Java語言實(shí)現(xiàn)

1、三次樣條曲線算法的改進(jìn)及語言實(shí)現(xiàn)摘要針對常規(guī)三次樣條插值存在的不足，本文提出了結(jié)合微分弦長積累的改進(jìn)型算法并給出了程序。該算法使得各給定的相鄰離散點(diǎn)區(qū)間段能保證至少二階導(dǎo)數(shù)連續(xù)，從而大大地提高了擬合曲線的光滑度。關(guān)鍵詞樣條曲線，均方曲率，積累弦長，邊界條件，Java1 引 言美國數(shù)學(xué)家I.J.Schoenberg于1946年提出的B樣條曲線，現(xiàn)在已得到了廣泛的應(yīng)用。在實(shí)際應(yīng)用中，比較多的是采用3次B樣條曲線。在文獻(xiàn)1中給出了平面坐標(biāo)系下的三次B樣條插值曲線的方程式三次B樣條插值在各種可能的插值中使得均方曲率為最小，即在一定意義下最為“光順”。它可以保證各相鄰離散樣點(diǎn)區(qū)間段直到二階導(dǎo)數(shù)連續(xù)，因而

2、光滑度較高。所以該插值法也是在工程應(yīng)用中使用得最多的一種插值方法。但在使用中我們發(fā)現(xiàn)，三次B樣條插值也存在著一大缺陷，它不是局部化的，每個節(jié)點(diǎn)都會影響到全局，雖然影響是隨著遠(yuǎn)離該點(diǎn)而衰退的，但是由于存在著誤差的遠(yuǎn)距離擴(kuò)散，使得樣條插值也會有“多余”的波動，特別是在間距不均勻以及其它一些特殊場合更為顯著1。根據(jù)三次B樣條插值函數(shù)的基本要求，函數(shù)變量必須單調(diào)遞增(或減)，這對于封閉性擬合曲線來說，難以實(shí)現(xiàn)。本文我們設(shè)想了采用普通三次B樣條插值與微分弦長積累相結(jié)合的辦法，即各相鄰離散樣點(diǎn)弦長積累，并以各樣點(diǎn)積累弦長為自變量構(gòu)造樣點(diǎn)弦長函數(shù)，再與三次樣條插值函數(shù)合并，尋求封閉樣條曲線的最優(yōu)擬合的辦法。

3、結(jié)果將該混合算法與原三次樣條算法的求解過程進(jìn)行比較和分析后，表明該算法能很好地解決上述樣條插值的不足。2 微分弦長累積原理根據(jù)輸入的離散樣點(diǎn)，首先求出相鄰點(diǎn)的積累弦長si和積累弦長差hi，再分別將離散點(diǎn)xi坐標(biāo)的值(yi坐標(biāo)同理)和si及hi代入三次B樣條曲線函數(shù)，根據(jù)導(dǎo)數(shù)連續(xù)的性質(zhì)和邊界條件構(gòu)造矩陣，利用高斯消元法求出Mxi(或Myi)。高斯消元法的基本思想是用逐次消去一個未知數(shù)（矩陣元素）的辦法把原來的矩陣化為等價的（即具有相同解答的）三角形矩陣，再利用回代法求出該等價三角形矩陣的各未知數(shù)（矩陣變量），從而得出X關(guān)于弦長s的三次B樣條函數(shù)X(s)， (Y(s)同理)，最后根據(jù)樣條函數(shù)X(s

4、)和Y(s),近似地將該擬合曲線分成若干小直線段，并將其繪出，最終得到所需要的三次B樣條擬合曲線。4 Java語言實(shí)現(xiàn)Java是面向?qū)ο蟮?、支持多線程的、體系結(jié)構(gòu)獨(dú)立的解釋型動態(tài)語言，具有高度的安全性、可移植性和代碼可重用性，具有很高的運(yùn)行效率，近年來Java已成為最受歡迎的面向?qū)ο蟪绦蛟O(shè)計語言之一，是目前軟件中極為健壯的編程語言。(1) 部分源代碼：import java.applet.*;import java.awt.*;public class Spline extends Appletpublic Spline(). . public void drawSpline(Graphics

5、 g). .for(i=0;iN-1;i+)nn=(si+1-si)/20;for(j=1;j21;j+)a=si+j*nn; x=Math.pow(si+1-(a-nn),3)*Mxi/(6*hxi)+Math.pow(a-nn-si,3)*Mxi+1/(6*hxi)+(si+1-(a-nn)*(pointxi/hxi-hxi*Mxi/6)+(a-nn-si)*(pointxi+1/hxi-hxi*Mxi+1/6);. .g.drawLine(int)x,(int)y,(int)xx,(int)yy);g.drawString(“邊界擬合線”+u,(int)pointxN-2,(int)po

6、intyN-2); (2) 輔助代碼有如下主要成員變量:int N;/邊界樣點(diǎn)總數(shù)double s=new doubleN; /邊界樣點(diǎn)從起點(diǎn)至終點(diǎn)的累積弧長double pointx=new doubleN;double pointy=new doubleN;/邊界樣點(diǎn)坐標(biāo)double Mx=new doubleN; double My=new doubleN;/Mi為三次樣條函數(shù)在第(i+1)點(diǎn)的二階導(dǎo)數(shù)值double hx=new doubleN-1; double hy=new doubleN-1; /將所輸入的樣點(diǎn)按縱坐標(biāo)從大到小劃分區(qū)段的各段間距有如下主要內(nèi)部方法:public v

7、oid design() /確定各初始點(diǎn)的坐標(biāo)public void drawMyLine(Graphics g ,double startx,double starty,double angle,double depth)public void splinex(double tx ,double ts ) /三次B樣條微分弦長累積插值曲線橫坐標(biāo)函數(shù)public void spliney(double ty ,double ts ) /三次B樣條微分弦長累積插值曲線縱坐標(biāo)函數(shù)public void arc(double x ,double y ) /累積弧長函數(shù)public void draw

8、Spline(Graphics g) /畫邊界擬合曲線public void paint(Graphics g)/圖形中心定位及其刷新5 算例分析通過該表的數(shù)據(jù)結(jié)果，不難看出，所取樣點(diǎn)個數(shù)越大，樣條函數(shù)所帶來的計算誤差也就越小，從而擬合的樣條曲線越接近于實(shí)際。當(dāng)然并不是說樣點(diǎn)個數(shù)越大越好，太大會使計算機(jī)程序運(yùn)行速度減慢，同時也增加了獲取樣點(diǎn)時的勞動強(qiáng)度。這個方法的優(yōu)點(diǎn)是，它采用了曲線自身的內(nèi)在坐標(biāo)，因而不依賴于曲線的形狀走向。它不僅對于封閉曲線，而且對于更一般的如相交(如圖2(c)也適用，因此有很大的通用性。通常工程繪圖用的曲線板所含的幾何信息，用約30個節(jié)點(diǎn)值就足以表達(dá)。這個方法顯然很容易推

9、廣到空間曲線的插值。該改進(jìn)型算法已應(yīng)用于某銅礦計算機(jī)輔助設(shè)計軟件中，取得了很好的應(yīng)用效果(如圖3所示，a為改進(jìn)前，b為改進(jìn)后的效果)。在將探礦取得的數(shù)據(jù)輸入后，原來只能用直線的形式定礦體邊界的工作，現(xiàn)在用擬合曲線的形式表現(xiàn)出來，極大地提高了工作效率和礦體儲量精確度，大大地節(jié)約了工程技術(shù)人員的勞動強(qiáng)度，更充分地利用了國家有限的礦物資源。6 結(jié) 語三次樣條插值是目前在工程應(yīng)用中使用得最為廣泛的一種插值方法。本文介紹了常規(guī)三次樣條插值與微分弦長累加的具體組合過程，改進(jìn)了常規(guī)三次樣條插值的算法，使得各相鄰離散點(diǎn)區(qū)間段能保證至少二階導(dǎo)數(shù)連續(xù)，從而大大地提高了擬合曲線的光滑度，同時也帶來了程序內(nèi)在的高度穩(wěn)定性。實(shí)踐證明，該組合算法，大大地完善了原三次樣條插值算法，且對于非封閉性的樣條插值問題也具有同樣的效果，因而有很大的通用性。參考文獻(xiàn)： 1 徐萃薇.計算方法引論M.北京：高等教育出版社，20012 孔祥慶.空間曲線的弧長一般求長法.南方冶金學(xué)院學(xué)報,20