（应用数学专业论文）关于圆盘b样条曲线插值及节点插入问题的研究.pdf

摘要 内容摘要：在计算机辅助几何设计( 简称c a g d ) 实践中，经常遇到 要求构造插值曲线以用于对已有曲线形状的近似表示问题，也就是构 造一条曲线( 一张曲面) 严格通过给定的数据点集( 一般从实际测 量中得到) 但是由于测量技术和手段等各方面的限制，经过测量得 到的数据通常都带有误差在二维的情况下，这些带有误差的测量数 据就是平面上一系列的小区域，这样一般的插值问题就演变成如何对 一系列的小区域进行插值的问题本文基于b 样条曲线的理论，对如 何用圆盘b 样条曲线对这些测量得到的小区域进行插值的算法进行了 研究节点插入算法是b 样条方法配套技术中最重要的技术之一，通 过插入节点，可增加曲线曲面造型的柔性，可以证明b 样条曲线的变 差减少性质等等，此外，实现b 样条曲线的另一基本运算升阶运算也 是以节点插入算法的实现为前提的本论文在一般b 样条曲线插入节 点算法的基础上，进一步研究了圆盘b 样条曲线的节点插入算法论 文主要包含以下内容：第一章绪论部分介绍了本文的研究背景及研 究内容，阐明了在曲线( 曲面) 的形状描述中引入圆盘算术的必要 性；第二章介绍了b 样条曲线的定义和性质，并且对已有的b 样条曲线 的插值算法进行了分析；第三章主要介绍圆盘b 样条曲线的定义及性 质，给出了圆盘b 样条曲线的递归算法；第四章具体讨论了对于带有 误差的测量数据，用圆盘b 样条曲线进行插值的算法，并且说明了所 得到的圆盘b 样条曲线具有局部性、连续性等良好的性质；第五章在 圆盘b 样条曲线定义的基础上研究了圆盘b 样条曲线的节点插入算法 关键词：b 样条曲线；数据圆盘；插值算法；节点插入；圆盘b 样条曲线； 连续性；数值实例 a b s t r a c t c o n t e n t ：i nt h ec o m p u t e r - a i d e dg e o m e t r i cd e s i g n ( c a g d ) p r a c - t i c e ，w eo f t e ne n c o u n t e r e dh o wt oc o n s t r u c tai n t e r p o l a t i o nc u r v et o d e s i g nac u r v e ss h a p e t h eb a s i cp r o b l e mi st oc o n s t r u c tac u r v e ( s i l l - f a c e ) t ob es t r i c t l yt h r o u g ht h ed a t ap o i n t ss e t ( n o r m a l l yg e tf r o mt h e a c t u a lm e a s u r e m e n t ) h o w e v e r ，b e c a u s et h em e a n so fm e a s u r e m e n t t e c h n o l o g ya n dt h er e s t r i c t i o n s ，i nt h em e a s u r e m e n to fd a t au s u a l l y w i t he r r o r i nt h et w o - d i m e n s i o n a lc a s e ，t h em e a s u r e m e n td a t aw i t h e r r o ri sas e r i e so fs m a l la r e ao nt h ep l a n e ，s ot h eg e n e r a li n t e r p o l a t i o n p r o b l e mt u r ni n t oh o wt oc a r r yo u tas e r i e so fs m a l lr e g i o n a li n t e r p 0 - l a t i o np r o b l e m i nt h i sp a p e r ，b a s e do nt h eb s p l i n ec u r v et h e o r y ，t h e i n t e r p o l a t i o na l g o r i t h mh o wt ou s ed i s kb s p l i n ec u r v e st oi n t e r p o l a t e t h r o u g ht h e s es m a l lr e g i o n sw a ss t u d i e d k n o ti n s e r t i o na l g o r i t h m i ss u p p o r t e do n eo ft h em o s ti m p o r t a n tt e c h n o l o g yo ft h eb s p l i n e s m e t h o d t h r o u g hk n o ti n s e r t i o n ，i n c r e a s et h ef l e x i b i l i t yo fs u r f a c e m o d e l ，i t sc a np r o v et h a tt h ev a r i a t i o nd i m i n i s h i n gp r o p e r t yo fb s p l i n ec u r v e s ，e t c i na d d i t i o n ，t h ea l g o r i t h mo fk n o ti n s e r t i o ni st h e f o u n d a t i o no fd e g r e ee l e v a t i o nw h i c hi sa l s oo n eo ft h em o s ti m p o r o t a n tp r o p e r t yo fb s p l i n e i nt h i sp a p e r ，b a s e do nt h eg e n e r a lb s p l i n e c u r v e sw es t u d yt h ed i s kb s p l i n ec u r v ek n o ti n s e r t i o na l g o r i t h m i t s m o s t l yc o n t a i n st h ef o l l o w i n gc o n t e n t s ：c h a p t e r1i n t r o d u c et h eb a c k - g r o u n da n dr e s e a r c hc o n t e n to ft h i sp a p e r ，a n di l l u s t r a t e st h en e c e s s i t y f o ri n t r o d u c t i o no fd i s ka r i t h m e t i ci nt h es h a p eo fc u r v e ( s u r f a c e ) d e - s c r i b i n g ；t h es e c o n dc h a p t e rd e s c r i b e st h ed e f i n i t i o na n dp r o p e r t yt h e b - s p l i n ec u r v e s ，a n da n a l y z e dt h ei n t e r p o l a t i o na l g o r i t h mo fb - s p l i n e 关于圆盘b 样条曲线插值及节点插入问题的研究 c u r v ew h i c hh a db e e ne x i s t e d ；c h a p t e r3i n t r o d u c e st h ed i s kb s p l i n e c u r v e s ，t h ed e f i n i t i o na n dp r o p e r t yo ft h ed i s kb s p l i n ec u r v e s ，a n d t h er e c u r s i v ea l g o r i t h mo fd i s kb s p l i n ec u r v e s c h a p t e r4i n t r o d u c e a s p e c i f i cd i s c u s s i o nh o wt ou s ead i s kb - s p l i n ec u r v et oi n t e r p o l a t e t h r o u g ht h em e a s u r e m e n td a t aw i t he r r o r ，a n dt h ei n t e r p o l a t i o nd i s k t h eb s p l i n ec u r v eh a st h eg o o dp r o p e r t yo fl o c a la n dc o n t i n u i t y , e t c c h a p t e r5b a s e do nt h ed e f i n i t i o no fd i s kb - s p l i n ec u r v e ss t u d i e st h e k n o ti n s e r t i o na l g o r i t h mo fd i s kb s p l i n ec u r v e s k e yw o r d s ：b s p l i n ec u r v e s ；d a t ad i s k ；i n t e r p o l a t i o na l g o r i t h m ；i n - s e r tn o d e s ；d i s ko fb s p l i n ec u r v e s ；c o n t i n u i t y ；n u m e r i c a le x a m p l e s l n 关于圆盘b 样条曲线插值及节点插入问题的研究 图表清单 图i 三次b 样条曲线7 图2 三次b 样条开曲线插值9 图3 三次b 样条闭曲线插值1 0 图4 未插入节点前b 样条曲线1 2 图5 插入一个节点后b 样条曲线1 3 图6 插入两个节点后b 样条曲线1 3 图7 插入三个节点后b 样条曲线1 3 图8 三次圆盘b 样条曲线1 7 图9 数据圆盘2 1 图1 0 控制圆盘和控制多边形2 l 图1 1 三次圆盘b 样条插值曲线2 1 图1 2 数据圆盘2 2 图1 3 控制圆盘和控制多边形2 2 图1 4 封闭三次圆盘b 样条插值曲线2 2 图1 5 未插入节点前b 样条曲线2 5 图1 6 插入一个节点后圆盘b 样条曲线2 5 图1 7 插入两个节点后圆盘b 样条曲线2 6 图1 8 插入三个节点后圆盘b 样条曲线2 6 v 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果论文中除特别 加以标注和致谢的地方外，不包含其他人和其他机构已经撰写或发表过的研究成果，其他同 志的研究成果对本人的启示和所提供的帮助，均已在论文中做出了明确的声明并表示谢意 一躲聒忪 e t 期：炒宫弓，矽 学位论文版权使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有权 保留并向国家有关部门或机构送交复印件和磁盘，允许论文被查阅和借阅本人授权辽宁师 范大学，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或其他复制手段保存、汇编学位论文保密的论文在解密后使用本授权书 一始泵夯缸e l 鬟毪 关于圆盘b 样条曲线插值及节点插入问题的研究 关于圆盘b 样条曲线的插值及节点插入问题 研究 1引言 计算机辅助几何设计( c o m p u t e r - a i d e dg e o m e t r i cd e s i g n ，简称c a g d ) 是一 门新兴学科，它的出现和发展对现代化工业的发展起到了巨大的促进作用【1 】并 且随着计算机科学以及现代化汽车、航空、机械制造等工业的蓬勃发展而迅速 发展起来它与微分几何、代数几何、数值逼近、矩阵论、数控技术和计算数 学等学科都有着十分密切的关系c a g d 最初主要应用于航空、汽车、造船等制 造业，现在已经进一步扩展到用于计算机辅助设计( c a d ) 、建筑设计、生物工 程、医疗诊断、电子工程、服装鞋帽模型设计、地质研究和计算机动画制作等 技术领域 1 1参数曲线曲面造型技术的总结与回顾 曲线曲面造型技术主要研究在计算机图像系统的环境下对曲线曲面的表 示、设计、显示和分析它最早起源于汽车、飞机、船舶、叶轮等工程应用领 域的外形放样工艺，由c o o n s 、b d z i e r 等大师于二十世纪六十年代奠定了理论 基础1 9 6 3 年，美国波音飞机公司的f e r g u s o n 提出了将曲线曲面表示为参数的 矢函数的方法，构造了组合曲线和由四角点的位置矢量及两个方向的切矢定义 的f e r 目】s o n 双三次曲面片，并引入了三次参数样条【2 】1 9 6 4 年c o o n s 提出了一个具 有一般性的曲面描述方法，给定围成封闭曲线的四条边界就可定义一块曲面片 1 9 4 6 年由s c h o e n b e r g 在他直到1 9 6 7 年才发表的论文中，首先提出了样条函数的概 念【3 】，提供了解决连接问题的一种技术样条方法用于解决插值问题，在构造整 体达到某种参数连续阶的曲线曲面时非常方便，但是他没有局部调整的自由度， 样条曲线曲面的形状难以预测1 9 6 2 年，法国雷诺汽车公司的b d z i e r 提出了一种 由控制多边形定义曲线的新方法，并以这种方法为基础，发展了一套自由型曲线 曲面的设计制造系统，称之为u n i s u r f 4 一只要移动控制顶点就可以方便地修 改曲线的形状而且形状的变化完全在预料之中b d z i e r 方法简单易行，又出色地 解决了整体形状控制的问题，在c a g d 中占有重要的地位，为c a g d 的进一步发 展奠定了坚实的基础但b d z i e r 方法仍然存在缺陷和不足，如连接问题，局部修改 问题等 1 9 7 2 年d e b o o r 7 与c o x i s 分别独立给出了关于b 样条计算的标准算法但作 为在c a g d 中的一个形状数学描述的基本方法，是在1 9 7 4 年由美国通用汽车公 关于圆盘b 样条曲线插值及节点插入问题的研究 司的g o r d o n 与r i e s e n f e l d 在研究b d z i e r 方法的基础上引入的【9 1 并将其与b d z i e r 曲 线联系起来作为其强有力推广，提出了b 样条方法它几乎继承了b d z i e r 方法的 一切优点，克服7 b 百z i e r 方法存在的缺点，较成功的解决了局部控制问题，又轻 而易举的在参数连续性基础上解决了连接问题为了保留b d z i e r 方法的优点，仍 采用控制顶点定义曲线同b d z i e r 曲线相比较，除了共有的直观性和保凸性等一 些优点外，还具有以下的优越性：( 1 ) 基函数的次数与控制顶点无关，计算简单； ( 2 ) b d z i e r 曲线缺乏局部性质，b 样条曲线具有良好的局部性质 1 2基于误差的曲线曲面造型技术研究现状 在实际应用中，由于测量误差和技术手段等限制，按照设计图纸加工出来 的产品不可能是精确的形式，而是在精确的曲线曲面附近变动，这样就形成了 一个区域，对这个区域的研究就有着实际的意义在曲线曲面的求交过程中， 由于浮点运算中存在着误差，常常会出现交点丢失的现象，而交点丢失会影响 系统的的稳定性因此，在几何设计和计算中缺少稳健性为了解决这些问 题，引入了区间算术( m u d u ra n dk o p a r k a r ，1 9 8 4 ；s e d e r b e r ga n df a r o u k i ，1 9 9 2 ； p a t r i k a l a k i s ，2 0 0 0 ) 1 9 9 2 年s e d e r b e r g 和f a r o u k i 1 0 】引入了区间b d z i e r 曲线的概念， 把区间算术引入到c a g d 中来h u 等人将区间运算应用于曲线曲面求交及几何 形体的表示中1 1 1 _ 1 3 】，提高了曲线曲面求交的稳健性t u o h y 和p a t r i k a l a k i s 弓i 入 了区间b 样条曲面的概念【1 4 1 寿华好讨论了区间曲线曲面和o f f s e t 曲线曲面的关 系【1 5 】；陈效群研究了利用区间曲线逼近o f f s e t 曲线和有理曲线【16 】；刘利刚等引进 了区间b d z i e r 由面的概念，给出了利用区间b d z i e r 曲面逼近一般曲面和有理参数 曲面的两套算法【1 7 1 陈发来【1 8 1 9 1 ，杨勤民【2 0 】和李涛等 2 1 】分别讨论了区间b e z i e r 曲 线降阶问题及区间b 样条曲线降阶问题，区间三角b e z i e r 曲面降阶以及有理区 间b z i e r 曲线曲面降阶逼近魏永伟等研究了区间b z i e r 曲线曲面的升阶算法 区间曲线曲面具有很多自身的优点，但是也存在着缺点比如在计算的过程 中区间会迅速变大，区间在旋转变换的过程中不具有对称性等缺点为了克服 这些缺点于是采用圆盘代替区间1 9 9 8 年q l i n 和j r o k n e 2 2 】提出了圆盘b d z i e r 曲 线，并讨论了圆盘b d z i e r 曲线的一些基本性质，同时提出了球域b d z i e r 曲线的概 念陈发来等研究了圆盘b d z i e r 曲线的降阶问题1 1 8 1 陈笑等用圆盘b d z i e r 曲线逼 近等距曲线翁彬等【2 4 , 2 5 1 提出了圆盘b 样条曲线的概念，并且研究了圆盘b 样 条曲线的降阶以及节点去除问题 1 3 曲线( 面) 插值算法概述 曲线曲面插值问题研究是计算机辅助几何设计( c a g d ) 中的基本课题之 2 关于圆盘b 样条曲线插值及节点插入问题的研究 一，也是一个始终非常活跃的研究领域关于曲线( 面) 插值的基本问题就是要 构造一条曲线( 一张曲面) 严格地通过给定的型值点集这种插值问题属于逆 向工程( r e v e r s ee n g i n e e r i n g ) 范畴，在自动化设计、机械制造、仿真以及医学 等方面都有非常广泛的应用插值法是一个古老的数学方法，它来自生产和实 践在计算机广泛使用之后，由于航空、造船等实际问题的需要，使插值问题在 实践或理论上显得更为重要，并得到很大的发展其中多项式插值在曲线造型中 起着重要的作用插值方法大概可以分为两个大类：整体插值和局部插值整体 插值能够较容易地构造满足给定连续阶的插值曲线最常见的是用c 2 连续的三 次曲线插值，它满足给定的端点条件本文也是从整体插值方面研究的圆盘b 样 条曲线的插值问题当然与局部插值相比整体插值也有它的局限性：在插值时不 便于曲线的局部形状调整控制相比较而言，局部插值更具有灵活性，更便于局 部调整，但是在连续阶方面有一定的限制例如，三次多项式样条作局部插值只 能达到c 1 连续曲线曲面插值一个典型的方法就是求解线性方程组来决定曲线 ( 面) 的控制网格，这种反求控制顶点的方法是一种全局性的行为，可以达到理 想的连续阶对于一般的曲线曲面插值方法的研究已受到广范关注，这方面已有 大量研究而对于圆盘b 样条曲线插值问题的研究据本文作者所知，尚未有具体 研究张宁【2 6 1 研究了如何用圆盘b d z i e r 曲线对这些小区域进行插值的问题，但是 其中用来插值的圆盘b d z i e r 曲线的整体表示不具备局部性和控制的灵活性等缺 点，这给插值过程带来很大的麻烦而用圆盘b 样条曲线代替圆盘b d z i e r 曲线进行 插值兼具了圆盘b 百z i e r 曲线插值的一切优点，而且克服了圆盘b d z i e r 曲线插值时 整体不具有灵活性等缺点 1 4b 样条曲线节点插入算法概述 b 样条方法在自由曲线曲面设计中占有重要的地位，这主要也是由于它自身 的很多配套技术的完善，例如：求导、反算、节点插入、升阶等等其中节点插入 算法在几何造型中起着举足轻重的作用，它既有重要的理论价值，而且在曲线曲 面设计中有着广泛的用途通过插入节点：( 1 ) 能简单的证明b 样条曲线的变差减 少( v d ) 性质；( 2 ) 可以进一步改善b 样条曲线的局部性质，提高对b 样条曲线控制 的潜在灵活性；( 3 ) 可以求出b 样条曲线上的点；( 4 ) 可以生成曲线的b d z i e r 点，得 到b 样条曲线的分段b d z i e r 表示；( 5 ) - - i p a 实现对曲线的分割；( 6 ) 在生成曲面时，可 以使不同的节点矢量统一起来等等1 1 】1 关于多项式b 样条节点插入问题已有两 个著名算法：每次都插入一个新节点的b o e h m 算法【2 7 ，冽和一次插入一列新节点 的o s l o 算法例这两个算法都有很多的改进和推广的版本它们已形成其它非 多项式样条曲线插入节点算法研究的基础b o e h m 算法是一维的线性方案，算 3 关于圆盘b 样条曲线插值及节点插入问题的研究 法简单，并且几何直观，因此易为工程实际所接受；o s l o 算法虽然同时可插入多 个节点，它要用到离散b 样条的理论却是一个二维的三角方案，因此效率远没 有b o e h m 算法高然而，它的改进版，可以提高o s l o 算法的效率秦开怀等提出的 插入节点算法改进- b o e h m 的算法，使得可在曲线的定义域外插入节点潘日 晶等给出了b 样条曲线的一种同时插入多个节点的算法1 3 1 】 1 5 本文研究内容 本文共分五章，各章内容如下： 第一章引言，主要介绍了与本文研究内容相关的曲线曲面造型的研究现状 与发展，并且进一步阐述了基于误差的曲线曲面造型技术的研究现状与发展在 介绍了插值算法和节点插入算法研究现状的基础上，说明本文研究内容的必要 性并且给出了本文要研究的内容 第二章介绍了b 样条曲线的定义、主要性质以及计算b 样条曲线上点的德 布尔算法并且介绍了利用线性方程组反求控制定点的基本插值方法接着对 已有的一般b 样条曲线的b o e h m 节点插入算法进行分析最后，用j a v a i 吾言给出 了b 样条曲线插值及节点插入算法的数值实例 ， 第三章引入了圆盘b 样条曲线的概念及其性质，重点讨论了圆盘b 样条曲线 的连续性问题接着给出了圆盘b 样条曲线的递归算法 第四章在第二章、第三章的基础上，具体研究了如何用圆盘b 样条曲线对 测量得到的带有误差的数据点进行插值的算法。通过数值实例说明了算法的 可行性在本章的最后，对于如何处理带有误差数据的包围圆方法【2 6 】做了介绍 第五章在第二章及第三章的基础上研究了圆盘b 样条曲线的节点插入算法， 并给出其数值实例 4 关于圆盘b 样条曲线插值及节点插入问题的研究 2b 样条曲线及其插值算法 b 样条方法兼具了 b d z i e r 方法的一切优点，具有表示与设计自由型曲线曲面 的强大功能，是广泛流行的形状数学描述的主流方法之一另外，b 样条方法是 目前已成为关于工业产品几何定义国际标准的有理b 样条方法的基础只有在 掌握b 样条方法原理与算法的基础上才能学习有理b 样条方法基于其重要应用， 1 9 7 2 年德布尔和考克斯分别独立给出了关于b 样条计算的标准算法本章主要介 绍b 样条曲线的定义、基本性质以及b 样条曲线的插值算法及节点插入算法 2 1b 样条曲线的定义f 1 】 b 样条曲线有着多种定义，这里我们主要介绍作为标准算法的德布尔和考克 斯的递推定义 定义2 1 一条k 次b 样条曲线定义如下： ( 2 1 ) 其中只0 = 0 ，l ，2 ，冗) 为b 样条曲线的( 冗4 - 1 ) 个控制顶点，顺次连接这些控制 顶点就构成了b 样条曲线的控制多边形，而批，缸( u ) g = 0 ，n ) 为由非递减节点 矢量u = 【u o ，u 1 ，u n + 七+ 1 确定的七次b 样条基函数其递推公式给出如下： 缸毗+ l u ) + u i + 世k - - 吐1 - - u i + 1m + 1 ，七一1 ( 也) ，- i n 、， ( 2 2 ) 这里规定o = 0 递推公式表明，k 次b 样条基函数具有如下性质： ( 1 ) 递推性由公式容易证得 ( 2 ) 规范性：om ，k ( u ) = 1 ( 3 ) 局部支承性 晰) 裂o f o 胁ru s i 如如m 这里也表明了它的非负性 ( 4 ) 可微性在节点区间内部是无限可微的，在节点处是( 后一r ) 次可微的，这 里的r 是节点的重复度 5 u 七mr n ：l = 让p 饥 伽 2 私嚣 = = 、，、l， u u ，fl，f p m m ，jl 关于圆盘b 样条曲线插值及节点插入问题的研究 2 2b 样条曲线的性质 由b 样条基函数的性质，可以推出b 样条曲线具有如下的几何性质： ( 1 ) 局部性质此性质是对b 样条曲线行为占支配地位作用的重要性质之 一一个方面是k 次b 样条曲线的定义域内参数为让 让 ，u i + 。】的一点尸( u ) 至多 与( 七+ 1 ) 个顶点b o = t k ，i k + 1 ，z ) 有关，与其他顶点无关这就优 于b d z i e r 曲线，因为b d z i e r 曲线上除了两个端点外的所有点都与控制多边形的所 有顶点有关，这个局部性质也表明，在曲线的定义域内，定义在非零节点区间让 h ，+ 1 】上那一次b 样条曲线段，由( 七+ 1 ) 个控制顶点最一七，只一七+ 1 ，只及相 应的b 样条基函数决定，与其他控制顶点无关从另一方面看，如果移动控制顶 点只至多影响到定义在区间( 地，地+ 1 ) 上那部分曲线 ( 2 ) 可微性在定义域内，节点具有最高重复度为r 的k 次b 样条基函数是( 七一7 ) 次可微的这导致所定义的k 次的b 样条曲线也是( 后一r ) 次可微的 ( 3 ) 凸包性 b 样条曲线恒位于它的凸包之内 ( 4 ) 变差减少性质( 且i j v d 性质) 就平面b 样条曲线而言，平面内任意一条直线与 其交点的个数不多于该直线与控制多边形交点个数 ( 5 ) 磨光性质除共线的顶点外，次数越高，b 样条曲线距离定义它的控制多边 形越远同一组控制顶点定义的b 样条曲线随着次数尼的升高而变得光滑 ( 6 ) 几何不变性与仿射不变性 2 3计算b 样条曲线上点的德布尔算法 给定控制项点只、次数尼及确定的节点矢量汐= 【咖，缸l ，u n + k + 后，就定 义了一条k 次b 样条曲线，给出定义域内一参数值乱【乱l ，u 件1 1c 【妣，+ 1 1 ，计算 该b 样条曲线上对应的点p ( 钍) 的德布尔算法的递推公式如下： 剐一p j ，2 - 0 。 i ( 1 一嘭) 巧一1 + ( 1 ；o d + - 1 1 ，j = z 一忌，i k + 1 ，i z = j u $ + 盟k + l - - u j + 1 规定o = 0 由德布尔一考克斯递推公式( 2 2 ) 及b 样条曲线的方程可推导出这组递推公式 具体算法可叙述如下： 一s e t 砰= 只，i = 0 ，1 ，死 一f o rz = 1 ，2 ，kd o 6 ，u + u 阻 c ，u +讹 心 u 碴 = 珏 1 m 肛， h 一 = u m 弓 竹触 = 让p 关于圆盘b 样条曲线插值及节点插入问题的研究 一f o rj f = i 一，i k + 1 ，一， 一l d o 一 矗：一竺! ! 吐l 、 ，1 j 十七+ 1 一t 0 + l 一碍= ( 1 一嘭) 弓1 + 嘭碍；i e n d 一e n d z o = 0 图l 为一具有五个控制顶点的三次b 样条曲线： 图1 三次b 样条曲线 2 4b 样条曲线的插值方法【3 2 】 构造一条曲线顺序通过经过测量得到的给定的数据点，称为对这些给定的数 据点进行插值，所构造的曲线称为插值曲线由于b 样条方法有着许多优良的性 质，所以对于给定的数据点，研究用b 样条曲线对其进行插值问题具有重要的实 际意义 假设给定了一系列的数据点为q i ，i = 0 ，1 ，n ，构造一条k 次b 样条曲线插 值于这些数据点待求的控制顶点为只，t = 0 ，l ，n + 七一1 2 4 1b 样条曲线插值的一般过程 节点矢量的确定影响着插值曲线的形状和性质，采用的是积累弦长参数化 的方法设u = 【u o ，u l ，+ 七+ 3 】为节点矢量，取u o = 1 5 1 = u 2 = = 妣= 0 ，u n + 七= + 七+ l = + 七+ 2 = = t f i + 2 k = 1 ，对数据点q i 进行积累弦长参数化， 即 ， i 砺= 0 i 磁= 甄一1 + f a q , i ，i = 1 ，2 ，n 其中i q f = l q i q t 一1 1 相应的可确定内节点值地+ 3 = 番，i = 1 ，2 ，n 对于( 七一1 ) 阶连续的b 样条闭曲线，定义域内的节点同样可按上面方法确定， 7 关于圆盘b 样条曲线插值及节点插入问题的研究 但是定义域外的节点按下一方法确定即伽= 一1 ，t 1 1 = + 1 1 ，u 2 = + 2 一 l ，t 珐一1 = + 七一l ；t 厶r 冲惫+ 321 + u k + l ，t 正，i + 知+ 421 + t 七+ 2 ，u n + 2 k21 + t 比七 将参数值磁= 讹+ 七，l = 0 ，1 ，礼依次带入式( 2 1 ) ，就可以产生死+ 1 个线性 方程组： n + k - 1 q 一七= j p ( 地) = n j ，知( 地) 最，t 【地，u i + t c 心知，t 钒l 】 i - - - o 对于开曲线来说，这个方程组少于未知顶点数，还必须补充七一1 个由合适边界条 件给出的附加的方程对于闭曲线来说因为生成的首末南个控制顶点一致，于是 就可以由上面的方程求解了 2 4 2 三次b 样条曲线插值算法及其数值实例 下面我们以三次b 样条曲线为例具体对插值算法进行说明，三次b 样条曲线 也是最常用的b 样条曲线分两个步骤： ( 1 ) 确定节点矢量 设= 【咖，u l ，+ 6 】为节点矢量，取u o = 缸1 = t 2 = 均= 0 ，+ 3 = 锄+ 4 = + 5 = t 6 = 1 ，对数据点q 进行积累弦长参数化，即 ， i 砺= 0 i 瓦= 蕊一1 + i q t i ，i = 1 ，2 ，扎， 其中l q “= l q q i l i 相应的可确定内节点值啦+ 3 = 募，i = 1 ，2 ，n 对于闭曲线情况，也就是首末数据点重合的情况定义域外节点确定为铷= u n 一2 1 ，t 12 一1 1 ，t 正22 一1 ，u n + 221 + u 4 ，u a + 321 + u 5 ，锄“。1 + 坳 ( 2 ) 确定控制顶点 曲线在其定义域t h ，乞k + 1 】c i t 3 ，+ 3 】中的内节点值满足下述插值条件 k + 2 瓴= p ( u k + 3 ) = 只札，3 ( 仳娜) ，k = 1 州2 一，亿一1 ( 2 3 ) i = k 令a k = n k , 3 ( + 3 ) ，k = n k + 1 。3 ( u 七十3 ) ，= 肌+ 2 ，3 ( u k + 3 ) ，将a k ，b k ，c k 代入( 2 3 ) 得线 性方程组 6 1c 1 6 2c 2 o0 0 0姜0。熹0i塞0an 2b n 2。、厂主。 i lb 一一2c n l ir 一1k lc t l 一1 只+ 1 f 吼 i i q 2 i 5 l j iq n 一2 k “ ( 2 4 ) 关于圆盘b 样条曲线插值及节点插入问题的研究 整理得 c l 0 6 2c 2 00 00 00 0 000 q 卜2k 一2c n 一 0 6 n 一1c n 一 马 b r 一1 r q l 一口1 p 1 q 2 q 再一2 q n 一1 一c n 一1 f k + 1 另一方面，令插值曲线的首末控制顶点分别与首末数据点一致，即 p o = q o ，r + 2 = q n ( 2 5 ) 设d o ，d n 分别表示首末数据点处的导数，对于一般的七次b 样条曲线有 风= l ( p l p o ) ， 风= _ l ( r r 1 ) ( 2 6 ) l 一札m 一七一1 可得附加方程 一p o + p l ：祟风， 一r + l + r + 2 ：毕队( 2 。7 ) 利用求曲线首末数据点处导数的贝塞尔方法可求出d o d n ，即 或= 石a 瓦i 酉a p i _ i + 若訾， 户o ：2 竽一赢：d o ， r ：2 尝一或一。：风 其中i = 氟+ 1 一瓦，a 只= 只+ 1 一只 将上式两个附加方程与线性方程组( 2 5 ) 联合，利用追赶法可快速求出控制顶 点只，l = 0 ，1 ，n + 2 对于闭曲线情况，将内节点值魄0 = 3 ，4 ，佗+ 3 ) 依 次代入式( 2 3 ) ，而且有q o = q n ，则只要取r = p o ，r + 1 = p 1 ，r + 2 = p 2 i l p - - j 图2 和图3 分别为b 样条开曲线和闭曲线的插值实例 9 关于圆盘b 样条曲线插值及节点插入问题的研究 图2 三次b 样条开曲线插值 图3 三次b 样条闭曲线插值 2 5b 样条曲线的节点插入算法【3 2 】 b 样条曲线插入节点的主要算法是b o e h m 的算法和c o h e n 等的o s l o 算法本 文是以b o e h m 插入节点的算法为基础研究的，所以我们在这里主要介绍b o e h m 的节点插入算法在本节的最后用j a v a 语言完成其数值实例 2 5 ib 样条曲线的b o e m h 节点插入算法 设 n p ( u ) ：= 只m ，七( 让) ( 2 8 ) i - - - - - 0 为一条已知的七次b 样条曲线，其中b 样条基由节点矢量 u = 【咖，牡l ，+ 知+ l 】 来确定现在在曲线的定义域某个区间内插入一个节点牡h ，啦+ 1 】c 【，+ l 】， 于是得到新的节点矢量 驴= 【u o ，i t l ，t 正，u ，讹+ 1 ，+ 七+ 1 】 重新编号后成为 驴= r o ，面1 ，砜，砚+ 1 ，十七+ 2 】 这些新的节点矢量决定了一组新的b 样条基藏，七( u ) ( i = 0 ，1 ，2 ，n + 1 ) ，新的控 制顶点设为扈( i = 0 ，1 ，2 ，n + 1 ) 那么原来的b 样条曲线( 2 8 ) 就可以用这组新 的b 样条基与新的控制顶点线性表出 1 0 ( 2 9 )叻“ 觑一r 州瑚 i i 妨“ 舭q ： 住 控制定点增加一个，曲线的形状及连续性均保持不变由b 样条曲线的局部 性质对于t h ，u + l 】，( 2 9 ) 式可以写成 并且 对于控制顶点有 b ，七( u ) = 扇岛，七( 心) ( 2 1 0 ) j - - i - k，= 一奄 ，七( 缸) = 砖 ( 缸) 0 = 0 ，l 一七一1 ) ，奄( 钍) = 岛“蠢( 锃) 0 = i + 1 ，铭) 弓= 扇( 牡) ，( j = 0 ，i 一七一i ) = b + 1 ( 仳) ，0 = t + 1 ，扎) ，七( u ) ，歹= i 一七，t 可以被岛，七( t 1 ) ，歹= i 一七， + 1 表示为： “缸) 2 景奶“锃) + 毒篙岛+ ， ( 珏) 将( 2 1 1 ) 代入( 2 i o ) 得 ( 嚣七( u ) + 巍藏- k + l , k ( u ) ) 只对 ( 盂兰蔫厩- k + l , k ( u ) + 石= = 篙藏一七+ 。，七) 最一知+ t + + ( 景厩刷+ 罴七) 只 一i 7 ；f 一七只一七+ + 7 ：f + 1 只+ l 依上式，并且用u 代替驴，移项合并同类项得： 藏一七( 缸) ( 最一七一只一七) + n i - k + l ( 仳) ( 晟一七+ - 一瓦_ , u + 。- 一u 他- k 一+ 知l 石只- k + l - - 瓦_ + 。+ 一1 啦- 一u 七+ 。p i 一七) + + 厩( 牡) ( 扇一瓦u 一- 强p i 一嚣蒿兰只一七) + 藏+ 1 ( 乜) ( 晟+ 1 一只= 0 1 1 ( 2 1 1 ) 关于圆盘b 样条曲线插值及节点插入问题的研究 由b 样条基函数的线性无关性以及上式可得经过节点插入算法给出的新顶点的 计算公式： 岛= 弓，歹= 0 ，i k 马+ 1 = ( 1 - 面u 七+ - 1u j + 嘶a + 1 ) p j + 丽u 七+ - - 1 让一j + 吻l + 1p j + l ，歹= 一，t r 弓= 马一1 ，j = i r + 1 ，n + 1 其中r 为新插入的节点在老节点矢量中的重复度这个算法实质上德布尔算法的 第一级递推 当把同一节点u 重复插入1 次，而该节点在老节点矢量中又可能是r 重的，则必 须使t + z k b o e h m 将插入一单个节点算法推广用来插入一个重节点重复 插入同一节点f 次的算法实质上就是执行求b 样条曲线一点的德布尔算法f 级递 推当z + r = 七时，可求出b 样条曲线上参数为插入节点值得一点，实际上这就是 计算b 样条曲线上一点的德布尔算法 2 5 2b o e m h 节点插入算法的数值实例 b 样条曲线的原控制顶点取为p o = 【一2 4 ，0 1 ，p l = 【一1 2 ，6 1 ，恳= 【l ，8 】，b = 【1 0 ，2 】，只= 1 2 ，o 】，节点矢量为u = 【0 ，0 ，0 ，0 ，o 7 5 ，1 ，1 ，1 ，1 】此b 样条曲线的次数 为3 ，如图4 我们首先插入一个节点乱= 0 5 后，按上面给出的算法处理后得到 新的控制顶点为p o = - 2 4 ，o 】，尸1 = - 1 6 ，4 】，忍= 【- 5 5 ，7 0 】，忍= 【5 5 ，5 0 】，只= 【1 0 ，2 】，忍= 【1 2 ，o 】，节点矢量变为u = 【0 ，0 ，0 ，0 ，0 5 ，0 7 5 ，1 ，1 ，1 ，1 】，实例效果如 图5 所示我们这里再次重复插入节点毡= 0 5 后，得到的新的控制顶点为p o = 【- 2 4 ，o 】，p l = 【- 1 6 ，4 】，b = 【- 9 ，6 】，尼= 0 ，6 ，只= 5 5 ，5 o 】，p 5 = 1 0 ，2 】，r = 【1 2 ，o 】，节点矢量变为u = 【0 ，0 ，0 ，0 ，0 5 ，0 5 ，o 7 5 ，1 ，1 ，1 ，1 】，实例效果如图6 所示 再次插入节点让= 0 5 后，得到的新的控制为p o = 一2 4 ，o ，b = 【1 6 ，4 】，p 2 = 【- 9 ，6 】， 3 = i - 3 ，6 ，只= 【0 ，6 ，p 5 = 【5 5 ，5 0 】，r = 【1 0 ，2 】，马= 【1 2 ，o 】，节点矢量 变为u = f o ，0 ，0 ，0 ，0 5 ，0 5 ，0 5 ，o 7 5 ，1 ，1 ，1 ，1 】最后一次插入节点0 5 后，得到新的 控制顶点恳= f 一3 ，6 1 就是经过德布尔递推算法得到的尸( o 5 ) 点的值 1 2 关于圆盘b 样条曲线插值及节点插入问题的研究 图4 未插节点前曲线 图5 插入一个节点情况 图6 插入两个节点情况 图7 插入三个节点情况 1 3 关于圆盘b 样条曲线插值及节点插入问题的研究 3圆盘b 样条曲线 在( 1 2 ) 中已经叙述了区间算术的引入对于曲线在实际计算和应用中的很多 优点，接着也叙述了圆盘算术的引入有优于区间算术的地方本章首先引入了 圆盘算术，接着主要介绍了圆盘b 样条曲线的定义及性质酬，最后给出了计算圆