三次样条曲线生成算法研究摘要

1、三次样条曲线的生成算法本文由天空乐园河南自考网整理分享摘要三次样条函数曲线具有的最高多项式插值精度是三次多项式函数，对其进行推广构造的三次参数样条曲线应至少具有同样的插值精度。本文讨论了构造三次参数样条曲线中节点选取问题，相邻两节点之间的跨度规范化为1，提出了构造2GC三次参数样条曲线的新方法。文中首先讨论了 2GC三次参数样条曲线需满足的连续性方程，然后讨论了平面有序五点确定一 组三次多项式函数曲线和平面有序六点唯一确定一条三次多项式函数曲线。在此基础上，提出了为给定数据点选取节点值的新方法。新方法构造的2GC三次参数样条曲线具有三次多项式函数的插值精度。最后以具体数据点对新方法和已有的四种

2、节点选取方法构造的插值曲线的精度做了比较。关键词：三次样条曲线；曲线拟合；计算机图形学自1946年美国数学家I. J. Schoenberg提出样条函数1以来，样条函数以其 构造简单、易于计算又有很好的力学背景等特点而被广泛用于科学计算、工程设计和计算机辅助设计等领域，成为最重要的曲线和曲面构造方法之一。 在样条 函数的应用中，三次样条函数由于具有极小模性质、最佳逼近性质和很强的收敛性2,3,4等而成为最主要的方法应用于构造插值曲线和曲面。用样条函数方法构造三次插值曲线，曲线的连续性基本可满足实际应用的要 求。当曲线的端点条件确定之后，曲线的精度和形状是由曲线需满足的连续性方 程唯一决定的。在

3、小挠度的情况下，插值曲线的精度和形状都是非常理想的。对大挠度曲线和任意平面数据点，则需推广三次样条函数方法构造三次参数样条曲 线，此时需知道每个数据点处的参数值（节点值）。在实际应用中，这些参数值一般是无法预先给定的，所以构造三次参数样条曲线的第一步是对给定数据点 参数化，即为每个数据点指定节点值。如果指定的节点值是精确的，给定适当的 端点条件，可使构造的插值曲线的代数精度达到三次参数多项式。构造三次参数 样条曲线，当曲线的端点条件确定之后，能够决定曲线插值精度的量只有节点。 因此构造三次参数样条曲线的关键是如何选择节点。目前常用的节点选取方法有4种，均匀参数化法、累加弦长参数化法、向心参数化

4、法 5和修正弦长参数化法 。这些方法虽然在实际中得到了较为广泛的应用，但从逼近的角度看，它们 的插值精度较低，其插值多项式的最高精度是线性的。最近一个确定节点的方法7具有二次多项式插值精度，如果用来构造三次参数样条曲线，这个精度也是较低的。三次样条函数曲线具有的最高多项式插值精度是三次多项式函数，对其进行推广构造的三次参数样条曲线应至少具有同样的插值精度。从这一目标出发，本文讨论了构造三次参数样条曲线中节点选取问题，相邻两节点之间的跨度规范化 为1,提出了构造2GC三次参数样条曲线的新方法。文中首先讨论了2GC次参数样条曲线需满足的连续性方程，然后讨论了平面有序五点确定一组三次多 项式函数曲线

5、和平面有序六点唯一确定一条三次多项式函数曲线。在此基础上，提出了为给定数据点选取节点值的新方法。新方法构造的2GC三次参数样条曲线具有三次多项式函数的插值精度。最后以具体数据点对新方法和已有的四平面自由曲线种节点选取方法构造的插值曲线的精度做了比较。不能用一个标准代数方程精确表示。实际中应用很多，如 轮船船身放样。将放样过程抽象为：平面上给定若干点（型值点），找一个代数方程，逼近或 插值上述型值点。理论上，n个点，可以找到一个n-1次多项式来逼近，但n太大时，多项式 次数太高，计算复杂，难以控制。工程上，降低次数，且分段定义。样条函数自提出以来，以其构造简单，易于计算，及很好的力学背景等特点

6、被广泛用于科学计算，工程设计和计算机辅助设计等领域，从而成为最重要的曲 线和曲面构造方法之一。三次样条曲线在使用中存在局限性， 且表示方法缺乏几何不变性。即当平面 直角坐标系中得型值点发生旋转等几何变形时，其曲线的形状也发生变形，严重时甚至不能保证满足X1<X2<X3<Xn的条件，对表现曲线的几何形状极为不便； 在使用autoCAD中spline命令绘制样条曲线时，可能导致各型值点的横坐标也 不能满足X1<X2<X3<Xn的条件。为了解决这些问题，一些学者运用向心参数法在周期性三次样条曲线拟合控制多边形时，取得了很小的偏差；基于累加弦长的三次参数样条曲线插值

7、在数控系统中取得了较好的效果，但是以累加弦长为参数的三次参数样条曲线插值和基样条的函数插值在各分段曲线两端曲率的符号相 同的情况下都有可能产生这段曲线上的拐点，造成曲线不光顾。因此一些准测提 出检查多余的拐点，YE J等人修正了 Kjellander的方法，并从累加弦长参数化和 光顾函数两方面消除了三次参数样条的震荡和回折。在曲线拟合中，插值过程可具体使用线性（liner）插值，三系样条（spline） 插值，立方（cubic）插值等方法，在曲线插值法中最常用的是线性插值法，它是估 计2个主干点之间数值的最简单，最易实现的方法，但采用线性插值法会有以下 缺点：1曲线不能显示连接主干点间的凸状弧

8、线；2从曲线导出远期曲线时会形 成人为的“尖头”。因此，通常采用样条法来构造曲线，它通过构造多项式（1个或1组不同阶 多项式）来形成1条把所有主干点连接起来的平滑曲线，一般常选择3次曲线（根 据3次插值样条函数所得的曲线）进行拟合。3次样条曲线具有良好的数学特征， 而且用3次曲线去拟合时，其结果要比线性插值估计更接近于工程实际情况，但是在工程应用中，我们利用三次样条插值方法，对相同的控制点，只可以得到1条光滑曲线，如果我们想基于相同的控制点，得到多条不同曲线，依靠传统算法， 是无法实现的，这就限制了三次样条在工程中，特别是印刷领域中得应用。在印刷领域，特别市在工艺前端，传统的方法是利用曲线进行

9、分色操作，由于色彩的特殊性，即人眼对色彩的感觉不尽相同。 如果只有1条色度曲线，那么 工艺人员就无法对色彩效果进行有效的对比。因此印刷工艺的特殊性要求能够根据相同控制点，得出多条曲线，实现不同的印刷色彩效果，从中选出最佳的色度 曲线。在这一点上，传统的方法是通过修改基本的控制点， 生成新的控制曲线实 行，本文提出改进的3次样条算法，实现了在相同的控制点上，生成了曲线不同 的新曲线。增加了生成曲线的条数，从而使得印刷前端的工艺操作人员， 对控制 图像的色度曲线有更多的选择。三次参数样条曲线的构造设平面上给定了 n个数据点Pi = h2,3r儿目标是构造一条对n个数据点插值的三次参数样条曲线 P。

10、设ti（待定）是与i P相对应的节点，令此小=心-"、则区间J el2丿-1上的 三次参数曲线Pi（t）可定义如下：叽血ry几a0= (z-l)r（0 =珂（丁+ 0（厂1怡+£十/（"“I也 *1坷+|其中0o(f) = (F -+ 1)0o(O = r(3-2f)为0,1区间上的三次埃尔米特基函数, t ()应满足的连续性方程是6,8:也一=如' 出为节点ti处的切矢。P方I + 2(% + 紅)M / + hM F+2,3,.yfi 一(2.2)其中；令;2.3)则(2.2)可写成如下形式:(2.4)其中;/二 2,3,人一11 tCCT寸宀S亡W+

11、T)如果Si给定，则可得到(2.4)中的Ni,i=1,2,n,由NN(2.5知，对i =1,2,n-1,(2.1)可写成如下形式:饷訴2眷仔匕5(讥(2.6)其中0w sw 1 o显然，由(2.6)定义的样条曲线是Gr 连续的。方程组(2.4)中有n - 2方程, n个未知量，解方程组需增加两个端点条件，方法如下：(1)对封闭或周期曲线N、二S1 S =九+几15所以,片-1片爲(1 片汕+(1片)(1-旳)C"3由啤U和y得(2)两端点处的二阶导数为零由山2£ +亠他=30-申®1-勺丄 N- + 2 洱此时，对(2.4)中的i =2和n-1，相应的方程为S,-

12、S N 2L +y +A；, = Ci. i = 2® 占气(I gj(1-»)(1)I - /I-, + -A；. + 丄-竹二 C九此Wn) 1=17。所求方程中的未知量为M/m心八凡_凡/(1 一讣给定端点切向条件M1和Mn ,NJ $ = FN” /（ 1 7”_ J =打（2.7）其中F1和F2的值确定将在第四节中讨论。设耳，7=12打-1上”+1' + 2,，是给定数点中连续五点，与pj相 对应的节点是t j（待定）。为讨论方便，我们做如下变换。设UK和£；不在一条 直线上，把坐标变换¥= F - -F： H-x+ -工一：（I -竹

13、） dd V 一 1'X 一 TU =i ； "1 （工-A； ） + 4_丄（V- V ）其中d =（ _兀（】匸一儿“（兀_ X）和蔘数变换（32）分别施加到Pi和ti。则在OVW坐标系中pmhna,i+心2.的坐标为匕产八2产（0）、岸=（02）、岸*b （1,0）和匕产（片心八%=-, 0心1+相应的节点值分别为S和is由£1，出，出駅和F厂丿星f-2,i + 2（2.3）定义。对插值的三次参数0（$） =（片（d W.（5）其中;t1一*C -I计=U；（5）- I- + »：（7）5（5 -川（片）（左3）1V,6f-(7)= 6©-

14、1) b.-s.1” U cr -1旳丿)=vi(s)和 wi(s)中二次- 1) 一* S.如果给定数据点是一条三次多项式函数曲线上的点，则 项系数之比等于三次项系数之比8，即1（17JT®十茁（丿）片1匕一（耳 + 1）比化简得:6 = + (1 - Ij = i 一 + 2（7 .（7,< （）,1 < （T. r其中满足'弋十由于Q （s）是唯一的，从而有匕(f-2)-口j + 2)+ 2)(35)直接验证知，两式是等价的，并且可写成如下形式(3.6)S+Jbg -m）（巧+2 - 1 Xkj（l 儿）一5J（6,-s.）- 07（5一6）（571）（片*

15、（1一 ）一巧0（5寸丄-6）=o由（3.4）知，这时一个关于 Si的一元五次方程，用公式法不能求出精确解。可用如下方法求精确解。考虑Pk，k=i-1,i+3，把变换（3.1）施加到Pk，由对称性得6+1 （ b心一 m ）（ 6 +m 1 ）（耳T（ 1 一 兀）叽（6-1 - £ J 一 -坷）=0其中St和由（3.4）定义。联立（3.6）和（3.7）可求出精确解Si。因此平面 六点可唯一定义一条三次多项式函数曲线。对边界数据点Pi,当3 = i ,相应于（3.7）的方程是斗）（b* 1）（片7（1 -呵）一-）- 1）（片打（1 -罚）一巧黑（巧*3 - $J） = 0(3.8

16、)联立（3.6）和（3.8）可求出精确解 S3对P2 ,由（3.4）知，相应于P2的参 数是6 7+（】一冬一叫）內所以，山=一6心一6）同理可求出计算题可用两种方法计算Si : 1）对（3.6）直接用数值方法求；2）联立（3.6）和（3.7） 用公式法求。所求的 Si应满足下列条件：0 <5. < 1J +(1巧£ -"lJ® V a也+(I 一片> h(3,9|这样的Si可能多于一个。所以，平面有序五点不能唯一决定一条三次多项式冒 C A ?函数曲线。 确定Si的方法是所有满足（3.9）的' 7 加权平均。下面讨论权函数的取值。在所有

17、 % % 儿中，只有一个值是所求的。-3，如果给定数据点是三次多项式函数上的点，由（3.3）和（3.4） 知，“mS 中应有一个Si,l满足考虑叫“）=V；九、力丿G（门耳血-）（» -1） = 0 让邑!伙）I =叫-"-叭jU）竹-1） = 0英屮，(耳,叫)是点理经$丨)变携后的坐标值,必=叫十(1-心-叫)込= 17 + (1-'-巧用丿Eij U)= 吃")+讥矯仗),k = /-3, /+3如果给定数据点+ H和P k不是三次多项式上的点，则,£；川)>0,斤=卜3,7+3。在这种情况下，希望E"仗)值小的Si,i对形

18、成Si的影响大。为此定义3</<n-2,/ ="-E卫+3), 2环(7-3)5(7+3)旧 £廿(一3) + E打(/+3) &川-3),'Si由下式定义:=工心人八北(3J0)，显然，如果Si,j ,满足Ei,j=O，则Si = Si,j。记(3.6)的右端为F(Si)。计算表明，在大多数情况下，F(Si)有符合(3.9)的两个 实根或两个重根，如图1所示。在图1中，F(Si)虽然有三个实根，但左边的根 不符合条件(3.9)。如果(3.6)中没有满足(3.9)的Si，贝诞取F(Si)在0,1区间上的 极小值点(F(Si)在0,1区间上的极值点

19、的值大于零)或极大值点(F(Si)在0,1区间 上的极值点的值小于零)作为Si。例如，对图2所示的情况选取极大值点为 Si。 如果F(Si)在0,1区间上既没有符合(3.9)的实根，也没有符合条件的极小或极 大值点，如图 3所示，则Si的选取应极小化下式的值比(4 2)_匕(/ +十卩r(/ = 2)-W；(/ + 2)F7 = /-2j + 2即,对应使(3.3)定义的两个三次参数曲线的三次项系数的差最小。例子:本节我们以实例对新方法、累加弦长法、向心法，修正弦长法和二次精度法 做比较。用于比较的数据点取自一条给定曲线。 用五种方法分别对给定数据点构 造三次参数样条曲线，以样条曲线的插值精度

20、对五种方法进行比较。 定义数据点 的曲线尸"）是(5J)x(O = z(z-1)(2/- )K +3r(3 一2i) y(f) = f(l-f)K其中，K'S 4三次参数曲线F（t）具有如下性质：K = 1,2,3,4时是凸的，K = 5,6,7,8时有 两个拐点，K = 9时有一个尖点，K = 10,11,12时有一个圈，图4是K = 3,6,9,12 时F（S）在区间0,1上的图形。用于比较的区间是0,1。区间被分成20个子区间定义数据点 Pi=F(Ti),i=0,1,2,20 ,Ti由下式定义(02)!. = 1/ + Z sin(20r)Z)J/20 i = 0.L2

21、A ,20<3.其中OW疋0.25。入的取值使数据点相邻两弦长耳-& 和出*+】满足Pg五种方法用绝对误差曲线E(s)比较,E(s)定义如下£(5)= |P($) -Fg “ <f <3|/=02A917其中 P(s)表示五种方法构造的三次参数样条曲线之一，F(t)为(5.1)或1。(5.3)定义的曲线，P i(s)表示P(s)在区间Si,Si+1上的部分，|P(s)-F(t)表示点P(s) 到F(t)的距离。(5.2)中取入=0.25时，五种方法产生的最大绝对误差见表 表1 五种方法对(5.1)插值产生的最大误差E(s)新方法二次精度累加弦长修正弦长向心K

22、=19.07e-61.68e-53.91e-44.97e-48.07e-4K=25.08e-69.24e-62.23e-52.77e-41.29e-3K=31.73e-74.89e-62.42e-55.50e-41.87e-3K=44.73e-51.47e-54.50e-59.40e-42.37e-3K=51.01e-43.88e-45.43e-51.36e-32.70e-3K=63.60e-46.21e-42.60e-41.68e-32.73e-3K=74.33e-41.64e-31.44e-31.61e-32.06e-3K=82.19e-43.08e-44.25e-31.07e-31.37

23、e-3K=92.68e-49.34e-41.11e-34.57e-41.84e-3K=102.75e-44.25e-46.32e-31.93e-32.31e-3K=111.72e-43.83e-43.15e-33.82e-33.70e-3K=121.46e-43.79e-41.23e-35.17e-35.55e-3下面用一个椭圆定义数据点对五种方法构造的闭合曲线进行比较。椭圆的方程是(5.3)X = 3cos(2 n t)Y = 2sin(2 n t)区间0,1也被分成20个小区间定义数据点。本例中也对用精确节点值构造的三次参数插值曲线进行比较。对应于(5.2)中不同的入，六种方法产生的最大绝

24、 对误差见表2。计算知，本例中入=0时新方法和二次精度法指定的节点都是精 确的。表2说明，对本例，新方法构造的插值曲线的精度比用精确节点构造的插值曲线的精度高。表2 五种方法对椭圆插值产生的最大误差E(s)精确参数新方法二次精度累加弦长修正弦长向心入 =.07.68e-57.68e-57.68e-56.65e-41.87e-43.56e-4入=.051.36e-41.16e-42.08e-47.55e-43.46e-34.68e-3入=.102.20e-41.68e-43.85e-48.41e-47.48e-31.02e-2入=.153.25e-42.26e-46.03e-49.23e-41.

25、24e-21.65e-2入=.204.51e-42.88e-48.62e-41.00e-31.83e-22.37e-2入=.256.00e-43.53e-41.17e-31.07e-32.50e-23.18e-2我们还把区间0,1分成30、40等个小区间对五种方法进行比较，其结果类 似于表1和表2。总结:在平面上唯一确定一条三次多项式函数曲线需要6个有序数据点。如果给定的6个有序数据点是三次多项式函数 F上的点，则6个数据点可精确定义F。对平面上给定的n个数据点，本文提出了一个对其进行参数化的新方法。用 指定节点构造的三次参数样条曲线是 2GC连续的，其多项式准确集包括所有三 次和小于三次的函数多项式。实例计算也表明，新方法构造的三次参数样条曲线 对给定数据点，尤其是对凸的数据点，具有较高的插值精度。继续的工作是：研究是否存在一个对数据点参数化的方法，使构造的三次参数样条曲线的多项式准确集包括所有三次和小于三次的参数多项式。推广本文思想构造对空间数据点插值的 2GC三次参数样