（应用数学专业论文）空间曲线的高阶几何hermite插值.pdf

摘要 本文在给定空间曲线两个端点的位置、切方向、曲率法 向量和挠率的情况下，用参数化五次b 6 z i e r 曲线来对这条空 间曲线进行几何h e r m i t e 插值。我们证明了插值问题局部可 解，解有两个自由度，而且本文还给出了一种确定这两个自 由度的方法。并证明了在适当的假设下插值有6 阶逼近度。 关键词：几何连续；插值；逼近度；曲率法向量；挠率；t g h i 中图法分类号t p 3 9 1 4b s t r a c t t h i s p a p e r u s e sp a r a m e t r i c q u i n a r yb 6 z i e r c u r v et oi n t e r p o l a t e ag i v e ns p a c i a lc u r v e ，w h o s ep o s i t i o n ，t a n g e n td i r e c t i o n 】t h ec u r v a t u r ev e c t o ra n dt o r s i o na r ep r e s c r i b e da te a c hk n o t w ep r o v et h a t t h ei n t e r p o l a n te x i s t sl o c a l l yw i t ht w od e g r e eo ff r e e d o m ，a n dw e g i v eam e t h o d t of i xt h et w o f r e e d o m m o r e o v e r ，w ep r o v et h a tu n d e ra p p r o p r i a t ea s s u m p t i o n st h ei n t e r p o l a n ti s6 t ho r d e ra c c u r a t e k e y w o r d s ：g e o m e t r i cc o n t i n u o u s ；i n t e r p o l a n t ；a c c u r a c y ；c u r v a t u r ev e c t o r ；t o r s i o n ；t g h i 3 致谢 在这里我要感谢我的导师曹沅老师，本文是在他的悉心 指导下完成的。并且，在研究生阶段的学习中，曹老师的谆 谆教诲让我获益匪浅，老师的无微关怀也让我将永远记住这 段求学的快乐时光。同时，也要感谢吴宗敏老师给这篇文章 的初稿提出宝贵意见，吴老师的帮助和教导也深刻的影响着 我。 我还要感谢在讨论班上，史建红、葛焰明、阎艳、李成、 王建华、陈荣华、熊正超、张立伟、张卫祥、杨艳、卜天奇等 同学提出的宝贵意见。我还想说的是，跟曹老师、吴老师以 及以上同学和朋友们在一起学习的时间我将永远记得，因为 这是我最难忘的时光。 预备知识 lh e r m i t e 插值 曲线插值是c a g d 中一类基本而广泛的闽题，而多项式插值是所有插值中 最基本的、应用最广泛的方法( 最早的多项式插值方法可能应该归功于i n e w t o n ) 。曲线设计的一个最普通的问题就是点插值问题：给定一列相对于参数t 。 的数据点p i r 4 ，i = 0 ，n ，需要找到一条曲线通过p t 。解决这个问题的 最早的方法就是找到一条多项式曲线通过这些点，这个多项式必须满足下面这些 插值条件： p ( 如) = p 。；i = 0 ，n 对这个问题已经有多种解决方案，比如： a i t k e n sa l g o r i t h m ，l a g r a n g ep o l y n o m i a l s ，t h ev a n d e r m o n d ea p p r o a c h 等等。在实际应用中，多项式播值不一定只能 插值点上的函数值，也可以插值别的一些信息，比如某些点上的导数信息，这样 就得到一个比一般的多项式插值更有用的插值方法，我们称之为h e r m i t e 插值。 在这里我们讨论两个节点的一般情形的h e r m i t e 插值：给定两点p o ，p ，以及 两端的各阶导数玮，p ，i = 1 m ，j = 1 m 。( 不失一股陛，我们设t o = 0 ，t l = h ) 我们需要找到一个多项式p 插值这些数据； p ( o ) = p o ， p ( h ) = p l ， p ( ( o ) = p j ，i = 1 m p ( ，) ( ) = p ，j = 1 n 其中p ( 4 】指p 的i 阶导数。我们记n = 仇+ n + 1 ，上式共有n + 1 个插值条 件，它可以确定n + 1 个系数，所以一般情况下满足这些插值条件的多项式p 的 最小次数为n ，而且该多项式唯一。 2 我们把多项式p 写成b 6 z i e r 形式，则必须确定n + 1 个b 6 z i e r 控制点b o ，b _ v 。 其中两个能够很快确定： b o = p o ，b n = p 1 对余下的控制点，我们利用多项式b g z i e r 形式的导数特点： ，n - k p 忙( t ) = ( eb ；b 。_ ( t ) ) = 去。b 。b 。，n 一( t ) i = 07 。i = 0 其中，县蛹( t ) = ( ? ) ( ；) ( 1 一；) ”2 ，a ：= a k - 1 b 件l a k - 1 b ：，o b ，= b 。由 此，我们很容易解出b ，b 一t ，从而确定了这条多项式插值曲线。 设原睦线为，( t ) ，则上面的h e r m i t e 插值有如下的误差估计： ，。) 一p ( t ) = 币矿 可，( 十u 嬉) t “十1 。危) “+ i ，【0 ，叫 于是， l f ( t ) 一p ( t ) l = o ( h n + i ) ，t 0 ，h 容易看出，高阶的h e r m i t e 插值能得到高阶的精度。 2 几何连续 由于曲线参数选择的不唯一，某条曲线可能在一种参数下是一阶连续，而在 另一种参数下却是两阶甚至多阶连续事实上，存在这样的曲线，它的曲率连续 但却不是两阶连续( 详情请参考 1 的1 2 章第一节，p 1 5 1 1 5 2 ) 。为了描述这 种情况，我们引入几何连续的概念，有很多文章都有关于几何连续的定义，也有 的叫视觉连续( v i s u a lc o n t i n u i t y ) ，但实际上只有两种意义上的连续，一种是 “n 阶接触”，另一种是“几何不变量连续” 设z = z ( t ) 是r d 中的一条合成曲线，z 一表示曲线某段的右端，而z + 表 示相邻段的左端。在连接点z + = z 一处的局部n 阶连续可以写成： 3 zz 7 z ( “ + = zz z ( “) 也可以简写成 x 十= x a( 1 ) 上面给出的上三角阵a 叫做“连接矩阵”，而d x + 1 ) 的矩阵x 有时叫做z 的n - j e t 上述两种连续主要的区别在于连接矩阵a 的不同，而这些不同影 响了曲线的代数或几何的性质。 设z ( t o ) 为要考虑的点，其中t o = 0 。把重定义的参数作如下t a y l o r 展开， ， t = j 。 。so 【a t + j z t 2 + ；，y t 3 + t o 则连接矩阵a 的元素很容易通过求导的链式法则得到。这时，满足( 1 ) 的瞌线 就在连接点z + = z 一处有n 阶接触比如：当n = 3 时 a 3 = 1ooo a 口7 o t 2 3 a b q 3 注意到当r 0 ，使得v 0 0 于是 b l = ? o 画，b 4 = b s l l d l( 2 ) 由定义，有 硒= ；半 = ；竿 3d o a b l a b 2 ，。、 丁0 2 瓦1 i 死盯 n = 壶觜 n 2 瓦1 砺再矿 由引理，存在u o ，u l 使得 a b l = u o d o - 4 - ! - 1 2 k o d o ( 5 ) a b 3 = 仳d l 一帮h d l ( 6 ) 由( 2 ) 、( 5 ) 和( 6 ) 可得 6 2 = ( 蛳+ 2 0 ) 面+ ；略岛如 ( 7 ) 6 3 = b 5 一( 虮+ 1 1 ) d l + ；日衄d l ( 8 ) 又因南= k l d l = 0 ，有 - a b 2 = b 3 ，兢b 2 = h ( b s 一6 2 ) 代入( 3 ) ( 4 ) 得可解条件 j 西2 5j 0 0 3 i 1 2 = 6 5 一沁l + f 1 ) 血+ ；瑶岛d 1 r 9 1 【西2 5 ，- 。3 。f h4 2 = 赶 砘一( u o - 4 - l o ) d o 一；略画】 事实上，如果2 0 ，1 1 ，7 - t 0 ，“- 满足( 9 ) ，则( 2 ) 、( t ) 和( 8 ) 8 给出t g h i 问 题的解。 下面就根据方程( 9 ) 的特点分几种不同的情况来讨论方程的解。 2j 若- d l 0 且k l d o 0 此时，任给定一组l o 0 ，2 l 0 都可得“o ，u l ，方程有解，且解有两个自由 度，于是证明了 定理1 ：如果d l 0 且凫l d o 0 ，则t g h i 问题有解，解由( 7 ) 一( 9 ) 给出，且有两个自由度。 为了确定这两个自由度，让播值表现出比较好的特性，而又不增加过多的计 算量，我们这里假定原曲线和插值曲线的参数札和t 之间存在简单的线性关系， 即珏= a t + b ，n ，b r ，考虑到乱 o ，h 】，t ( 0 ，1 j ，则有a = h ，b = 0 ，我 们记u = 西( t ) = h t ，希望在这个参数变换下，插值曲线与原曲线的接触能达到 e 1 ，也就是( i o 咖) ) = 6 7 ( t d ，i = o ，1 ；t o = 0 ，t l = 1 ，则f o = e ( o ) i h 5 ，f l = v ( h ) m 5 ，此时方程的解唯一确定。从后面第5 部分的例子可以看出，这种确 定自由度的方法一般都能得到比较满意的结果。 2 2 若岛d l 和k 1 一d o 中至少有一个为0 2 2 j 岛- d l = 0 ，赶- 南0 此时可解条件为，- 6 5 不全为0 ，且s 细礼( ，k l ，d 1 ) = s i g n ( t o ) 或 s i 妒( k o ，k l ，d 1 ) = - s i g n ( k o b s ) 这时只要找出一个合适的1 1 ，使得据( 9 ) 的 第一式解出的l o 0 ，然后把解得的f o ，2 t 代入( 9 ) 的第二式，可得u o ，再任意 指定一个l ，就得到方程的解。 2 22 d l 0 ，h 面= 0 9 此时可解条件为f l ，南l b 5 不全为0 ，且s i g n ( k 1 ，画) = 一s i g n ( 1 ) 或 s i g n ( k 1 b 5 ) = s i g n ( k l ，岛，d o ) 。这时只要找出一个合适的l o ，使得据( 9 ) 的第 二式解出的f ， 0 ，然后把解得的2 0 ，j t 代入( 9 ) 的第一式，可得u 1 ，再任意指 定一个钍o ，就得到方程的解 22 0 - d l = h - 如= 0 此时( 9 ) 式化为 i 西2 5 0 3 i 岛f 2 = b 5 + 粒南l d 1 i 西2 5 3 1 i h l2 = k l 6 5 一；培d o 】 此时方程组或者无解，或者解不易显式给出但在接下来的定理3 说明我们 可以细分这个问题，对任意一条挠率不为0 的曲线，都可以找出一条分段五次 b 6 z i e r 曲线满足g c 3 一条件。 3 插值解的存在性 设r = “s ) ，s 0 ，f 】是一条光滑曲线，其中s 为弧长参数。考虑t g h i 问 题，记 b o = “o ) ，如= 一( o ) ，岛= 知( o ) ，叼= 丁( o ) b 5 = r ( ) ，d l = 一( ) ，矗l = 知( 危) ，n = _ ( h ) 当h 足够小时，插值可看成是对原曲线r = r ( s ) ，8 0 ，h 】的一个逼近。我们把 r = r ( 8 ) 在s = 0 处展开，有 巾) = d s + 去，s 2 + 扣“o ( s 4 ) 其中“。) = 扣1 ( o ) ，i = 1 ，2 ，3 。因8 为弧长参数，所以i 一( s ) = 1 ，一( s ) 一( s ) = 0 ，于是有 愚( s ) = 一( s ) 一( s ) = 一一+ 一一，s + 刍( ，一+ 一，) s 2 + o ( s 3 ) 1 0 由t a y l o r 展式，我们得到 1 ，d l = 去( 一，一，一”) 2 + o ( m ) 1 k ，d o = ；( 一，一7 ，一”) 2 + p ( 3 ) 如果挠率0 ，则( 一，一，) 0 ，于是k 1 d o 0 ，d - 0 ，由定理1 ， 该插值问题有解于是得下面结论： 定理2 ：设r = r ( u ) c 6 o ，目在i t = 0 处挠率不为o ，则存在h 0 ，使得 v o 0 b ( 1 ) = r ( 危) ，6 ，( 1 ) = 6 1 一( h ) ，d l 0 =6 即) 6 ( o ) i b ( o ) 1 3 ：! ! ! ! 兰! ! ! ! l , q o ) 1 3 等铲= 帮 = 帮= 鬻瓣 n = 喘黼= 端瓣 因“s ) 在s = o 处挠率不为0 ，则一( o ) 0 ，6 ，( o ) 0 ，不失一般性我们设 , f r o ) 的第一个坐标不为0 ，即x ( o ) 0 ，则当h 足够小时，咒( s ) ，sc - o ，剜 可逆，而且我们可以证明，在一定条件下，z ( t ) ，t 0 ，1 】也可逆。 事实上，我仃 需要证明。协) 0 ，v t f 0 ，1 j 。因 6 ，( t ) = 5 a b i b i ，4 ( t ) ，t ( 0 ，1 】 4 = d 于是我们只需证明系数a b , ，i = 0 ，1 ，2 ，3 ，4 ，都同号从第二部分的讨论我们有 b o = l o d o a b l = u o 面+ ；l ：d d a b 2 = b 5 一a b , 。甾4 a b a = u l d 1 一翔h d l 1 2 d 4 = h d l 如果记c o = u o h ，1 l = u l h ，“o 0 ，呐 0 ，经过一些计算我们可得 a b o u o 危一+ o ( h 2 ) 曲- ：( 2 6 w o + 1 5 u ；一2 5 u ；) 一十o ( h 2 ) 6 2 ；( 2 1 5 u ；一1 5 u 1 2 + 2 5 u j + 2 5 u i ) 一十o ( 2 ) 6 3 _ ：( 2 6 w l + 1 5 u 一2 5 u 3 ) 一+ o ( 危2 ) a b 4 ( 1 一u 1 ) 一+ o ( h 2 ) 于是我们证明如果 2 6 w o + 1 5 w 3 2 5 w 0 2 1 5 u 3 1 5 ( = 2 + 2 5 ：o + 2 5 u o ( 1 0 ) 2 6 “i + 1 5 w ；一2 5 “3 0 4 l 一“1 0 ( 容易看出，这个条件比较容易满足，只要u o ，u - 足够小，e g u o = u z = 1 5 ， 就可以满足) ，则z ( t ) ，t 0 ，1 可逆，当h 足够小时。 现在我们通过参数化来证明逼近度。记 b 心) = f ，口暗) ，2 ( f ) ，r 任) = f ，y 幢) ，z 心) 】， 矗，- j 其中0 = y ox ，2 = 。0 x ，y = y0 x _ 。，z = zo x ，z _ 1 ，x _ 1 分别表示 z ( t ) ，x ( s ) 的反函数，o 表示函数的合成，= z 。x - 1 ( ) = x 。x _ 1 ( ) ，岛= x ( o ) = x ( o ) ，l = x ( 1 ) = x ( h ) 。由链式法则，有 鬈= 多，塞= 耸笋幽( ，+ ( 多) 2 + ( 势峦 z 一 峦2( 口) 3 “。、1 。、z ，。z 一7 其中女3 为曲率法向量凫的第三坐标，类似可得d 2 d f ，d ? d ，d 2 d f ，d 2 l 必2 ，d 2 p 蜒2 ，d 2 2 蟛 根据插值条件容易验证 丑( 4 ) ( 白) = r ( ( 6 ) i = 0 ，1 ，2 ，j = 0 ，1 上面的计算我们假设r = r ( s ) 是光滑的，事实上g 6 就够了。因一( t ) 0 ，刀( s ) 0 ，容易看出口( 6 ，置( 6 ( ) 在嗡，1 上一致有界，又因f f l 一岛i = o h ) ，则由两点h e r m i t e 插值的标准估计可得 i 曰( 妁一冠( ) = o ( h 6 ) ，f j 由此，再考虑到定理2 我们得到： 定理4 ；设曲线r = r ( u ) ，u c 6 【o ，l 】在= 0 处挠率不为0 ，则存在 h 0 使得v 0 h h ，t g h 问题有解，解有两个自由度。如果当条件f 1 0 ) 被满足时，则插值解有6 阶精度 5 例子 在这个部分我们通过对两个例子使用我们的方法插值来展示我们的方法。为 了方便地与以往的方法进行比较，我们在例1 中取与徐良宏所用的相同的圆柱 螺线。因为在徐的文章中知道，他的方法能够得到比h s l l i g 和k o c h 的方法更好 的结果，所以在这里我们只与徐良宏所用的g h i 方法进行比较。 例1 ：给定圆柱螺线 r ( 乱) = ( c d s ( 让) ，s i 扎( 乱) ，豇1 “( 0 ，7 r 2 两端的切向、曲率法向量和挠率，用上述方法进行插值( 其中取f o = 2 。= 7 r 1 0 ) ， 图1 , 2 分别给出两种方法下曲线、曲率和挠率的误差 1 4 图1 ：左图为曲线误差，右图为瞌率误差 图2 ：挠率误差 从上面的例子看出，t g h i 方法与g h i 方法相比能够更好的逼近原曲线， 并且在曲率和挠率方面也能够达到更好的精度因为圆柱螺线的挠率为常数，为 了验证我们的方法的普遍适应性，我们尝试用挠率有一定变化的曲线来应用我们 的方法。于是我们在这里引入圆锥螺线。 例2 ：给定圆锥螺线 一w ) = p c d s ( 口) ，v s i n ( v ) ，u 0 ，r 4 15 两端的切向、曲率法向量和挠率，用上述方法进行插值( 其中取l o = l 一( o ) i 丌2 0 ，l l = i 一( ：) i7 r 2 0 ) 图3 ，4 给出曲线、曲率和挠率的误差 图3 ：左图为曲线误差，右图为曲率误差 图4 ：挠宰误差 例1 和例2 中f o ，j l 都是用21 的方法给定，从结果可以看出，这种确定的 自由度的方法能够得到比较满意的效果从而与徐的g h i 方法中自由度的难以 确定相比，本文的方法更容易在实践中得到应用。 1 6 参考文献 【l 】g e r a l df a r i n ，c u r v e sa n ds u r f a c e sf o rc o m p u t e ra i d e dg e o m e t r i cd e s i g n ，a c a d e m i cp r e s sh c 1 9 8 8 f 2 】b o e h m ，w ，l e t t e rt ot h ee d i t o r ，o nt h ed e f i n i t i o n o fg e o m e t r i cc o n t i n u i t y c o m p u t e ra i d e d g e o m e t r i cd e s i g n j ，1 9 8 8 ，2 0 ( 7 ) ：3 7 0 3 7 2 【3 】d eb o o r ，c ，h s l l i g ，k a n ds a b i n ，m ，h i g ha c c u r a c yg e o m e t r i ch e r m i t ei n t e r p o l a t i o nc 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 j ，1 9 8 7 ，4 ( 4 ) ：2 6 9 - 2 7 8 【4 】w u ，z h o n g m i n ，h u a n gy i ，g 0 2h e r m i t e i n t e r p o l a t i o nb yr a t i o n a lc u b i c n u m e r i c a lm a t h e m a t i c s aj o u r n a lo fc h i n e s eu n i v e r s i t i e s ( s p e c i a li s s u ef o rc o m p u t a t i o n a lg e o m e t r y ) i j i ，1 9 9 3 ：9 8 1 0 3 ( 吴宗敏黄毅，参数有理三次插值高等学校计算数学学报( 计算几何专集) 1 9 9 3 ：9 8 1 0 3 ) f 5 h s l l i g ，k ，k o c h 3 ，g e o m e t r i ch e a i t ei n t e r p a l a t i o nc o m p u t