第四章-数字高程模型之表面建模

第四章数字高程模型之表面建模4.1表面建模的基本概念4.2建立数字地形表面模型的各种方法4.3三角网的基本概念及生产方法4.4泰森多边形分析4.5TIN生成的算法4.6格网的基本概念与生产方法4.1表面建模的基本概念4.1.1内插与表面建模

DEM建模可以使用一个或多个数学函数来对地表进行表示。这样的数学函数通常被成为是内插函数。当DEM表面建模完成后，模型上任一点的高程信息就可以从DEM表面中获得。DEM内插：估计一个新点高程的整个过程，这个新点可能随后被用于表面建模。DEM表面重建：重建表面的实际过程，这个过程或许并不包含内插的计算。4.1.2表面建模与DEM结构网络结构网络指的是表面建模时的一种有特定结构的数据类型。结构网络更多涉及数据点在位置意义上的相互关系，而不一定涉及高程。

DEM表面根据网络建立，包含一系列一阶导数连续或不连续的子面，这是网络与DEM表面之间的主要区别。从结构网络的形式看，表面建模四种主要的方法：基于点的建模方法；基于三角形的建模方法；基于格网的建模方法；混合方法。从建立DEM表面时的数据来源分：根据高程量测数据直接建立；根据派生数据间接建立。（首先根据原始测量数据内插高程点，然后建立DEM表面）4.2建立数字地形表面模型的各种方法4.2.1地形表面重建与内插的通用多项式函数4.2.2基于点的表面建模假如使用单个数据点建立的平面表示此点周围的一小块区域（在地理分析领域也称为该点的影响区域），则整个DEM表面可由一系列相邻的不连续表面构成。如何确立相邻点间的边界。4.2.3基于三角形的表面建模分析多项式的前三项（两个一次项和一个零次项），生成一个平面，最少需要三个点（三维空间中的三个点）。这三个点可构成一平面三角形，从而决定了一倾斜的表面。如果每个三角形多代表的平面只用于代表三角形所覆盖的区域，则整个DEM表面可由一系列相互连接的相邻三角形组成。----基于三角形的表面建模。（图1.3.2b）三角形被认为所有图像中最基本的单元。有时候会使用高于一次的多项式，在这种情况下形成的三角形已不是平面的三角形，而可能是一曲面。4.2.4基于格网的表面建模通用多项式中的前三项与a3XY项一起使用的话，则至少需要4个点以确定一个表面。双线性表面。最终表面将包含一系列邻接的双线性表面。（图1.3.2a）基于格网的建模常用于处理覆盖平缓地区的全局数据。4.2.5混合式表面建模4.2.6表面建模方法的选择上文提到的四种主要的建模方法，分别对应于某一特定的数据结构。在实际应用中，由于基于点的建模并不实用而混合表面往往也转换为三角形网络，因此，基于三角形网络和格网的建模方法使用较多，被认为是两种基本的建模方法。上述讨论表明，即使对同一种数据，也可使用不同的建模方法建立不同类型的DEM表面。另外，需要指出的是，表面建模方法从不同角度考虑可有不同的分类方法。4.3三角网的基本概念及生成方法4.3.1简介不规则三角网（TIN-TriangulatedIrregularNetwork）通过从不规则分布的数据点生成的连续三角面来逼近地形表面。

TIN能以不同层次的分辨率来描述地形表面。与格网数据相比，能在某一特定的分辨率下，用更少的空间和时间更精确地表示更加复杂的表面。

TIN模型的基本要求：TIN是唯一的；力求最佳的三角形几何形状，每个三角形尽量接近等边形状；保证最邻近的点构成三角形，即三角形边长之和最小。在所有可能的三角网中，狄洛尼（Delaunay）三角网在地形拟合方面表现最为出色。当不相交的断裂线等被作为预先定义的限制条件作用于TIN的生成当中时，则必须考虑带约束条件的狄洛尼三角网。4.3.2狄洛尼三角网的定义与基本特性（1）标准（不带约束条件）狄洛尼三角网狄洛尼三角网由对应Voronoi多边形共边的点连接而成。狄洛尼三角形由三个相邻点连接而成，这三个相邻点对应的Voronoi多边形有一个公共的顶点，次顶点同时也是狄洛尼三角形外接圆的圆心。区域数+顶点数-棱数=2欧拉定理：狄洛尼三角网直接明了的定义：狄洛尼三角网为相互邻接且互不重叠的三角形的集合，每一个三角形的外接圆内不包含其他的点。图4.3.116个平面点集合的狄洛尼三角网及Voronoi的对偶空圆法则（狄洛尼法则）：狄洛尼三角形外接圆内不包含其他点的特性，被用作从一系列不重合的平面点建立狄洛尼三角网的基本法则。只要不超过三个邻域点在欧几里得平面上共圆，则狄洛尼三角网总是惟一的。局部几何形状最优的狄洛尼三角网可以根据最大最小（MAX-MIN）角度法则来建立，即在由两个相邻三角形构成的凸四边形中，交换此四边形的两条对角线，六个内角的最小角不再增大。（也称为最小角最大原则）如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大，从这个意义上讲，Delaunay三角网是“最接近于规则化”的三角网。（2）带约束条件的狄洛尼三角网当互不相交的断裂线与扩展边界加入到三角网时，表征狄洛尼三角网扩展到带约束条件的三角网。在图4.3.1中加入两条断裂线，图中的阴影部分，是被重新定义的三角形。图4.3.116个平面点集合的狄洛尼三角网及Voronoi的对偶图4.3.116个平面点集合的狄洛尼三角网及Voronoi的对偶带约束条件的Delaunay法则：只有当三角形外接圆内不包含任何其他点，其三个顶点相互通视时，此三角形才是一个带约束条件的Delaunay三角形。带约束条件的DelaunayLawsonLOP交换：只有在带约束条件的Delaunay法则满足的条件下，由两相邻三角形组成的凸四边形的局部最佳对角线（LocallyOptimalDiagonal）才被选取。

4.3.3狄洛尼三角网的生成算法主要介绍静态方法中典型的三角网生长算法和动态方法中的数据点逐点插入算法，同时考虑地形特征线和其他约束线段的插入算法。1）在所有数据中任取一点，查找距离此点最近的点2，相连后作为初始基线1-2；2）在初始基线右边应用Delaunay法则搜寻第三点3，形成第一个Delaunay三角形；3）并以2-3，3-1两条新边作为新的初始基线；4）重复步骤2）和3）。如果引入约束线段，则要在确定第三点时判断想形成的三角形边是否与约束线段交叉。1三角网生长算法2数据逐点插入法算法的基本思路是：先在包含所有数据点的一个多边形中建立初始三角网，然后将余下的点逐一插入，用LOP算法确保其成为Delaunay三角网。本算法的基本步骤为：

(1)定义一个包含所有数据点的初始多边形；

(2)在初始多边形中建立初始三角网，然后迭代以下步骤，直至所有数据点被处理；

(3)插入一个数据点P，在三角网中找出包含P点的三角形，把P点与三角形的三个顶点相连，生成新的三角形；

(4)用LOP算法优化三角网。3顾及线段约束的Delaunay三角网生成算法在动态生产三角网的基础上，采样两步法实现CDT的建立：（1）将所有数据包括约束线段上的数据点，建立标准的Delaunay三角网。（2）嵌入线段约束，根据对角线交换法LOP调整每条线段影响区域内的所有三角形。图3-3-8所示，约束线段插入的步骤：在三角网中插入一约束线段；确定边界与约束线段相交的三角形，如果两个这样的三角形有公共边，则将此公共边删除，最后形成约束线段的影响多边形；将影响多边形其他各顶点与约束线段的起始节点相连；应用带约束条件的LOP交换，更新影响多边形内的三角网，使约束边成为三角网中的一边；重复步骤①~④，直至所有约束线段都加入三角网中。包括以下三个步骤：1）凸包的生成求出离散点集中满足min(x-y)、min(x+y)、max(x-y)、max(x+y)条件的四个点；求出的四个点是离散点集中与包含该离散点集的外接矩形的4个角点最为接近的点，将他们按逆时针方向组成一个链表，构成初始凸包；设以凸包上相邻两点，计算连接两点的矢量线段右侧的所有点到该线段的距离，找出距离最大的一点；将该距离最大的点插入上述两点之间；重复③④两个步骤，直到点集中没有在该线段右侧的点为止；重复③~⑤三个步骤，直到凸包中任意相邻两点连线的右侧不存在离散点时，结束点集凸包求取过程。4凸包插值算法包括如下步骤：将数据点分别N/k块，k是每块中点的平均数量，缺省值为4；（1）数据分块4凸包插值算法(2)凸闭包的计算（3）凸包三角剖分建立一空的基线链表,将凸闭包的第一条边存入到此链表中；应用Delaunay法则,检测位于第二条基线左边的第三点；建立Delaunay三角形,将此三角形的所有边添加到基线链表中.三角形的新边确定方式:从基线边的开始结点到第三点,然后从第三点到基线的终止结点.更新拓扑数据结构中边与三角形的相邻拓扑关系.重复2-4以生成Delaunay三角网,直至所有基线处理完毕.（4）离散点内插‘在结束对凸包的三角剖分之后，对于那些不在凸包上的离散点，可以采取逐点内插的方法进行二次剖分，基本过程如下：找出外接圆包含待插入点的所有三角形，构成插入区域；删除插入区域内的三角形公共边，形成由三角形顶点构成的多边形；将插入点与多边形所有顶点相连，构成新的Delaunay三角形；重复上述步骤，直到所有非凸壳离散点都插入完为止，结束离散点内插。（5）约束线段的插入‘（6）外围边界裁剪删除内部外围边界以内和外部外围边界以外的三角形‘4.3.3从规则数据生成三角网两种方式：（1）直接将格网进行分解组合即可得到三角形；（2）通过一定的法则，选择“重要”的点（VIPs）来建立三角形。（1）直接方式在正方形格网情况下，以一条或两条对角线简单地将格网分解便形成了一系列规则的三角形。以这种方法根据正方形格网来生成三角网，有时是相当随意的。如图4.3.6所示，尽管图中每个例子中的格网节点的高程值都相同，单格局a-d四个不同表面所内插出来的高程点，其高程值相差很大。（2）选择VIPs方式这种方式的本质是根据一定的法则，通过选择表示地形曲面的“重要”的点，或者移去表示曲面“不重要”的点，建立TIN模型来实现的。两个关键步骤：确定格网高程点对于地形模型是否“重要”，或者格网高程点对于表达地形模型特征的程度。（全局方法；局部方法）确定终止判断的条件。（达到预设的格网点数；达到预设的精度。）常见的VIPs选择的方法有：地形骨架法。即利用地形特征点、线建立地形的“骨架模型”，然后对其内插点，到达预定的精度。地形滤波法。格网DEM可以看做一幅数字图像，可使用空间高通滤波器对其滤波，保留“图像”中的高频信息（即为地形信息）。层次三角网法。其基本思路为：连接格网DEM边界四个点中任意对角的两个点，形成初始三角形。分别对两个初始三角形，找出包含在三角形内的格网点中与三角面距离最大的点，并分别与包含它的三角形的三个顶点相连形成新的三角形。对每个三角形，找到它所包含的格网点中到三角面距离最大的点，内插该点在三角形面上的高程，求出内插高程与该高程之差的绝对值。如果该值小于高差阈值，不将该点插入到三角形中；如果大于高差阈值，将改点分别与包含它的三角形的三个顶点连接形成新的三角形。如果插入点的点数大于预定点数，或不再有点到包含它的三角形的高差大于给定的高差阈值，则终止整个过程。试探法。从整个DEM点集开始，每次去掉一个最不重要的点，不断反复，直到满足一定的精度要求或达到预定的点数。迭代贪婪插入法。基本步骤如下：对DEM的边界上所有的点组成的多边形进行狄洛尼构网。计算出每个三角形内所包含的格网点中与该三角形面距离（绝对值）最大的网络点，记为该三角形的“候选点”。比较所有三角形“候选点”的高差，将高差最大的点插入三角形。用狄洛尼三角形法则重新构网，得到新的三角形，删除被改变的三角形，并分别计算新三角形的“候选点”。重复b),c)直到满足终止条件。4.3.2从等高线数据生成三角网（1）等高线离散点直接生成TIN（2）将等高线作为特征线的方法（3）自动增加特征点及优化TIN的方法4.3.3从混合数据生成三角网格网被首先分解为规则的三角形，但如果有特征线穿过格网边，则格网并不通过自身的对角线分解，而是考虑特征线上的点，在格网中生成不规则形状的三角形。4.4泰森多边形分析4.4.1.泰森多边形及其特性（1）泰森多边形的定义：将所有相邻气象站连成一个三角形，作三角形各边的垂直平分线，每个气象站周围的若干垂直平分线便围成一个多边形，用这个多边形所包含的唯一一个气象站的降雨强度来表示这个多边形区域内的降雨强度，该多边形称为泰森多边形（Thiessenpolygons,又称Voronoi多边形）。根据有限的采样点数据生成多个面区域，每个区域内只包含一个采样点，其各个面区域到其内采样点的距离小于任何到其它采样点的距离，那么该区域内其它未知点的最佳值就由该区域内的采样点决定，该方法用于邻域分析。泰森多边形是对一个平面的划分，在泰森多边形Ti中，任意一个内点到该泰森多边形的发生点Pi的距离都小于该点到其他任何发生点Pj的距离。泰森多边形也可理解为对空间的一种内插方式，空间中的任何一个未知点的值都可以用距离它最近的已知采样点的值来代替。下图中虚线构成的多边形就是泰森多边形。泰森多边形每个顶点是每个三角形的外接圆圆心。泰森多边形也称为Voronoi图.（2）泰森多边形的特性及应用每个泰森多边形仅含有一个控制点数据；泰森多边形内的点到相应控制点的距离最近；位于泰森多边形边上的点到其两边控制点的距离相等；若泰森多边形是n边形，则与n个离散点相邻。

泰森多边形可用于定性分析、统计分析、邻近分析等。例如，可以用离散点的性质来描述泰森多边形区域的性质；判断一个离散点与其它哪些离散点相邻时，可根据泰森多边形直接得出，若泰森多边形是n边形，则就与n个离散点相邻；当某一数据点落入某一泰森多边形中时，它与相应的离散点最邻近，无需计算距离。设施负荷分析学校、医院等公共设施能否满足城市居民的需求？设施选址消防站响应需要一定时间，超过这一范围就不能在规定的时间内达到，因此消防站的选址就是要满足这一要求。4.4.2.Delaunay三角网的构建

Delaunay三角网是由与相邻泰森多边形共享一条边的相关点连接而成的三角网，它与泰森多边形是对偶关系。在泰森多边形的建立过程中，关键的一步是Delaunay三角网的生成。凸包插值算法（在4.5内容中介绍）4.4.3.泰森多边形的建立（1）泰森多边形建立过程1）建立Delaunay三角网，对离散点和形成的三角形进行编号，并记录每个三角形是由哪三个离散点构成的；2）找出与每个离散点