搜索
三次样条曲线算法的改进及Ｊａｖａ语言实现［摘要］针对常规三次样条插值存在的不足，本文提出了结合微分弦长积累的改进型算法并给出了程序。该算法使得各给定的相邻离散点区间段能保证至少二阶导数连续，从而大大地提高了拟合曲线的光滑度。［关键词］样条曲线，均方曲率，积累弦长，边界条件，Java1引言美国数学家I.J.Schoenberg于1946年提出的B样条曲线，现在已得到了广泛的应用。在实际应用中，比较多的是采用3次B样条曲线。在文献[1]中给出了平面坐标系下的三次B样条插值曲线的方程式三次B样条插值在各种可能的插值中使得均方曲率为最小，即在一定意义下最为“光顺”。它可以保证各相邻离散样点区间段直到二阶导数连续，因而光滑度较高。所以该插值法也是在工程应用中使用得最多的一种插值方法。但在使用中我们发现，三次B样条插值也存在着一大缺陷，它不是局部化的，每个节点都会影响到全局，虽然影响是随着远离该点而衰退的，但是由于存在着误差的远距离扩散，使得样条插值也会有“多余”的波动，特别是在间距不均匀以及其它一些特殊场合更为显著[1]。根据三次B样条插值函数的基本要求，函数变量必须单调递增(或减)，这对于封闭性拟合曲线来说，难以实现。本文我们设想了采用普通三次B样条插值与微分弦长积累相结合的办法，即各相邻离散样点弦长积累，并以各样点积累弦长为自变量构造样点弦长函数，再与三次样条插值函数合并，寻求封闭样条曲线的最优拟合的办法。结果将该混合算法与原三次样条算法的求解过程进行比较和分析后，表明该算法能很好地解决上述样条插值的不足。2微分弦长累积原理根据输入的离散样点，首先求出相邻点的积累弦长si和积累弦长差hi，再分别将离散点xi坐标的值(yi坐标同理)和si及hi代入三次B样条曲线函数，根据导数连续的性质和边界条件构造矩阵，利用高斯消元法求出Mxi(或Myi)。高斯消元法的基本思想是用逐次消去一个未知数（矩阵元素）的办法把原来的矩阵化为等价的（即具有相同解答的）三角形矩阵，再利用回代法求出该等价三角形矩阵的各未知数（矩阵变量），从而得出X关于弦长s的三次B样条函数X(s)，(Y(s)同理)，最后根据样条函数X(s)和Y(s),近似地将该拟合曲线分成若干小直线段，并将其绘出，最终得到所需要的三次B样条拟合曲线。4Java语言实现Java是面向对象的、支持多线程的、体系结构独立的解释型动态语言，具有高度的安全性、可移植性和代码可重用性，具有很高的运行效率，近年来Java已成为最受欢迎的面向对象程序设计语言之一，是目前软件中极为健壮的编程语言。(1)部分源代码：importjava.applet.*;importjava.awt.*;publicclassSplineextendsApplet{publicSpline(){......}publicvoiddrawSpline(Graphicsg){......for(i=0;iN-1;i++){nn=(s[i+1]-s[i])/20;for(j=1;j21;j++){a=s[i]+j*nn;x=Math.pow(s[i+1]-(a-nn),3)*Mx[i]/(6*hx[i])+Math.pow(a-nn-s[i],3)*Mx[i+1]/(6*hx[i])+(s[i+1]-(a-nn))*(pointx[i]/hx[i]-hx[i]*Mx[i]/6)+(a-nn-s[i])*(pointx[i+1]/hx[i]-hx[i]*Mx[i+1]/6);......g.drawLine((int)x,(int)y,(int)xx,(int)yy);g.drawString(“边界拟合线”+u,(int)pointx[N-2],(int)pointy[N-2]);}}}(2)辅助代码有如下主要成员变量:intN;//边界样点总数doubles[]=newdouble[N];//边界样点从起点至终点的累积弧长doublepointx[]=newdouble[N];doublepointy[]=newdouble[N];//边界样点坐标doubleMx[]=newdouble[N];doubleMy[]=newdouble[N];//M[i]为三次样条函数在第(i+1)点的二阶导数值doublehx[]=newdouble[N-1];doublehy[]=newdouble[N-1];//将所输入的样点按纵坐标从大到小划分区段的各段间距有如下主要内部方法:publicvoiddesign()//确定各初始点的坐标publicvoiddrawMyLine(Graphicsg,doublestartx,doublestarty,doubleangle,doubledepth)publicvoidsplinex(doubletx[],doublets[])//三次B样条微分弦长累积插值曲线横坐标函数publicvoidspliney(doublety[],doublets[])//三次B样条微分弦长累积插值曲线纵坐标函数publicvoidarc(doublex[],doubley[])//累积弧长函数publicvoiddrawSpline(Graphicsg)//画边界拟合曲线publicvoidpaint(Graphicsg)//图形中心定位及其刷新5算例分析通过该表的数据结果，不难看出，所取样点个数越大，样条函数所带来的计算误差也就越小，从而拟合的样条曲线越接近于实际。当然并不是说样点个数越大越好，太大会使计算机程序运行速度减慢，同时也增加了获取样点时的劳动强度。这个方法的优点是，它采用了曲线自身的内在坐标，因而不依赖于曲线的形状走向。它不仅对于封闭曲线，而且对于更一般的如相交(如图2(c))也适用，因此有很大的通用性。通常工程绘图用的曲线板所含的几何信息，用约30个节点值就足以表达。这个方法显然很容易推广到空间曲线的插值。该改进型算法已应用于某铜矿计算机辅助设计软件中，取得了很好的应用效果(如图3所示，a为改进前，b为改进后的效果)。在将探矿取得的数据输入后，原来只能用直线的形式定矿体边界的工作，现在用拟合曲线的形式表现出来，极大地提高了工作效率和矿体储量精确度，大大地节约了工程技术人员的劳动强度，更充分地利用了国家有限的矿物资源。6结语三次样条插值是目前在工程应用中使用得最为广泛的一种插值方法。本文介绍了常规三次样条插值与微分弦长累加的具体组合过程，改进了常规三次样条插值的算法，使得各相邻离散点区间段能保证至少二阶导数连续，从而大大地提高了拟合曲线的光滑度，同时也带来了程序内在的高度稳定性。实践证明，该组合算法，大大地完善了原三次样条插值算法，且对于非封闭性的样条插值问题也具有同样的效果，因而有很大的通用性。参考文献：[1]徐萃薇.计算方法引论[M].北京：高等教育出版社，2001[2]孔祥庆.空间曲线的弧长一般求长法[Ｊ].南方冶金学院学报,2001,(4):290-292[3]张新建、黄建华.Wm2空间中样条插值算子与最佳逼近算子的一致性[Ｊ].计算数学,2001,(4)：385-392[4]刘建国、赵林明.B样条曲线端点的一种处理方法及应用.电脑开发与应用.1999,(4)（注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文）