一種基于離散插值的多項式曲線逼近有理曲線的方法

李光耀，楊連喜，徐晨東

(寧波大學 理學院， 浙江 寧波 315211)

一種基于離散插值的多項式曲線逼近有理曲線的方法

李光耀，楊連喜，徐晨東*

(寧波大學 理學院， 浙江 寧波 315211)

提出了一種用多項式曲線插值逼近有理曲線的方法.首先，構造一條含參數的多項式曲線，令其插值于有理曲線的一些固定點處，求解相應的方程得到待定參數的值，從而確定多項式插值曲線.然后，采用離散的Hausdorff距離計算插值曲線與有理曲線之間的誤差，典型數值算例表明,本文方法具有較好的可行性.

有理曲線；多項式曲線；插值；結式方法；Hausdorff距離

0 引 言

有理Bézier曲線在曲線設計中具有非常重要的作用，且在實踐中應用廣泛.由于有理曲線在進行求導等運算時計算量較大，通常用多項式曲線代替有理曲線.為此不少學者研究并提出了用多項式曲線逼近有理曲線的方法.在一些特定情況下，希望在多項式曲線與有理曲線具有較好擬合效果的基礎上盡可能多地通過有理曲線上的某些固定點，因此如何對有理Bézier曲線插值，使得插值曲線與有理曲線有較好的擬合效果，成為重要的課題.

之前學者們已經提出了多種逼近有理曲線的插值方法.例如1987年DEBOOR等[1]提出了高精度的幾何Hermite插值方法，在保持固定點處二階幾何連續的情況下，構造了一條三次插值曲線，并且提出了插值曲線存在的條件.2003年YANG[2]在空間Hermite插值的基礎上提出了一種用五次Bézier曲線或有理曲線逼近螺旋曲線的方法，并且逼近曲線在端點處滿足二階幾何連續.2006年FLOATER[3]提出了一種多項式插值曲線逼近有理曲線的新方法，通過在點的位置和切線方向插值，構造一條新的多項式插值曲線，實現了對任意次有理Bézier曲線的插值.2008年HUANG等[4]提出了用多項式曲線逼近有理曲線的2種簡單方法，一種是將有理曲線升階，用產生的控制頂點所定義的Bézier曲線來逼近有理曲線，第2種是取有理曲線上若干個等分點，以等分點作為控制頂點定義Bézier曲線用于逼近有理曲線.

在此基礎上，本文提出了一種新的簡單的插值方法.首先運用結式方法將有理曲線的參數形式轉化為隱式方程，再將含參數曲線在固定點處插值.通過求解相應的方程組得到待定參數的值，進而獲得一條多項式插值曲線來表示有理曲線.

1 預備知識

1.1 有理Bézier曲線的定義與性質

1.1.1 有理Bézier曲線定義[5]

n次有理Bézier曲線：

(1)

1.1.2 有理Bézier曲線性質[5]

1.1.2.1 端點性質

設ω0和ωn均不為零，則有理曲線在端點處的函數值及導數值為：

R(0)=R0,R(1)=Rn,

1.1.2.2 De Casteljau算法

其中,

1.2 Hausdorff距離

對于給定的2條曲線P(t),R(s),t0≤t≤t1,s0≤s≤s1，設2條曲線在端點處重合，即P(t0)=R(s0),P(t1)=R(s1)，則2條曲線的Hausdorff距離[6]定義為

dH(P(t),R(s))=

max(d1(P(t),R(s)),d2(P(t),R(s))),

其中,

本文在估計誤差時采用的是離散的Hausdorff距離，分別取2條曲線上的N個點組成2個點的集合A,B，則2條曲線之間離散的Hausdorff距離[6]為

1.3 結式方法[7]

設f(x),g(x)是2個次數分別為m,n的單變量多項式：

f(x)=amxm+…+a1x+a0,

g(x)=bnxn+…+b1x+b0,

其中,am≠0,bn≠0，則m+n階行列式：

稱為多項式f(x)、g(x)的結式，記作R(f,g,x).

本文采用結式方法將有理Bézier曲線的參數方程轉化為隱式方程.有關有理曲線的參數化方法詳見文獻[7-9].

2 構造多項式曲線的方法

2.1 構造參數多項式插值曲線

含參數多項式曲線表示有理曲線時，保持2條曲線在端點處滿足G1連續，因此組合后控制頂點在兩端點處不變，并且滿足端點處的切線方向相同,故線性組合后的控制頂點為：

2.2 離散插值求解參數

i=1,2,…,n.

代入有理曲線R(t)的隱式方程，得到方程組：

(2)

插值確定參數λi的過程，即為該方程組的求解過程.

對于方程組(2)，有理曲線次數越高就越復雜，計算量也大大增加；并且該方程組解的情況復雜多樣，甚至存在無解的情況，因此該方法具有一定的局限性.本文只考慮有解的情況.

由于該方法選擇的參數值所對應的Hausdorff距離最小，并且此時Hausdorff距離即為插值曲線和原有理曲線之間的誤差，理論上此時得到的插值曲線能更好地表示原有理曲線，該求解過程在限定條件λi>0(i=1,2,…,n)下，計算簡便.

2.3 算法實現步驟

Step1利用結式方法將n次有理Bézier曲線R(t)的參數形式轉化為隱式：F(x,y)=0.

Step6Hausdorff距離最小時所對應的一組參數λi,i=1,2,…,n，即為最優參數值，確定此時的插值曲線,并對2條曲線進行誤差分析.

3 數值實例

用實例進一步驗證多項式曲線插值有理Bézier曲線方法的可行性.分別取曲線上2 000個點作為集合A和B，采用離散的Haussdorff距離進行誤差計算.最后，對多項式插值曲線和有理曲線進行誤差分析.

例1設四次對稱有理Bézier曲線的控制頂點和權值為(0,0),(1,5),(4,9),(7,5),(8,0)和2,3,2,3,2， 則該有理Bézier曲線的表達式為

首先將該有理曲線轉化為隱式：

f(x,y)=-1888427520x+893052864x2-

164249856x3+10265616x4+

377685504y+333891072xy-

41736384x2y-74803392y2-

63290880xy2+7911360x2y2+

10238976y3-154880y4，

有理曲線升階一次后的控制頂點為：

同時取有理曲線上的五等分點為：

其次，2組控制頂點線性組合后得到的新控制頂點為：

因此，定義一條含參數多項式曲線：

(8t3+(5(t-1)t(10136t2-23536t-

21336t3+(2t-1)(4686(λ1+λ1(t-1)t)+

5201λ2(t-1)t)))/5467,

(10(t-1)t(49(t-1)t(612+169λ2)-

11715(1+3(t-1)t)λ1))/5467).

在五等分點處插值，確定一個方程組：

根據上述方法，通過限制條件解該方程組，可得到參數λ1和λ2的值：

顯然，取第1組參數值時，插值曲線與原有理曲線的誤差最小為0.010 574 2.圖1和2分別給出了插值曲線和原有理曲線以及曲率的對比.

圖1 有理曲線與插值曲線Fig.1 The rational curve and the interpolation curve實線為有理曲線，虛線為插值曲線.Solid line： rational curve,dashed： interpolation curve.

圖2 有理曲線與插值曲線曲率Fig.2 Curvature between rational curve and interpolation curve

例2設一條三次有理Bézier曲線的控制頂點和權因子分別為(0,0),(2,4),(4,6),(9,0)和1,3,2,1，將該曲線升階，按照本文插值有理曲線的方法確定含參數多項式曲線為：

2t(7(t-1)(15+2λ2)-85λ3))).

根據限定條件，在四等分點處插值求解參數的值為

圖3 有理曲線與插值曲線Fig.3 The rational curve and the interpolation curve實線為有理曲線，虛線插值曲線.Solid line： rational curve,dashed： interpolation curve.

圖4 有理曲線與插值曲線曲率Fig.4 Curvature between rational curve and interpolation curve

例3三次有理Bézier曲線的控制頂點和權因子分別為(0,0),(2,5),(4,0),(6,5)和2,3,2,1.采用本文的參數多項式曲線插值有理曲線的方法確定含參數多項式曲線為

t(t-8))+4(t-1)(7λ2(t-1)+90tλ3))).

同理，通過四等分點處插值并根據限定條件確定參數值為

求出其對應的離散Hausdorff距離分別為：

圖5 有理曲線與插值曲線Fig.5 The rational curve and the interpolation curve

圖6 有理曲線與插值曲線曲率Fig.6 Curvature between rational curve and interpolation curve

表1 上述例子的誤差與已有方法的比較

Table 1 The error analysis of case 1 to 3

由上述3個例子及誤差對比可知(見表1)，本文方法插值有理曲線有較好的效果，并且在升階次數相同時，較文獻[11]的方法更優.

本文只是提供了一種插值思路，其精度與文獻[10]相同.

4 結 語

研究了利用含參數的多項式曲線插值有理Bézier曲線的方法,該方法不僅具有較好的效果,而且在應用中可根據實際需要使得插值曲線通過有理曲線上的某些固定點.實例分析證實了該方法的有效性,具有實際意義.但該方法也存在一定的局限性,比如在求解非線性方程組時可能含有無解的情況,并且當有理曲線次數較高或升階次數較多時,計算量較大等.另外,只考慮了平面曲線的插值,實際上該插值方法還可推廣至空間有理曲線.

[1] DEBOOR C,H?LLIG K,SABIN M.High accuracy geometric Hermite interpolation[J].ComputerAidedGeometricDesign,1987,4(4)： 169-178.

[2] YANG X N.High accuracy approximation of helices by quintic curves[J].ComputerAidedGeometricDesign,2003,20： 303-317.

[3] FLOATER M S.High order approximation of rational curves by polynomial curves[J].ComputerAidedGeometricDesign,2006,23(8)： 621-628.

[4] HUANG Y D,SU H M,LIN H W.A simple method for approximating rational Bézier curve using Bézier curves[J].ComputerAidedGeometricDesign,2008,25(8)： 697-699.

[5] FARIN G.CurvesandSurfacesforComputerAidedGeometricDesign,APracticalGuide[M].5th ed. San Diego： Academic Press,2002.

[6] CHEN J,WANG G J.A new type of the generalized Bézier curves [J].AppliedMathematics：AJournalofChineseUniversities(SerB),2011(1)： 47-56.

[7] 陳發來.曲面隱式化新發展[J].中國科學技術大學學報,2014,44(5)： 345-361.

CHEN F L.Recent advances on surface implicitization[J].JournalofUniversityofScienceandTechnologyofChina,2014,44(5)： 345-361.

[8] 陳發來.有理曲線的近似隱式化表示[J].計算機學報,1998,21(9)： 855-859.

CHEN F L.The implicitization of ration curves[J].ChineseJournalofComputers,1998,21(9)： 855-819.

[9] 李彩云,朱春鋼,王仁宏.參數曲線的分段近似隱式化[J].高校應用數學學報：A輯,2010,25(2)： 202-210.

LI C Y, ZHU C G, WANG R H. Piecewise approximate implicitization of parametric curves[J].AppliedMathematics：AJournalofChineseUniversities,2010,25(2)： 202-210.

[10] FLOATER M S.High order approximation of rational curves by polynomial curves[J].ComputerAidedGeometricDesign,2006,23(8)： 621-628.

[11] 楊連喜,徐晨東.一種用多項式曲線逼近有理曲線的新方法[J].浙江大學學報：理學版,2015,42(1)： 21-27.

YANG L X,XU C D.New method of parametric polynomial curves approximation rational curves[J].JournalofZhejiangUniversity：ScienceEdition,2015,42(1)： 21-27

LI Guangyao,YANG Lianxi,XU Chendong

(FacultyofScience,NingboUniversity,Ningbo315211,ZhejiangProvince,China)

Amethodonpolynomialcurveapproximationofrationalcurvesbasedonthediscreteinterpolation.Journal of Zhejiang University (Science Edition)， 2017, 44(6)： 705-710

This paper presents a method for interpolating rational curves with polynomial curves. Firstly, we construct a polynomial curve with some undetermined parameters, and let this polynomial curve interpolate the given rational curve at some fixed points. By solving the corresponding equation of undetermined parameters, a suitable polynomial interpolation curve is formed. The error between the rational curve and the polynomial interpolation curve is estimated based on discrete Hausdorff distance. Some typical numerical examples illustrate the effectiveness of this method.

rational curve; polynomial curve; interpolation; resultant method; Hausdorff distance

2016-05-25.

國家自然科學基金資助項目(11101230,11371209).

李光耀(1991-),ORCID： http： //orcid.org/0000-0001-6205-4803，男，碩士研究生，主要從事計算幾何研究.

*通信作者，ORCID： http： //orcid.org/0000-0002-2759-4123,E-mail： xuchendong@nbu.edu.cn.

10.3785/j.issn.1008-9497.2017.06.009

O 241.5; TP 391

A

1008-9497(2017)06-705-06