数据拟合问题就是根据若干参考点上的已知值求出待定点 上（未知点）的研究值。数据拟合问题通常可分为插值问 题和光顺逼近问题。 插值问题的解要求严格经过已知量测点，而光顺逼近问题 的解虽不要求严格经过已知点，但它要求在某种约束条件 下（比如最上 乘意义下 最小曲面能或最小粗糙度意义 下（比如最上二乘意义下、最小曲面能或最小粗糙度意义 下）达到整体逼近效果。
6/21/2010
空间插值方法
第6讲 空间插值方法及 TIN/TEN构建算法

6.1 问题的提出 6.2 空间数据插值方法概述 6.3 几种空间数据插值方法原理
6.1 空间插值问题的提出

6.2 空间数据插值方法概述

GIS在实际应用过程中，很多情况下，比如采样密度不够、 曲线与曲面光滑处理、空间趋势预测、采样结果的可视化 等，必须对空间数据进行插值和拟合，因此空间数据插值 是GIS数据处理的一项重要任务。其主要目的是根据一组 已知的离散数据，按照某种数学关系推求其他未知点和未 知区域的数据的过程。
Delauny三角化方法自提出后并未引起足够多 的重视，到了20世纪80年代才开始研究这个算 法，目前比较有效的算法有：

分治算法 逐点加入法 生长算法 凸壳法

分治算法

分治算法的基本思想是一个递归思想，把点集划分到足够小， 使其易于生成三角网，然后把子集中的三角网合并生成最终 的三角网。 逐点加入法有两个基本步：1.定位，找到包含新加点的三角 形；2.更新，形成新的三角形。 生长法从第一个DT开始，而后由三角形边逐步形成新的DT。 如果二维上的任意一点对应到三维点，可以计算出提升点的 凸壳，除去朝上的凸壳面，剩下的朝下的面就是原始点的DT （这个关系适合于任意n维）。
TIN/TEN构建算法

TIN: Triangular Irregular Network TEN: Tetrahedron Network 二维三角形和三维四面体剖分是计算几何中的 重要研究课题，它在有限元非结构化网格生成、 重要研究课题 它在有限元非结构化网格 成 实体造型、曲面逼近、数据场可视化、地学数 字高程模型等领域有着广泛的应用。

给定一个点集S={x1,x2,…,xn}，可以为集合中的每一 个点定义一个区域，这个区域满足：
x xi x x j , i j

所有区域的集合称为Diriclet图形，每个区域称为 Voronoi区域，也称为Voronoi多边形。

Voronoi多边形可以被想象成细胞的生长过程：

3
6/21/2010
The power of kriging results from the fact that, as a preceding step to the interpolation between the known observation points, a structural analysis of the spatial correlation revealing details of the geological forming process has to be performed. Semivariograms reveal important details of the geological generation since they provide an analytical means to quantify the anisotropy and the range of the underlying forming process. To speak in statistical terms, semivariograms quantify the distance (range) at which samples become uncorrelated from each other and they give an idea of the direction of the best and worst spatial correlation.
6.5 二维TIN逐点插入算法及实例


逐点加入法

该方法的基本过程是：


生长算法


凸壳法


给定将要插入的点P； 找到一个单元，这个单元包含P； 形成空腔。所谓空腔是指外接圆包含插入点P的单 元的集合，这些单元是将要被删除的单元。空腔的 形成准则一般采用圆形准则和邻接关系相结合的方 法； 形成空腔的单元。空腔的边界将来与新近插入的点 一起形成新的单元。
空间统计分析理论（地质统计学）
Kriging插值方法
2 2 i y( xi , , x0 ) i j y ( xi , x j )
i 1 i 1 j 1
n
n
n
上式表示用每个点作为估计依据时 方差(semi-variogram)，减去采样点相互 之间的方差(semi-variogram)除。
（2）反距离加权插值法(Shepard’s Method)
(3) 移动内插法(Moving Interpolating Method)
2
6/21/2010
(4) 克里金法(Kriging Method)
克里金法是一种地质统计方法，是一种最优、线性、无 偏内插估计量（Best Linear Unbiased Estimator，简称 BLUE）。较常规方法而言，它的优点在于不仅考虑了各 已知数据点的空间相关性 而且在给出待估计点的数值的 已知数据点的空间相关性，而且在给出待估计点的数值的 同时，还能给出表示估计精度的方差。经过多年的发展完 善，克里金法已经有了好几个变种，如普通克里金法、泛 克里金法等等。以下介绍普通克里金法。
内容提纲

6.4 Delauny三角化方法

6.4 Delaunay三角化方法 6.5 二维TIN逐点插入算法 6.6 二维TIN、三维TEN逐点插入算法实例

Delauny三角剖分从Dirichlet和Voronoi图形发展 起来。 Dirichlet图形由Dirichlet于1850年提出，他给出 了将给定区域剖分成互相联系的凸多边形的方 法：
6.6 二维TIN、三维TEN逐点插入算法 实例

根据上节算法原理，用C++编制Delauny2d和 Delauny3d类，实现二维TIN、三维TEN逐点插 入算法。 类的定义如下：

class Delaunay2d { public: Delaunay2d(int iVQuantity, Vector2<Real>* akVertex, Real fEpsilon); int GetSimplexQuantity () const; bool GetIndexSet (int i, int aiIndex[3]) const; }; class Delaunay3d { public: Delaunay3d(int iVQuantity, Vector3<Real>* akVertex, Real fEpsilon); int GetSimplexQuantity () const; bool GetIndexSet (int i, int aiIndex[4]) const; bool GetHull (int& riTQuantity, int*& raiIndex) const; };
while (stack is not empty){ stack.pop(T, A); compute i0,i1,i2,i3 with T.v(i1)=A.v(i2) and T.v(i2)=A.v(i1); if (T.v(i0) is in Circumcircle(A)) { N0 = mesh.Insert(T.v(i0), T.v(i1), A.v(i3)); B0 = A.adj(i1); if (B0 is not null) stack.push(N0, B0); N1 = mesh.Insert(T.v(i0), A.v(i3), A.v(i2)); B1 = A.adj(i3); if (B1 is not null) stack.push(N1, B1); } } // remove any triangles that share a vertex from the supertriangle mesh.RemoveTriangleSharing(V(0), V(1), V(2)); }
6.3 几种空间数据插值方法原理




代表性的基于整体的插值方法有： 趋势面法 最小二乘法 代表性的基于局部的插值方法有： 反距离加权插值法（谢别德法） 反距离加权插值法 谢别德法） 移动内插法 样条函数法 克里金法
1
6/21/2010
（1）趋势面法(Trend Surface Analysis)
5 4 6
将点集中的每一个点都想角成正在生长的细胞，这 些细胞从他们的细胞核开始，同时并且以相同的速 率向四周扩张。 当一个细胞的边界与另外的细胞边界相遇时这个边 界就停止生长。 最终，除了最外面的边界继续生长外，其余每个点 都将给定的区域分割成一系列的凸多边形，这些凸 多这形互不重叠，每一个凸多边形对应一个细胞核， 即节点。
当p=2时，为二次曲面：

f ( x, y ) b0 b1 x b2 y b3 x 2 b4 xy b5 y 2
所谓趋势面法，是通过选择一ห้องสมุดไป่ตู้二元函数来逼近采样数据 的整体变化趋势。该二元函数的一般形式为：
f ( x, y )
r s p r s 0
可用于模拟地形起伏、褶曲煤层等。 该二元函数必须满足观测值与拟合值之差的平方和最小
b