Algorithm 版 (精华区)

发信人: Lerry (第一次有失恋的感觉), 信区: Algorithm
标  题: 一种离散点插值的新算法 
发信站: 哈工大紫丁香 (2002年03月12日10:44:56 星期二), 站内信件

一种离散点插值的新算法
　
提出了一种按离散测量点构造曲面的新方法，即对每一测量点定义一个矩形作用域，并
在每一个作用域上构造一个特殊的Hermite插值曲面，最后通过各作用域在高度上的叠加
来构造一张插值曲面。证明了新算法的完备性和对测量点的依赖性，并通过实例计算证
明了新算法的有效性。
引言
　　二维离散数据的插值和曲面构造在数值处理中有着广泛的应用，如在地质探测、CA
D/CAM、社会调查统计和天气分析等许多方面都是必不可少的数学工具。早在20世纪70年
代中期，Mclain就采用最小二乘法开始了对这一类问题的探索。1978年，冲野和竹尾改
用弹性网逼近法，取得了优于Mclain的结构，并用于实际机械零件的构造。其后他们还
提出了曲线法。上述两种方法的共同特点是，首先用某种方法将任意分布的型值点置换
成与之等价的呈矩形分布的网格节点，然后按力学原理令其沿Z坐标变形，以求出网格节
点的Z坐标，或通过几何方法来求出网格节点的Z坐标。以后又有Barnhill和Franke等人
也先后讨论了几种求解方法，但效果并不理想。
　　本文提出的算法是一种纯几何的构造方法，其基本出发点是首先在u，w平面上对实
际测量点的参数值进行双向排序，然后按排序结果确定每一实际测量点的作用域。这些
作用域布满u，w平面并有限度地相互重叠。再用一种特殊的Hermite插值样条在每一作用
域上构造一张曲面片，使得测量点恰好位于曲面片上，并且该点的Z向梯度为0。在曲面
片的边缘处Z坐标值和梯度均为0。插值曲面上任一点的Z值就是由覆盖该点的所有曲面片
的Z值累加而得到的。本文详细描述了该方法的理论基础和几何特性，并以大型水轮机叶
片加工余量分布曲面的构造展示了该算法的实用性。
参数平面上作用域的构造方法及理论基础
　　在参数平面的定义域上确定每一个测量点的作用域是离散点造型的关键技术之一，
其主要要求为：作用域的集合必须覆盖整个定义域，不能留下任何空白；作用域的重叠
程度必须有一个上限，并且该上限不会因为测量点的加密而提高，以保证计算效率和测
量点数值的局部性。常用的三角域划分方法可以满足完全覆盖的要求，其重合度为1，但
构造过程相当烦琐。本文提出的矩形域构造方法可以快速简捷地解决作用域的构造问题
。
　　设P是参数平面上的一个测量点，它的参数为u0和w0。为了确定该点作用域的右边界
，从P点出发沿u线正向的 ± p /4范围内向右搜索，直到找到另一个测量点。该点的u值
就作为P点的右边界，记为uR 。如果直到曲面定义域的右边界仍未找到一个测量点，就
将定义域右边界的u值加上某一较大的数作为P点的uR 。用类似的方法即可求得P点作用
域的左边界uL、上边界Wu和下边界WB 。显然，按这种方法构造的作用域的集合会超越定
义域的边界，但这并不会给实际计算带来任何影响，也不会增加内存。在下节讨论了He
rmite插值曲面片的构造后将会看到作用域的外延是必要的。
　　根据上述作用域的构造方法可以知道如果定义域只有一个测量点，该点的作用域将
完全覆盖定义域。现假设定义域上有n个测量点，并且这些作用域的集合完全覆盖了定义
域。若在P0点的作用域里再增加一个测量点，不失一般性，可假设所增加的测量点Pi在
过P0点的u线 ± p /4的范围内。可以分两种情况来讨论：如果在V形域d 中不存在测
　　量点，则P0和Pi的作用域之和必定能完全覆盖原P0点的作用域，因此并不会因为增
加Pi点而产生空白；如果在V形域d 中存在一个测量点P5，则存在一个s ，它是原P0点作
用域和新的P0及Pi点作用域之差。现在考察s 是否会成为空白。从过P5的u线沿u线的反
向 ± p /4进行搜索，如果直到W＝Wi（Pi点的W值）都未找到测量点，则P5的作用域将
覆盖s ；否则必定存在一个P6阻断了P5的作用域使其不能完全覆盖s ，但P6作用域的下
边界不是Wi就是W3、W4、W0或Wi。对于第一种情况，P6作用域将覆盖s ；对于第二种情
况，P4和P5的作用域之和必定能够覆盖s 。因此在一个完全覆盖的作用域中插入新的测
量点不会产生空白。由数学归纳法的原理可知，对于任意一个测量点系，按本文所述方
法构造的作用域的集合可以覆盖整个定义域。不难证明，定义域上任意一点的重合度不
大于4。
作用域上插值曲面的构造
　　每一个作用域的插值曲面由4张曲面片构成。对于第一张曲面片，除了与测量点重合
的角点外，其余角点上的Z值均为0，而与测量点重合的角点的Z值与测量点相同。由于每
一个测量点都对其它测量点的作用域有屏蔽作各作用域上Z值的叠加不会改变测量点上的
Z值。在测量点上插值面的斜率为0，这与经验也是基本相符的，因为随机测量点往往选
在局部的最高或最低点上。为了不使插值面上的Z值在定义域的边界上突然降为0，而是
接近于离定义域边界最近的测量点值，将近界处的作用域拓展到远离定义域的地方是必
要的。
　　Hermite曲面片可表示为张量积的形式。考虑到本文中插值曲面片的特殊构造方法，
其表达式可简化为
　　　Z=Zi（1－3t12+2t13）（1－3t22+2t23）
式中Zi表示i个测量点的Z值，
u－ui
ui2－ui (u 3 ui)
t1= ui－u
ui－ui1 (u < ui)
w－wi
wi2－wi (w 3 wi)
t2= wi－w
wi－wi1 (u < ui)
　　其中ui1表示第i个测量点作用域u值的下界；ui2为作用域u值的上界；wi1为w值的下
界；wi2为w的上界。当计算点不在该作用域内时，令Z=0。
计算实例
　　按本文提出的算法对一张混流式水轮机叶片毛坏测量数据的处理。负余量部分为需
要补焊的区域，余量较大的区域需进行局部粗加工处理。
结论
　　通过这种方法构造的曲面充分考虑了测量的实际情况，基本反映了曲面的几何特性
，与三角域构造离散点自由曲面相比较，其减少了烦琐的曲面片的建立过程，大大提高
了计算效率。

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]