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

天空乐园网（郑州大学生兼职）天空乐园网（郑州大学生兼职）由天空乐园网（郑州大学生兼职）整理更多信息请及时登三次样条曲线的生成算法天空乐园网（郑州大学生兼职）天空乐园网（郑州大学生兼职）１天空乐园网（郑州大学生兼职）天空乐园网（郑州大学生兼职）三次样条曲线的生成算法摘要三次样条函数曲线具有的最高多项式插值精度是三次多项式函数，对其进行推广构造的三次参数样条曲线应至少具有同样的插值精度。本文讨论了构造三次参数样条曲线中节点选取问题，相邻两节点之间的跨度规范化为1，提出了构造2GC三次参数样条曲线的新方法。文中首先讨论了2GC三次参数样条曲线需满足的连续性方程，然后讨论了平面有序五点确定一组三次多项式函数曲线和平面有序六点唯一确定一条三次多项式函数曲线。在此基础上，提出了为给定数据点选取节点值的新方法。新方法构造的2GC三次参数样条曲线具有三次多项式函数的插值精度。最后以具体数据点对新方法和已有的四种节点选取方法构造的插值曲线的精度做了比较。关键词：三次样条曲线；曲线拟合；计算机图形学天空乐园网（郑州大学生兼职）天空乐园网（郑州大学生兼职）１自1946年美国数学家I.J.Schoenberg提出样条函数[1]以来，样条函数以其构造简单、易于计算又有很好的力学背景等特点而被广泛用于科学计算、工程设计和计算机辅助设计等领域，成为最重要的曲线和曲面构造方法之一。在样条函数的应用中，三次样条函数由于具有极小模性质、最佳逼近性质和很强的收敛性[2,3,4]等而成为最主要的方法应用于构造插值曲线和曲面。用样条函数方法构造三次插值曲线，曲线的连续性基本可满足实际应用的要求。当曲线的端点条件确定之后，曲线的精度和形状是由曲线需满足的连续性方程唯一决定的。在小挠度的情况下，插值曲线的精度和形状都是非常理想的。对大挠度曲线和任意平面数据点，则需推广三次样条函数方法构造三次参数样条曲线，此时需知道每个数据点处的参数值（节点值）。在实际应用中，这些参数值一般是无法预先给定的，所以构造三次参数样条曲线的第一步是对给定数据点参数化，即为每个数据点指定节点值。如果指定的节点值是精确的，给定适当的端点条件，可使构造的插值曲线的代数精度达到三次参数多项式。构造三次参数样条曲线，当曲线的端点条件确定之后，能够决定曲线插值精度的量只有节点。因此构造三次参数样条曲线的关键是如何选择节点。目前常用的节点选取方法有4种，均匀参数化法、累加弦长参数化法、向心参数化法[5]和修正弦长参数化法[6]。这些方法虽然在实际中得到了较为广泛的应用，但从逼近的角度看，它们的插值精度较低，其插值多项式的最高精度是线性的。最近一个确定节点的方法[7]具有二次多项式插值精度，如果用来构造三次参数样条曲线，这个精度也是较低的。三次样条函数曲线具有的最高多项式插值精度是三次多项式函数，对其进行推广构造的三次参数样条曲线应至少具有同样的插值精度。从这一目标出发，本文讨论了构造三次参数样条曲线中节点选取问题，相邻两节点之间的跨度规范化为1，提出了构造2GC三次参数样条曲线的新方法。文中首先讨论了2GC三次参数样条曲线需满足的连续性方程，然后讨论了平面有序五点确定一组三次多项式函数曲线和平面有序六点唯一确定一条三次多项式函数曲线。在此基础上，提出了为给定数据点选取节点值的新方法。新方法构造的2GC三次参数样条曲线具有三次多项式函数的插值精度。最后以具体数据点对新方法和已有的四种节点选取方法构造的插值曲线的精度做了比较。平面自由曲线——不能用一个标准代数方程精确表示。实际中应用很多，如轮船船身放样。将放样过程抽象为:平面上给定若干点（型值点），找一个代数方程，逼近或插值上述型值点。理论上，n个点，可以找到一个n-1次多项式来逼近，但n太大时，多项式次数太高，计算复杂，难以控制。工程上，降低次数，且分段定义。样条函数自提出以来，以其构造简单，易于计算，及很好的力学背景等特点被广泛用于科学计算，工程设计和计算机辅助设计等领域，从而成为最重要的曲线和曲面构造方法之一。三次样条曲线在使用中存在局限性，且表示方法缺乏几何不变性。即当平面直角坐标系中得型值点发生旋转等几何变形时，其曲线的形状也发生变形，严重时甚至不能保证满足X1X2X3Xn的条件，对表现曲线的几何形状极为不便；天空乐园网（郑州大学生兼职）天空乐园网（郑州大学生兼职）２在使用autoCAD中spline命令绘制样条曲线时，可能导致各型值点的横坐标也不能满足X1X2X3Xn的条件。为了解决这些问题，一些学者运用向心参数法在周期性三次样条曲线拟合控制多边形时，取得了很小的偏差；基于累加弦长的三次参数样条曲线插值在数控系统中取得了较好的效果，但是以累加弦长为参数的三次参数样条曲线插值和基样条的函数插值在各分段曲线两端曲率的符号相同的情况下都有可能产生这段曲线上的拐点，造成曲线不光顾。因此一些准测提出检查多余的拐点，YEJ等人修正了Kjellander的方法，并从累加弦长参数化和光顾函数两方面消除了三次参数样条的震荡和回折。在曲线拟合中，插值过程可具体使用线性（liner）插值，三系样条（spline）插值，立方(cubic)插值等方法，在曲线插值法中最常用的是线性插值法，它是估计2个主干点之间数值的最简单，最易实现的方法，但采用线性插值法会有以下缺点：1曲线不能显示连接主干点间的凸状弧线；2从曲线导出远期曲线时会形成人为的“尖头”。因此，通常采用样条法来构造曲线，它通过构造多项式（1个或1组不同阶多项式）来形成1条把所有主干点连接起来的平滑曲线，一般常选择3次曲线（根据3次插值样条函数所得的曲线）进行拟合。3次样条曲线具有良好的数学特征，而且用3次曲线去拟合时，其结果要比线性插值估计更接近于工程实际情况，但是在工程应用中，我们利用三次样条插值方法，对相同的控制点，只可以得到1条光滑曲线，如果我们想基于相同的控制点，得到多条不同曲线，依靠传统算法，是无法实现的，这就限制了三次样条在工程中，特别是印刷领域中得应用。在印刷领域，特别市在工艺前端，传统的方法是利用曲线进行分色操作，由于色彩的特殊性，即人眼对色彩的感觉不尽相同。如果只有1条色度曲线，那么工艺人员就无法对色彩效果进行有效的对比。因此印刷工艺的特殊性要求能够根据相同控制点，得出多条曲线，实现不同的印刷色彩效果，从中选出最佳的色度曲线。在这一点上，传统的方法是通过修改基本的控制点，生成新的控制曲线实行，本文提出改进的3次样条算法，实现了在相同的控制点上，生成了曲线不同的新曲线。增加了生成曲线的条数，从而使得印刷前端的工艺操作人员，对控制图像的色度曲线有更多的选择。三次参数样条曲线的构造设平面上给定了n个数据点目标是构造一条对n个数据点插值的三次参数样条曲线P(t)。设ti(待定)是与iP相对应的节点，令则区间上的三次参数曲线Pi(t)可定义如下：其中天空乐园网（郑州大学生兼职）天空乐园网（郑州大学生兼职）３为[0,1]区间上的三次埃尔米特基函数，为节点ti处的切矢。Pt()应满足的连续性方程是[6,8]：其中;令；则(2.2)可写成如下形式：其中；如果Si给定，则可得到(2.4)中的Ni,i=1,2,…,n,由天空乐园网（郑州大学生兼职）天空乐园网（郑州大学生兼职）４知，对i=1,2,…,n-1,(2.1)可写成如下形式：其中0≤s≤1。显然，由(2.6)定义的样条曲线是连续的。方程组(2.4)中有n−2方程，n个未知量,解方程组需增加两个端点条件，方法如下：(1)对封闭或周期曲线所以，(2)两端点处的二阶导数为零此时，对(2.4)中的i=2和n-1，相应的方程为天空乐园网（郑州大学生兼职）天空乐园网（郑州大学生兼职）５所求方程中的未知量为(3)给定端点切向条件M1和Mn，其中F1和F2的值确定将在第四节中讨论。设，是给定数点中连续五点，与Pj相对应的节点是tj(待定)。为讨论方便，我们做如下变换。设不在一条直线上，把坐标变换分别施加到Pi和ti。则在ovw坐标系中的坐标为相应的节点值分别为和其中is由(2.3)定义。对插值的三次参数曲线是天空乐园网（郑州大学生兼职）天空乐园网（郑州大学生兼职）６其中；如果给定数据点是一条三次多项式函数曲线上的点，则vi(s)和wi(s)中二次项系数之比等于三次项系数之比[8]，即化简得：其中满足由于Q(s)是唯一的，从而有直接验证知，两式是等价的，并且可写成如下形式由(3.4)知，这时一个关于Si的一元五次方程，用公式法不能求出精确解。可用如下方法求精确解。考虑Pk，k=i-1,i+3，把变换(3.1)施加到Pk，由对称性得天空乐园网（郑州大学生兼职）天空乐园网（郑州大学生兼职）７其中由(3.4)定义。联立(3.6)和(3.7)可求出精确解Si。因此平面六点可唯一定义一条三次多项式函数曲线。对边界数据点Pi，当3=i，相应于(3.7)的方程是联立(3.6)和(3.8)可求出精确解S3对P2,由(3.4)知，相应于P2的参数是所以，同理可求出。计算题可用两种方法计算Si：1)对(3.6)直接用数值方法求；2)联立(3.6)和(3.7)用公式法求。所求的Si应满足下列条件：这样的Si可能多于一个。所以，平面有序五点不能唯一决定一条三次多项式函数曲线。确定Si的方法是所有满足(3.9)的加权平均。下面讨论权函数的取值。在所有中，只有一个值是所求的。考虑，如果给定数据点是三次多项式函数上的点，由(3.3)和(3.4)知，中应有一个Si,l满足天空乐园网（郑州大学生兼职）天空乐园网（郑州大学生兼职）８如果给定数据点和Pk不是三次多项式上的点，则,。在这种情况下，希望值小的Si,l对形成Si的影响大。为此定义Si由下式定义：显然，如果Si,j,满足Ei,j=0，则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]区间上的极值点的值大于零)或极大值点(F(Si)在[0,1]区间上的极值点的值小于零)作为Si。例如，对图2所示的情况选取极大值点为Si。如果F(Si)在[0,1]区间上既没有符合(3.9)的实根，也没有符合条件的极小或极大值点，如图3所示，则Si的选取应极小化下式的值天空乐园网（郑州大学生兼职）天空乐园网（郑州大学生兼职）９即，对应使(3.3)定义的两个三次参数曲线的三次项系数的差最小。天空乐园网（郑州大学生兼职）天