李光耀，楊連喜，徐晨東

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

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

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

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

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

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

0 引 言

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

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

在此基礎(chǔ)上，本文提出了一種新的簡單的插值方法.首先運(yùn)用結(jié)式方法將有理曲線的參數(shù)形式轉(zhuǎn)化為隱式方程，再將含參數(shù)曲線在固定點(diǎn)處插值.通過求解相應(yīng)的方程組得到待定參數(shù)的值，進(jìn)而獲得一條多項式插值曲線來表示有理曲線.

1 預(yù)備知識

1.1 有理Bézier曲線的定義與性質(zhì)

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

n次有理Bézier曲線：

(1)

1.1.2 有理Bézier曲線性質(zhì)[5]

1.1.2.1 端點(diǎn)性質(zhì)

設(shè)ω0和ωn均不為零，則有理曲線在端點(diǎn)處的函數(shù)值及導(dǎo)數(shù)值為：

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，設(shè)2條曲線在端點(diǎn)處重合，即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個點(diǎn)組成2個點(diǎn)的集合A,B，則2條曲線之間離散的Hausdorff距離[6]為

1.3 結(jié)式方法[7]

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

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

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

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

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

本文采用結(jié)式方法將有理Bézier曲線的參數(shù)方程轉(zhuǎn)化為隱式方程.有關(guān)有理曲線的參數(shù)化方法詳見文獻(xiàn)[7-9].

2 構(gòu)造多項式曲線的方法

2.1 構(gòu)造參數(shù)多項式插值曲線

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

2.2 離散插值求解參數(shù)

i=1,2,…,n.

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

(2)

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

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

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

2.3 算法實現(xiàn)步驟

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

Step6Hausdorff距離最小時所對應(yīng)的一組參數(shù)λi,i=1,2,…,n，即為最優(yōu)參數(shù)值，確定此時的插值曲線,并對2條曲線進(jìn)行誤差分析.

3 數(shù)值實例

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

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

首先將該有理曲線轉(zhuǎn)化為隱式：

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

164249856x3+10265616x4+

377685504y+333891072xy-

41736384x2y-74803392y2-

63290880xy2+7911360x2y2+

10238976y3-154880y4，

有理曲線升階一次后的控制頂點(diǎn)為：

同時取有理曲線上的五等分點(diǎn)為：

其次，2組控制頂點(diǎn)線性組合后得到的新控制頂點(diǎn)為：

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

(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).

在五等分點(diǎn)處插值，確定一個方程組：

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

顯然，取第1組參數(shù)值時，插值曲線與原有理曲線的誤差最小為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設(shè)一條三次有理Bézier曲線的控制頂點(diǎn)和權(quán)因子分別為(0,0),(2,4),(4,6),(9,0)和1,3,2,1，將該曲線升階，按照本文插值有理曲線的方法確定含參數(shù)多項式曲線為：

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

根據(jù)限定條件，在四等分點(diǎn)處插值求解參數(shù)的值為

圖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曲線的控制頂點(diǎn)和權(quán)因子分別為(0,0),(2,5),(4,0),(6,5)和2,3,2,1.采用本文的參數(shù)多項式曲線插值有理曲線的方法確定含參數(shù)多項式曲線為

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

同理，通過四等分點(diǎn)處插值并根據(jù)限定條件確定參數(shù)值為

求出其對應(yīng)的離散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)，本文方法插值有理曲線有較好的效果，并且在升階次數(shù)相同時，較文獻(xiàn)[11]的方法更優(yōu).

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

4 結(jié) 語

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

[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] 陳發(fā)來.曲面隱式化新發(fā)展[J].中國科學(xué)技術(shù)大學(xué)學(xué)報,2014,44(5)： 345-361.

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

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

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

[9] 李彩云,朱春鋼,王仁宏.參數(shù)曲線的分段近似隱式化[J].高校應(yīng)用數(shù)學(xué)學(xué)報：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].浙江大學(xué)學(xué)報：理學(xué)版,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.

國家自然科學(xué)基金資助項目(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