基于三角剖分与质心原理的三维插值方法对比

朱佩婕

摘 要 本文針对空间三维体插值加密与成像问题，进行建模、求解和相关分析并给出两种解题方法及其优劣对比。

关键词 Delaunay三角剖分 质心原理 三维插值 矩阵变换

中图分类号：TP301.6 文献标识码：A DOI：10.16400/j.cnki.kjdks.2016.12.015

Abstract In this paper， based on the three-dimensional interpolation and imaging of three-dimensional interpolation problems， modeling， solving and related analysis and give the two methods and their advantages and disadvantages.

Keywords Delaunay； Triangular subdivision； Centroid principle； three dimensional interpolation； Matrix transformation

第一种方法是根据分段插值的原理，采用基于Delaunay三角剖分的三维插值算法进行求解；为了减小距离所求点较远的点插值时因增加插值次数而导致龙格现象，本文所给出的第二种方法是基于质心原理的三维插值算法，有效减小节点间的函数震荡，相较于普通的插值方法具有更好的收敛效果。

1 问题重述

1.1 问题背景

在实际的科研或工程研究中，常常需要在已有数据点的情况下获得这些数据点之间的中间点的数据，就需要使用不同的插值方法进行数据插值，而对数据的插值加密与成像问题，因为要对繁杂大量的数据进行插值处理以及涉及部分数字图像的相关处理，所以在生活以及军工业方面具有十分重要的现实意义与研究价值。

1.2 待解决的问题

在以上提及的背景，有4851组相关数据有待解决：根据所给的4851组数据的特点，建立两种适当的数学模型，保证用该方法插值计算后电阻率数据的极值及其对应的位置不发生改变，并计算空间点所对应的电阻率数值。

2 模型假设

（1）数据真实可靠；

（2）电阻率不随各类外部因素发生改变；

（3）三维物体具有各向同性。

3 模型建立与求解

3.1 问题分析

要求我们根据文本中所给的4851组数据，使用两种适当的插值计算方法计算出空间中某点处所对应的电阻率值并说明该方法插值后所得到的电阻率数据极值大小与位置不变。由于题中所给的条件限制，因极值的大小和位置不能发生改变，若直接采用普通的Lagrange、Newton和Hermite插值时，当所选取的节点个数较多，插值多项式的次数会相应提高，会出现龙格现象。因此针对这种情况，本文给出了两种方法求解。

3.2 基于Delaunay三角剖分的三维插值计算方法

Delaunay三角剖分过程中采用Bowyer-Watson算法，其基本步骤为：（1）构造一个大三角形，包含所有散点，放入三角形链表；（2）将点集中的散点依次插入，在三角形链表中找出外接圆包含插入点的三角形（称为该点的影响三角形），删除影响三角形的公共边，将插入点都影响三角形的全部顶点连接起来，完成一个点在Delaunay三角形链表中的插入；（3）根据优化准则对局部新形成的三角形优化，将形成的三角形放入Delaunay三角形链表；（4）循环执行上述第2步，直到所有散点插入完毕。

以上计算过程可通过Matlab中的griddata函数所实现，其计算公式如下所示：

以下为方便叙述，使用“方法一”代指基于Delaunay三角剖分的三维插值算法。

3.3 基于质心原理的三维插值计算方法

本方法首先选取所给数据中距离待求点（'，'，'）最近的八个节点及其函数值，如表1所示：

其中八个节点和是方向上与'的前后间距，和是方向上与'的前后间距，和是方向上与'的前后间距。由质心原理，设点（'，'，'）到各节点的权重因子分别为、、、、、、和。

以下为方便叙述，使用“方法二”代指基于质心原理的三维插值计算方法。

4 模型评价与推广

4.1 模型评价

4.1.1 优点

（1）在方法一中，根据分段插值的原理，采用基于Delaunay 三角剖分的三维插值算法进行求解，先将原始数据进行插值处理，再将循环所得的点所对应的坐标（或要求点的坐标）写入Matlab中，运用Matlab内置的griddata函数对各点进行插值插值运算。根据问题二的复杂性评估和定量分析易看出：方法一平均值与标准差的大小更接近原始数据且模型简单易懂，Matlab中有内置函数griddata便捷了此法的运算实现。问题四的相关数据更是能够清晰地反映方法一与原始数据的近似度较高；

（2）在方法二中，基于质心原理的三维插值算法，读入循环所所得的点所对应的坐标（或要求点的坐标），在待求点附近寻找距离其最近的8个节点，代入公式进行计算（通过Codeblocks编程实现）。根据问题二的复杂性评估和定量分析易看出：方法二运行时间较短，为方法一的近10倍，而且从数据结果可看出，方法二的精确度可达小数点后12位，较高。

4.1.2 不足

（1）方法一运用Matlab实现算法，耗时较长，占用计算机内存较大，对计算机配置有一定要求，并且数据结果的精确度低于方法二；

（2）方法二运用Codeblocks实现算法，时间短、精确度高，但是与原始数据的相似性劣于方法一。

4.2 模型的推广

采用图像插值技术来提高数字图像的分辨率和清晰度，从软件方面进行改进具有十分重要的实用价值，以及用于遥感图像的几何校正、医学城乡以及电影、电视和媒体广告等影像特技处理中。

应用插值加密的方法处理图像示例图如图2：上图为放大图片后的结果，易看出马赛克色块且清晰度较低；下图为插值加密处理后的图像，图片清晰度明显提高。

参考文献

[1] 杨盛林，刘昱，刘玉峰.惯性平台热场分析及热设计的改进[J].中国惯性技术学报，2005.13（1）：5-9.

[2] 王瑾.基于强对流数值模拟的贵州冰雹识别及临近预报方法研究[D].中国科学院博士论文，2009.

[3] 肖艳娇.新一代天气雷达三维组网技术及应用研究[D].南京信息工程大学博士论文，2007.

[4] 徐恭学，李玉忱.一种优化的光线投射体绘制采样算法[J].厦门大学学报（自然科学版），1997.36（1）：27-32.

[5] Sicot O，Gong X L， Cherouat A， et al. Influence of residual stresses on the mechanical behavior of composite laminatematerials[J].Advanced Composite Materials，2005.14（4）：319-342.