（计算数学专业论文）平面上散乱数据的分片代数曲线拟合.pdf

大连理工大学硕士学位论文 摘要 基于大规模散乱数据的插值或拟合方法，在很多领域都有重要的应用。所以长期 以来，有很多学者从事这方面的研究，并且发展和形成了许多方法。本文产用分片代 数曲线来拟合散乱数据点，采用最小二乘法来计算其最佳逼近。 自王仁宏在1 9 7 5 年提出了多元样条的理论，采用经典的代数几何中的方法发展了 多元样条理论。并给出了一些基本空间的基函数组。此篇论文采用霹( 漱) 样条空间 的分片代数曲线来做散乱数据的拟合，我们由其空间的一组基函数可以确定样条函数 函数。运用最小二乘法建立一目标函数。同时为了更好的拟合效果，在目标函数中可 以加入一些其它项，例如切向，法向和能量。同时也可以对一些点进行一些限制，可 以要求某些点严格经过此分片代数曲线。而一些点在其上部或下部。这样，问题就变 成求解非线性约束优化的最优化问题。同时我们知道多元样条空间的结构还依赖于 其剖分的性质，因此为了达到更好的拟合效果，我们可以逐渐的加细剖分。 因为分片代数曲线是一种隐式曲线，因此其具有隐式曲线的所有优点，计算简 单。同时又可以通过低次的曲线即可达到较好的拟合效果。 本文运用了大量实例来验证此算法，都收到了比较好的效果。 关键词：散乱点拟合；分片代数曲线；母( 瓣) 空间；最优化问题 平面上散乱数据的分片代数曲线拟合 f i t t i n gp i e c e w i s ea l g e b r a i cc u r v et os c a t t e r e dd a t ai nap l a n e a b s t r a c t t h ep r o b l e mo fc o n s t r u c t i n ga p p r o x i m a t i o n sb a s e du p o ns c a t t e r e dd a t ai se n c o u n - t e r e di nm a n ya r e a so fs c i e n t i f i ca p p l i c a t i o n s s om a n ys c h o l a r sh a v eb e e nr e s e a r c h i n g a b o u tt h i st o p i ca n dd e v e l o p e dm a n ya l g o r i t h m s w ep r e s e n t s8 2 1a l g o r i t h mu s i n gt h e p i e c e w i s ea l g e b r a i cc u r v et oa p p r o x i m a t et h es c a t t e r e dd a t a ，a n du s i n gt h el e a s t s q u a r e s m e t h o dt oc a l c u l a t et h eb e s ta p p r o x i m a t i o n s r e n h o n gw a n ga d v a n c e dt h et h e o r yo ft h em u t i s p l i n e ，a n du s i n gt h ec l a s s i ca l g e b r a i cg e o m e t r yt od e v e l o pt h em u t i s p l i n ei n1 9 7 5 a f t e rt h a t ，h ea n dh i ss t u d e n t s g a v et h eb a s ef u n c t i o n so ft h ek i n d so fs p l i n es p a c e w ea d o p tt h es p i n ef u n c t i o no f t h es p a c e ：母( 彻c 1 ) ，u s i n gt h el e a s t - s q u a r e st oc r e a t eao b j e c t i v ef u n c t i o n a tt h es a m e t i m e ，w ea l s oc o n s i d e r e do t h e ri t e m s ，s u c ha st h ea s s o c i a t e dn o r m a l sa n dt a n g e n t s ，a n d p o i n t sc o n s t r a i n t s ，t h ee n e r g yt e r mi sa l s oc o n s i d e r e di nt h em e t h o d a sar e s u l t ，w e g e tt os o l v eao p t i m i z a t i o np r o b l e m w ec e i lg e tab e t t e rr e s u l tb yf r a c t i o n i z i n gt h e p a r t i t i o n b e c a u s et h ep i e c e w i s ea l g e b r a i cc u r v ei si m p l i c i t l yd e f i n e dc u r v e s ，t h i sm e t h o di s c o m p u t a t i o n a ls i m p l e ，a n dt h em a i na d v a n t a g ei st h a tt h ed e g a so fc u r v e 8a r el o w e r c o m p a r e dw i t ho t h e rm e t h o d s t h en u m e r i c a le x a m p l e si nt h i st h e s i ss h o wu st h e s em e t h o d sa r ef e a s i b l e ，a n dt h e r e s u l t sa r es a t i s f y i i l g k e yw o r d s ：s c a t t e r e dd a t af i t t i n g ，p i e c e w i s ea l g e b r a i cc u r v e ，$ 3 1 ( a 璺) ) s p a c e ， o p t i m i z a t i o np r o b l e m i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名獬日期： 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连理工大学硕士、博士学位 论文版权使用规定 ，同意大连理工大学保留并向国家有关部门或机构送交 学位论文的复印件和电子版，允许论文被查阅和借阅本人授权大连理工 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可 采用影印、缩印或扫描等复制手段保存和汇编学位论文 作者签名：受趁碜 导师签名：二垃 越馑月上日 大连理工大学硕士学位论文 引言 基于大规模散乱数据的插值或拟合方法，在很多领域都有重要的应用。所以长期 以来，都有很多学者从事这方面的研究，并且发展和形成了许多方法。在计算机辅助 几何设计( c a g d ) 领域中，熟知有两种定义曲线曲面的方法，即参数形式与隐式形 式。参数形式的曲线与曲面以其设计简单，容易计算等特点而流行与世并成为几何设 计的主流，由此使人们产生隐式形式不实用的感觉，然而研究与使用经验表明，实际 情况并非如此，即对于c a g d 中的许多问题，隐式形式同样或更为方便有效。本文即 研究一种隐式曲线：分片代数曲线用于曲线拟合。与参数形式的曲线，用分片代数曲 线( 隐式形式) 的优点为：隐式形式有更多的自由度，因而在同样次数的情况下，隐 式形式可达到更高的光滑度或提供更多的形状控制的手段；作为解析曲线的子集，隐 式形式提供了足够的灵活性使其几乎可以拟合任何复杂形状的曲线；隐式曲线不仅有 紧凑的表达形式而且具有几何运算下的封闭性。任何参数形式形式或隐式形式的曲线 之间的几何运算( 求和，求差，或交以及偏移( o 蠡e t ) ) 的结果均可表成隐式形式； 另外，隐式形式定义一个半空间，因而十分容易区分一个点是在曲线的内侧或外侧 或在曲线之上。这样的判定是检测空间中两个物体是否碰撞的基础。文献 1 2 】- 2 2 】都 是运用隐式曲线曲面拟合散乱数据的。这些研究主要是用低维分支( 系数满足给定 条件保证结果的拓扑性质) 。j u t t l e r 用隐式定义的张量基样条曲线曲面拟合散乱数 据。w a n g y a n g 用隐式定义的张量基样条曲线曲面拟合b l e n d i n g ，这些方法计算简单， 但是要求高阶的曲线曲面。因为分片代数曲线是一种隐式曲线，因此其具有隐式曲线 的所有优点，计算简单。同时又可以通过低次的曲线即可达到较好的拟合效果。朱 春钢在文f 4 1 产用基于样条空间熨( 激) 的分片代数曲线来拟合散乱数据。本篇论文产 用鼹( 黝) 空间的分片代数曲线来拟合平面上的散乱数据。最后给出大量的数值例子 证明其可行性。 1 平面上散乱数据的分片代数曲线拟合 1 曲线拟合的相关介绍 1 1 曲线的隐式形式和参数形式 与参数形式的曲线曲面性比，隐式形式具有如下优点：隐式形式有更多的自由 度，因而在同样次数的情况下，隐式形式可达到更高的光滑度或提供更多的形状控制 手段，隐式形式提供了足够的灵活性使其几乎可以拟合任何复杂形状的曲线与曲面。 通过参数的消去我们知道，参数形式是隐式的特例，任何参数形式的曲线曲面均可 以表达成隐式形式。隐式形式不仅具有紧凑的表达形式而且具有几何运算下的封闭 性。任何参数形式或隐式形式的曲线曲面之间的几何运算( 求和、求差或交易即偏移 ( o f f s e t ) ) 的结果均可表成隐式形式。参数形式便没有这个特点，比如参数曲线的偏 移( o f f s e t ) 不能表成参数形式。因此，如果一个几何设计系统不能包容隐式形式，那 么上述运算便超出它力所能及的范围。另外，隐式形式定义的是一个半空间，因而十 分容易区分一个点是在曲线或曲面的内侧或外侧或在曲线曲面之上。然而隐式形式有 若干不利于使用的缺陷，其中包括：( 1 ) 计算不如参数形式简单，因为隐式形式的 曲线曲面由多项式的零点定义，所以求值隐式曲线曲面原则上等价于解一个非线性方 程；( 2 ) 隐式曲线曲面可有奇异性；( 3 ) 隐式曲线曲面有多分支性。所以c a g d 中使 用隐式曲线曲面所要研究的关键问题是如何发挥其优点，克服其不足。 1 2 曲线拟合的方法介绍 自由曲线，曲面因其复杂性不易由画法几何与机械制图等简单方式表达清 楚。1 9 6 3 年，美国波音公司的弗格森首先提出了将曲线曲面表示为参数的向量函数 方法。从此，参数形式成为自由曲线曲面数学描述的标准形式。法国雷诺汽车公司 的b e z i e r 在1 9 7 1 年发表了一种由控制多边形定义曲线的方法。设计者可以通过移动控 制顶点来控制曲线的形状，而且还可以预料曲线形状的变化。b e z i e r 方法简单易用， 得到了广泛的应用。德布尔( d eb o o r ) 于1 9 7 2 年提出了关于b 样条的一套标准算法， 随后美国通用汽车公司的戈登( g o r d o n ) 和里森费尔德将b 样条理论用于自由曲线 曲面的描述。b 样条方法继承了b e z i e r 曲线曲面的优点，并克服了b e z i e r 方法在局部控 制等方面的不足，成为构造自由曲线曲面的主要工具。而b e z i e r 曲线曲面由于其简单 易用，亦成为分段，分片的b 样条曲线和曲面的主要表示形式。美国s y r a c a u s e 大学 的福斯普里尔1 9 7 5 年首次提出了有理b 一样条方法，该方法后来发展为均匀有理b 样条 ( n u r s e ) 方法。近年来，隐式曲线曲面也有很多人研究。分片代数曲线是二元样条 的零点集合。 2 大连理工大学硕士学位论文 1 9 7 5 年，王仁宏采用函数论与代数几何的方法，建立了任意剖分下的多元样 条函数的基本理论框架，并提出所谓的光滑余因子协调法( 1 】，并给出了部分空间 的维数与基底。由此可求出满足一定条件二元样条的表达式，进而可得到分片代 数曲线。而关于曲线曲面的拟合已有很多人从事此方面的研究。p r a t t 提出若干种 拟合技术( 包括精确拟合一插值，简单拟合最小二乘，球面拟合以及混合拼接拟 合) ，这些技术考虑使用一个曲面片拟合给定的数据，其合成的曲面的光滑性未 予考虑。d m o o r e 和j w a r r e n 使用最小二乘技术及分片隐式曲面拟合稠密的曲面数 据，c a r r e t a l 用多重调和的径向基函数从点云数据和不完全网格重构光滑的流型曲 面。p r a t t 和t a r e l 介绍的曲线和曲面拟合的方法是基于代数距离，数据的梯度。其方 法通过限制了数据梯度的二次方的和保证了几何不变量平方的标准化。b a j a j 和x u 发展了用a 一样条作为有利的工具对给定测量数据重构曲线和曲面，这些研究主要 是用低维分支( 系数满足给定条件保证结果的拓扑性质) 。j u t t l e r 用隐式定义的张 量基样条曲线曲面拟合散乱数据。w a n g f a n g 用隐式定义的张量基样条曲线曲面拟 合b l e n d i n g ，这些方法计算简单，但是要求高阶的曲线曲面。 1 3 对于点云的处理 在反求工程中所获取的测量数据一般是无序的，而且采样密度非常稠密，因此， 我们无法也无需找到一条曲线使之通过所有的采样点。我们可以先将其进行细化。然 后再用分片代数曲线进行拟合。 对于细化点集，可产用移动最4 - - 乘法( m l s ) 1 3 1k 一近邻搜索 散乱点集内某点的局部形状仅与该点邻域内的点有关【5 1 。因此，在运用m i s 方法 前，通过快速搜索k 一近邻，建立散乱点之间的局部邻接关系。本文给出的k 近邻快 速搜索算法借鉴文献 6 1 所提出的空间球搜索算法，将其应用于平面散乱点的k 一近邻搜 索。基本思想是采用逐步递加搜索平面栅格的策略，首先对数据点集进行平面栅格划 分，并计算测点到所在平面栅格四条边的距离，对距离进行排序。根据距离的大小确 定平面圆的半径，考虑不同半径的平面圆与哪些平面栅格发生干涉，结合搜索终止条 件，在发生干涉的平面栅格中进行搜索。该算法每次搜索平面栅格的个数与假想平面 圆的半径有关，建立对应的搜索终止原则，有效减少了搜索平面栅格的个数，提高了 算法效率。 3 平面上散乱数据的分片代数曲线拟合 1 3 2 建立邻域点集 建立上述k 一近邻结构后，就可以方便地搜索当前数据点p + 的有效邻域点集，用于 后续拟合局部回归曲线。搜索的基本方法是：通过k 一近邻搜索与点p 4 的之间的距离小 于某个距离阀值h 的所有点，作为p 的的局部邻域点集。为了使算法能适用于疏密不 均的散乱点集，引入了相关性概念用于计算一个变化的h 值来反映点云的不同稀疏程 度【7 】。 1 3 3 计算局部回归曲线 本文考虑r 2 空间内的点集p = p i = ( 娩，犰) ，i = 1 ，佗 ，对点集p 中的每一个数 据点分别按移动最小二乘法进行计算。 ( 1 ) 建立局部近似直线 由于点集在r 2 空间，l e v i n 5 提出局部近似超平面就退化为一条直线。所以对平面 散乱点集p 中的每一点p ( 鬈，片) 建立局部近似直线。令局部近似直线l + ：y = a x + b ， 可以通过计算下式得到 r a i ne a x t + 6 一玑) 2 w t i = l ( 1 1 ) 式中：m 为p 的局部邻域点的个数；伽t 是一个随与邻点距离的增加而急剧减小的非负函 数。 w i = e - r 2 胪 ( 1 2 ) 式中：r = 慨一p + i f 2 ；h 为邻域半径。对于式( 1 1 ) 的最小二乘解求解方法如下：分别对系 数a ，b 求偏导数，并令其为零，简化得到矩阵形式，即 瞪怒建搿w ) ( ：) = ( 鲶nw 剐 3 ， 竺。( 妣觑) 篓。t ) 7 、6 一，：，；玑) 卜“7 利用高斯消元法求解，便可得到点p 邻域点集的最小二乘拟合直线f 。 ( 2 ) 计算投影点的m l s 曲线 以p 为原点、与直线l + 平行的方向为x 轴建立新坐标系，齐次变换矩阵为 ，c o s 轨e 、 m = i s i n oc o s o 一弓l ( 1 4 ) oo1 式中：b 为局部回归直线l + 与坐标系x 轴的夹角。将p + 的局部邻域点集a 变换到该新 坐标系下，得到一个新的点集，记为p = 协= ( 或，矾，i = 1 ，m ) 然后用二次曲 4 大连理工大学硕士学位论文 线c + ：雪= 以2 + 砼+ c 来逼近尸，则曲线矿可由式( 1 5 ) 得到 m r a i n ：( + 6 甄+ c 一犰) 2 w i ( 1 5 ) i - - - - 1 求解式( 1 5 ) 的方法与式( 1 1 ) 类似，计算后即可得到曲线c 的系数a ，b ，c 。则p 点 在曲线c + 上的对应点的值为p = 户+ c + ( 0 ，0 ) = ( 0 ，c ) ，通过逆变换矩阵m 一， 将p + ( 0 ，c ) 转换至原坐标系下就可得到与p 4 对应i 构m l s 点。对点集p 内的所有点，计算 其对应的m l s 点，并移动至m l s 点，散乱点集得到细化。 1 4 最 b - - 乘法介绍 最小二乘法( l e a s ts q u a r e s ) 是最传统和最成熟的曲线和曲面逼近理论，它是工程 领域最常用的数值逼近方法之一。最t j 、- - 乘拟合以其计算简单和实用性的特点在反向 工程c a d 建模的曲线曲面逼近中扮演着重要的角色。根据研究目标对象的不同，最小 二乘方法可分为线性最小二乘法和非线性最小二乘法。本节主要介绍其方法的应用。 1 4 1 最, j 、- - 乘法 想。 参见 8 - 1 0 】 最小二乘法在曲线拟合中是非常有用且重要的方法。本文中即采用此方法的思 最小二乘法的基本方法如下：已知数据( 巧，f ( x j ) j 凳o ，在圣= s p a n 妒o ，妒1 ，) 中 确定一函数8 ( x ) 使得： 。 最小一、i 署, f f j 、卅m ：o 是权函数，均大于零。 最小- 乘解s ( x ) = 丝on 七的系数满足下面法方程的解： ( 妒o ，伽) ( 妒1 ，妒o ) ( q 0 n ，q 0 0 ) 妒0 妒1 q o o 妒1 妒1 妒1 q o o 妒l 妒0 峰n 肇n ： 节n 5 ( 1 6 ) 批引7 ， z ，j z k r z伽 m ：豆 平面上散乱数据的分片代数曲线拟合 其中内积为离散的内积： 二= ( ，g ) = w ( x y ( x j ) g ( z j ) ( 1 8 ) j = 0 当_ 愀) 楚。关于点集 ) 凳。满足哈尔( h a 甜) 条件时，则有法方程组存在唯一解向 量。 哈尔条件： ) 楚occ a ，6 的任意系数不全为。的线性组合在点集 ) 整o ( m 孔) 中至多有1 1 个不同的零点( _ ) 楚。是线性无关的函数组) 最小二乘法是一种数学优化技术，它通过最小化误差的平方和找到一组数据的最 佳函数匹配。最小二乘法是用最简的方法求得一些绝对不可知的真值，而令误差平方 之和为最小。最t j 、- - 乘法通常用于曲线拟合。很多其他的优化问题也可通过最小化能 量或最大化熵用最小二乘形式表达。 1 4 2 线性最小二乘法 线性最小问题的解x 又可称作线性方程组 血= ba r m n ( 1 9 ) 的最小二乘解。 根据m 和n 以及矩阵a 的秩的不同，最小二乘问题可分为不同的情形，这里给 出r a n k ( a ) = 1 1 ， ( i l ，j l ；z q ，i q ) =q p ( t l ，j 1 ) ，( i q , 九) 显然q luq 2 的基数是2 ( m + 2 ) ( n + 2 ) 一2 5 要多3 。所以集合 ( 2 2 6 ) ( 2 2 7 ) 它比空间砖( 瓣) 的维数2 ( m + 2 ) ( n + 2 ) 一 g = ( 饬1i ( i ，歹) q l ，u 璐i ( i ，歹) q 2 ) 是线性相关的。但是，要指出的是，g 是空i b ，一。1 、a ( i ) 。) 的一个生成集。 事实上，有更强的结果： 定理2 9集合 9 1 = 磁，磅i ( i ，歹) q 1 ( m ，佗+ 1 ) ，( s ，t ) q 2 ( 仇+ 1 ，佗；m + 1 ，他一1 ) ) 在区域d 上是线性无关的。 定理2 1 0 任意的f ( z ，可) 3 1 a ( 1 ) ；) 都可表示成下面的式子 f ( z ，) = 码( z ，y ) + 奶璐( z ，y ) ， ( i , j ) e n l ( i ，j ) q 2 此处c r n ，计l = d m + l ，n = d m + 1 ，n 一1 ( 2 2 8 ) ( 2 2 9 ) ( 2 3 0 ) = 0 ，层p q 。l 、a ( 1 ) 。) 中元素是9 1 中所有样条函数的组合。 其证明见 1 娜9 页 g ( 黝) 两个基函数的图如下： 引入记号 9 1 ( t l ，j 1 ；i 2 ，j 2 ；i 3 ，矗) = 9 2 ( i 1 ，歹1 ；i 2 ，如；i 3 ，如) = 1 ( t 1 ，j l ；t 2 ，歹2 ；i 3 , j 3 ) = 2 ( i 1 ，j 1 ；i 2 , 如；i 3 , 如) = 锡 磁 磁 磁 b 磊 磋 瑶 瑗 ( i ，j ) ( z ，j ) ( i ，j ) ( i ，j ) q 1 ( 雹1 ，j 1 ；i 2 ，j 2 ；i a ，j 3 ) ，( 8 ，t ) q 2 ) q 1 ，( 8 ，亡) q 2 ( i l ，j l ；i 2 ，j 2 ；i 3 ，j f 3 ) ) 1 ( i l ，j l ；i 2 ，j 2 ) ，( 8 ，t ) q 2 ( i 3 ，矗) ) q 1 ( 1 ，j 1 ) ，( 8 ，t ) q 2 ( z 2 ，歹2 ；i a ，如) ) 对于如何选取砖( 瓣) 的具有局部支集的基函数组由如下定理。 ( 2 3 1 ) 定理2 1 1 铲( i 1 ，j 1 ； 2 ，j 2 ；i 3 , 力) ( p = 1 ，2 ) 是s j ( 1 ) 的基函数，必须且只须( i l ，2 1 ) ，( i 2 ，j 2 ) 和( t 3 ，歹3 ) 三点不共线； 9 1 ( t 1 ，歹1 ；i 2 ，如；i 3 ，如) 是器( 1 ) 的基函数，必须且只须( i l ，j 1 ) ，( i 2 ，j 2 ) 和( i a 一2 , 3 ，如+ 2 3 ) 三- - 点不共线； 1 8 大连理工大学硕士学位论文 图2 5b 1 ( z ，y ) f i g 2 5b 1x ，y ) 图2 6b 2 ( z ，y ) f i g 2 6b 2 ( z ，y ) 1 9 平面上散乱数据的分片代数曲线拟合 警( z 1 ，j l ；i 2 ，j 2 ；i 3 ，如) 是母( 1 ) 的基函数，必须且只须( z 1 4 - 2 3 ，j 1 - 2 3 ) ，( i 2 , j 2 ) 和( i 3 ，j 3 ) - 三 点不共线； 证明见 1 中6 2 页。 2 3 分片代数曲线曲面 2 3 1 代数曲线 代数曲线，又称紧黎曼面。它是紧的2 维定向实流形，也就是复的一维流形。代 数曲线是代数几何中最简单的一类研究对象。 代数曲线曲面是交换代数及代数几何基础理论研究的对象。它们在数值逼近、多 元样条、计算几何以及c a g d 等领域也起着重要的作用。 代数曲线或曲面一般按隐式方式定义，即用一个代数方程或代数方程组来定义。 可以表示为有理参数形式的代数曲线或曲面称之为有理曲线或曲面。 2 3 2 分片代数曲线 用有限条直线，射线或线段对平面区域q r 2 进行剖分，于是6 2 ，n ，它们 被称为胞腔。 用p ( ) 表示上分片多项式构成的环。即 设 p ( v ) = s l y l y , = 以r 陋，引，i = 1 ，) s p ( ) = y l s c p ( q ) np ( ) ) ，p 0 ( ) 成为样条环。 多元样条空间定义为 定义2 4称 ( 2 3 2 ) ( 2 3 3 ) 跷( ) ：= f l d e g f m ，( ) )( 2 3 4 ) z ( s ) = ( z ，) l j f ( z ，y ) = 0 ，( z ，y ) q )( 2 3 5 ) 为q 中关于剖分的c p 分片代数曲线，简称分片代数曲线f = 0 ，为了方便，我们 就说分片代数曲线f 。 2 0 大连理工大学硕士学位论文 分片代数曲线作为二元样条函数的零点集合，它是代数几何与计算几何中一种新 的重要概念，显然也是经典代数曲线的推广 但由于分片代数曲线依赖于剖分的几何性质且具有局部性，使得对它的研究存在 许多实质性困难，它绝不是代数曲线的简单推广。目前，对它的研究还刚刚开始，有 许多问题有待于解决。 2 1 平面上散乱数据的分片代数曲线拟合 3 分片代数曲线的散乱数据点的拟合 在c a g d 中，隐式代数曲线或曲面具有参数曲线曲面所不具备的优点。通过隐式 方程容易判断某点在曲线或曲面上，因而便于应用到曲线曲面求交问题中；利用隐式 代数曲线曲面比较容易表示几何实体。分片代数曲线具有隐式曲线的优点，且可利用 较低的次数得到较好的结果。朱春钢在文【4 产用基于样条空间踺( 漱) 的分片代数曲 线来拟合散乱数据。本篇论文产用鼹( a ( 1 ) ，一, f i i 的分片代数曲线来拟合平面上的散乱 数据。本部分介绍了其基本理论，且在最后给出了数值例子证明其可行性。 3 1 基本理论 给定散乱数据点y i = 协) 些1cq ，其中q 是一个平面上的区域。 首先，对q 进行1 型三角剖分，然后可以由第二部分介绍的理 。1 一。1 、a o ) 。) 的 基函数，就可以得到s ( z ，y ) 砖( 默) ，可以表示成如下： s ( x ，) = 磁x ，可) + 奶璐x ，可) ( 3 1 ) i - - - - 0j = oi - - oj = o 其中c = ( ) ( t ，j ) 幽d = ( 奶) ( 幻) j 是未知的，i = ( i , j ) - - i = 0 ，m + l , j ：0 ，n + 1 当然由第二部分知可令，n + 1 = 0 ，d m + 1 ，n 一1 = o ，d m + 1 ，n = 0 最基本的，通过最小化“代数距离”的和逼近给定数据： n 三( gd ) = s 2 慨1 ，鼽2 )( 3 2 ) 3 2 约束优化 分片代数曲线在一个区域内可能会分很多片。所以为了得到更加理想的结果，可 对目标函数加些限制。我们对点做些限制做为辅助的工具。分片代数曲线把一个区域 分成三部分：代数曲线本身s ( x ，y ) = o ，曲面的内部s ( x ，y ) o 对于n 中 某些点，可以要求代数曲线严格经过这些点。为了得到的代数曲线的形状符合给定的 散乱数据点。对于另外一些点可以强制使其在分片代数曲线的内部或外部，由此我们 可以对目标函数增加下面的限制： s 溉) = 0 ，i = i x ，赴 s ( d i ) 0 ，i = 1 ，k( 3 3 ) s ( 俄) 0 ，i = 1 ，7 大连理工大学硕士学位论文 3 3 优化目标函数 为了得n c ，d ，我们可以使目标函数最小，而为了得到更好的结果，可以增加目 标函数的项。 3 3 1 法向和切向量 为了得到更加有用的结果，可以在目标函数上加上切向和法向的相关项。其可以 保证拟合得到的分片代数曲线的形状更接近散乱数据点的形状。如何通过给定的散乱 数据点预估出其法向和切向在曲线和曲面的逼近中是一个比较重要的问题。最简单的 方法是采用用每点附近的几点产生其近似一次回归曲线，采用这点在回归线的法线 和切向量为其法向量和切向量。也可采用在f 2 5 中用到的方法。此方法大体如下面所 述，更具体的步骤可参阅( 2 4 ，2 5 1 ) 首先，我们估计给定的散乱数据 鼽= 慨1 ，p i 2 0 ，i = 1 ，n ) 的单位法向量 他- - - - ( ? 1 m n t 2 ) ， i = l ，) 和切向量 & - - - - - ( 8 m 8 t 2 ) ，i = 1 ，) 。由散乱数据点估计其法向和切向量是 曲线和曲面拟合中基本的问题。最简单的方法是采用线性函数逼近其附近的几个点， 然后取其法向做这个点的法向。当然也可用二次函数进行逼近，其效果会更好些。本 论文中，我们用最简单的方法，即用一点附近的几个点来估计其法向量。 以法向量为例。对一点p i = 慨1 ，p i 2 ) ，一条局部回归线l t ：y = a x + b 可以通过计算下 面二次函数的最小值： ( 3 4 ) 这里她是计算逼近权函数的对每个点仇非负的权重，可以选择随与邻点距离的增加而 急剧减小的非负函数。我们选择纰= e - r 2 日2 ，这里r = | f 鼽一岛i i ，h 是邻域半径。m 是邻 域内点的个数。从这个加权回归函数，可以得到局部对于玩最优的偏差线厶。进而可 以得到每一点的近似的初步的法向量i i n 1 1 = 1 ，这里l | 矿l l 是厶的单位法向量。 可以选择点在厶的法方向作为此点的近似法向。为了得到有用的结果，我们必须 保证相邻的数据点的法向量有相同的方向，i e ，礼j 0 数据点轨单位切向量8 i 可以通 过计算n t 8 t _ 0 。并且相邻的数据点的切向量也有相同的方向。下面的图是数据点的估 计切向量。 除了代数距离l ( c ) 项外，加进下面的项： nn m ( c ，d ) = ( v s ( p i l ，p i 2 ) s d 2 + ( v s ( p i l ，p i 2 ) 弛一1 ) 2 ( 3 5 ) 2 3 魄 力纯 一 l d+ 哦 m 谢 | l d 平面上散乱数据的分片代数曲线拟合 渺吁“ 图3 1 数据点的估计切向量 f i g 3 1t h ee s t i m a t e dn o r m a lv e c t o r so ft h ed a t as e t 妙n n r l 。“圳“纠烈缆 、 多 图3 2 数据点的估计切向量 f i g 3 2t h ee s t i m a t e dn o r m a lv e c t o r so ft h ed a t as e t ：蓼 大连理工大学硕士学位论文 v s 慨1 ，仇2 ) = ( ，s ) l ( p i l ，p i 2 ) 是样条函数s ( x ，y ) 在点鼽= 慨1 ，鼽2 ) 的导数，佻是用上述方法 估计的在鼽法向量，8 t 是锄切向量。 为了得到更有用的结果，需要对目标函数增加一些限制。我们把点的限制作为辅 助的工具。 分片代数曲线z ( s ) 把q 划分为三部分：曲线本蔓t s ( x ，y ) - - - - o ，曲面内部8 ( x ，y ) o 。 通过精确的测度拟合曲线要求通过在n 中的某些点。另一方面，为了得到形状较 好的拟合曲线，我们可以强加一些点在分片代数曲线的内部( 或外部) 。所以我们需 要对目标函数加上下面的限制： s 慨) = 0 ，i = i l ，乱， s ( 也) 0 ，i = 1 ，k ，( 3 6 ) s ( 夕t ) 0 ，i = l ，r 3 3 2能量项 在某些情况下，代数距离l 的最小化可能会产生几块分离的部分。 有几种方法解决这种问题，通过对目标函数项的追加，可以使结果更为理想。最 简单的方法是加上能量项。通过选择足够适合的系数，那么可以得到比较理想的拓扑 结构。 我们运用二次函数给定的能量项： e ( c ，d ) = ( s 2 $ + 2 s ：翟十s 毳) 如d 可dn 。 ( 3 7 ) 3 4 平面上散乱数据的分片代数曲线逼近 由上面的讨论可得到运用分片代数曲线逼近平面上散乱数据基本理论是：通过给 定的样条函数的基函数，构造一个目标函数；而为了结果更为理想，可向目标函数加 各种项：如切向，法向，能量来保证。而且也可以增加对点的区域的限制。不一定要 点都在分片代数曲线上。那么问题既成为解下面的约束优化问题； r a i n ( 1 一p 一：g l ( c ，d ) + p m ( c ，d ) + a e ( c ，d ) s 圳a ) = 0 , i = ，赴 f 3 8 ) s ( d i ) 0 ，i = 1 ，k ， s ( 阢) 0 ，i = 1 ，r 2 5 平面上散乱数据的分片代数曲线拟合 3 5 数值实验 在本章中将给出一些实例来检验上一章提出的理论。并将给出不同的点区域限制 和肛，a 值的例子。 例一：此例子，m = 2 ，n = 2 这些数据点( a ) 是从一条参数曲线上取出的；目标函数里 的权重选择p = 0 0 ，0 1 ；作为对比。且在加入了点的限制，要求过蓝色的点对比不同的限 制得到的结果。 例二：这个例子加进最小能量项，看不同的权系数的效果。蓝色的点为要严格通过 代数曲线的。这里m = 2 ，n = 3 ，其中肛= 0 1 ，0 3 ，a = 0 0 1 例三：这里给出了另一个例子，这里m = 6 ，n = 3 肛= 0 1 ，0 4 ，并且对比了加入点的限 制后的效果。 ( a ) 散乱数据点 ? ”、 ， + 、 7 _ 弋。 、0 、 譬 y ( b ) p = o 1 ( c ) p = o 1 ，加上点限制 图3 3 用分片代数曲线拟合散乱数据 f i g 3 3f i t t i n gw i t hp i e c e w i s ea l g e b r a i cc u r v e $ 、 大连理工大学硕士学位论文 一 f 、 ， ( a ) 散乱数据点 f 。 j ( e ) p = o 3 ，a = o 0 0 1 ( b ) p = 0 1 ( d ) p = o 1 ，a = o 0 0 1 ( f ) p = 0 1 ，a = o 0 0 1 ，加上点限制 ( g ) p = 0 3 ，a = o 0 0 1 ，加上点限制 图3 4 用分片代数曲线拟合散乱数据 ，、 ，( 平面上散乱数据的分片代数曲线拟合 。：一：一。 p ：， ， 乞：。 ( a ) 散乱数据点 ( c ) p = 0 4 ( b ) 肛= o 1 ( d ) # - - 0 1 ，加上点限制 ( e ) # - - 0 4 ，加上点限制 图3 5 用分片代数曲线拟合散乱数据 f i g 3 5f i t t i n gw i t hp i e c e w i s ea l g e b r a i cc u r v e s ， 大连理工大学硕士学位论文 结论 本文中提出平面上拟合散乱数据的一种方法，产用已经知道的样条函数空 间霹( 黠) 得到的分片代数曲线拟合散乱数据点，通过数值实验证明其是可行的。效 果也是比较好的。且因为分片代数曲线是隐式曲线，所以具有用隐式曲线拟合散乱数 据的所有优点；同时，又因为分片代数曲线的特殊性，此方法又具有可以用较低次数 的曲线拟合得到较好的结果。 2 9 平面上散乱数据的分片代数曲线拟合 参考文献 1 】王仁宏等多元样条函数及其应用北京：科学出版社，1 9 9 4 【2 】王仁宏，多元齿的结构与插值，数学学报，1 8 ( 1 9 7 5 ) ，2 1 5 - 1 0 6 3 】i j s c h o e n b e r gc o n t r i b u t i o nt ot h ep r o b l e mo fa p p l i c a t i o no fe q u i d i s t a n td a t ab ya n a l y t i c f u n c t i o n s ，w a r t a p p l m a t h ，4 ( 1 9 4 6 ) ，4 5 9 9 ：1 1 2 1 4 1 4 c g z h u ，r h w a n g ，l e a s t s q u a r e sf i t t i n go fp i e c e w i s ea l g e b r a i cc u r v e s ，m a t h e m a t i c a l p r o b l e m si ne n g i n e e r i n g ，2 0 0 7 ，1 1 ，2 0 0 7 d o i ：l o 1 1 5 5 2 0 0 7 7 8 7 0 2 5 】l e v i nd t h ea p p r o x i m a t i o np o w e ro fm o v i n gl e a s t s q u a r e s m a t h e m a t i c so fc o m p u t a t i o n ， 1 9 9 8 ，6 7 ：1 5 1 7 - 1 5 3 1 6 】卫炜，张丽艳，周来水一种快速搜索海量数据集k 一近邻空间球算法航空学 报，2 0 0 6 ，2 7 ( 5 ) ：9 4 4 - 9 4 8 【7 】i n - k w o nl e e c u r v er e c o n s h v e t i o nf r o mu n o r g a n i z e d n t a c o m p u t e r - a i d e dg e o m e m cd e - s i g n ，2 0 0 0 ，1 7 ，1 6 1 - 1 7 7 f 8 】徐树方，高立，张平文数值线性代数北京大学出版社2 0 0 0 【9 】林成森数值计算方法科学出版社1 9 9 8 【l o 】李庆扬，王能超，易大义数值分析清华大学出版社2 0 0 4 【1 1 x i n g p i n gc a o ，n e e l i m a s h r i k h a n d e ，g o n g z h o uh u 。a p p r o x i m a t eo r t h o g o n a ld i s t a n c er e g r e s - s i o nm e t h o df o rf i t t i n gq u a d r i ct or a n g ed a t a p a t t e nr e c o g n i t i o n l e t t e r s 1 9 9 4 ，1 5 ：7 8 1 7 9 6 1 2 】c l b a j a j ，j c h e n ，r j h o l ta n da n n e t r a v a l i ，e n e r g yf o r m u l a t i o n so fa s p l i n e s ， c o m p u t a i d e dg e o m d e s ，1 6 ( 1 9 9 9 ) ：3 9 5 9 1 3 】c l b a j a j ，g x u ，a - s p l i n e s ：l o c a li n t e r p o l a t i o na n da p p r o x i m a t i o nu s i n gg k - c o n t i n u o u s p i e c e w i s er e a la l g e b r a i c c u r v e s ，c o m p u t a i d e dg e o m d e s ，1 6 ( 1 9 9 9 ) ：5 5 7 - 5 7 8 1 4 j c c a r t ，e ta 1 ，r e c o n s t r u c t i o na n dr e p r e s e n t a t i o no f3 do b j e c t sw i t hr a d i a lb a s i s f u n c t i o n s ，i n ：s i g g r a p h2 0 0 1 ，l o sa n g e l e s ，c a ，p p ：6 7 - 7 6 【1 5 】c s c h e n ，f l c h e n ，y y f e n g ，b l e n d i n gq u a d r i cs u f a c ew i t hp i e c e w i s ea l g e b r a i cs u r - f a c e s ，g r a p h i c