一种基于离散插值的多项式曲线逼近有理曲线的方法

李光耀，杨连喜，徐晨东

(宁波大学 理学院， 浙江 宁波 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