3、表面建模-PPT（精）

《3、表面建模-PPT（精）》由会员分享，可在线阅读，更多相关《3、表面建模-PPT（精）（68页珍藏版）》请在金锄头文库上搜索。

1、第三讲 DEM的表面建模,一、表面建模的基本概念 二、DEM表面建模方法 三、三角网生成算法简介 四、格网生成算法简介 五、TIN与Grid比较,用多少点来描述一个表面? 这些点是规则的分布，还是随机分布? 采样点位于局部最大、最小值?,采样的核心问题,表面建模的核心问题,根据有限的离散采样点，如何才能得到地形表面任意位置处的高程? 通过表面模拟建立对象的计算机表示，这种表示通常为多边形面片的集合 通过内插实现从离散点到连续表面的表示 内插的基本依据是空间的自相关性，即所谓的地理学第一规律: 空间上越靠近的事物就越相似，相互之间的影响也越大,内插,DEM建模可以使用一个或多个数学函数来对地表进

2、行描述。这样的数学函数通常被认为是内插函数 内插包括利用邻近点的某种“均值”来估计未知点高程的整个过程,内插,采用什么类型的表面以及如何重建的问题,表面建模中的内插方法,一、表面建模的基本概念,DEM是地形表面的“数学/数字模型”根据不同数据集采用一个或多个“数学函数”表示，数学函数通常被认为是内插函数。 对地形表面进行表达的各种处理称为表面重建或表面建模，重建的表面即为DEM表面。 因此：地形表面重建=DEM表面重建/表面生成,地形表面重建与内插的通用多项式函数,Z= f (x,y ),二、 DEM表面建模方法,多项式中每一项的表面形状都有自己的特征 某一特定建模程序在建立实际表面时，一般只

3、使用函数中的其中几项，并不一定需要这个函数中的所有各项,用于表面重建的通用多项式,通用多项式中单独项的表面形状,Planar Z = a0,y,Linear Z = a1x,x,y,z,Linear Z = a2y,x,y,z,x,z,y,Quadratic Z = a3 x2,二、 DEM表面建模方法,根据建模过程中使用的基本几何单元，数字地形表面建模的方法可以分为以下四类： 基于点的建模方法 基于三角形的建模方法 基于格网的建模方法 基于两种结合的混合建模方法,基于点的建模方法 使用单点数据建立一个平面区域以表示该点所在区域的地表，则整个DEM表面可由一系列相邻但不连续的表面构成； 该方法

4、简单，但不易确定相邻点的边界； 在理论上，该方法只涉及独立的点，所以可用于处理所有类型的数据,二、 DEM表面建模方法,二、 DEM表面建模方法,三角表面建模 用三点构成一个三角形平面； 每三角形可用于表达三角形所覆盖的区域，整个DEM表面可由一系列相互连接的三角形组成，该方法称基于三角形的表面建模；,三角表面建模 正方形、矩形及其它任意形状均可分解为一系列三角形； 基于三角形的表面建模可适于所有的数据结构，且无论这些数据是由选择采样、混合采样、规则采样、剖面采样生成，还是由等高线法生成； 三角形建模由于其形状与大小非常灵活，易于融合断裂线、生成线或其它任何数据；,二、 DEM表面建模方法,格

5、网表面建模 规则点阵中相邻四点构成一个表面，可以是线性表面，也可以是四点拟合而成的曲面； 整个DEM由相互连接的正方形或矩形面片或拟合的光滑表面表达；,二、 DEM表面建模方法,二、 DEM表面建模方法,格网表面建模 适于基于格网采样及渐进采样，特别是基于正方形格网采样方法所获取的数据建模； 适于地势平坦地区的地形表达，而不太适合地形起伏巨大，存在大量断层和陡峭斜坡的情形； 格网模型易于管理、计算分析以及可视化处理； 数据冗余量大；,二、 DEM表面建模方法,混合表面建模 在多种采样方式或存在多种数据类型时，易采用混合表面建模； 混合表面建模，通常指格网建模与三角网建模的结合； 但为了便于统一

6、处理，混合建模通常转为三角表面；,三、 三角网的生成算法简介,不规则三角网(TINTriangulated Irregular Network)通过从不规则分布的数据点生成的连续三角面来逼近地形表面。 优点：能以不同层次的分辨率来描述地形表面。 对于TIN模型，其基本要求有三点： (1)TIN是惟一的； (2)力求最佳的三角形几何形状，每个三角形尽量接近等边形状 (3)保证最邻近的点构成三角形，即三角形的边长之和最小。,3.1 从离散点生成TIN：Delaunay三角网,如何把一个散点集合剖分成不均匀的三角形网格，这就是散点集的三角剖分问题，散点集的三角剖分，对数值分析以及图形学来说，都是极为

7、重要的一项预处理技术。,关于Delaunay三角形 1850年Dirichlet和1908年Voronoi最早讨论空间散点的关系问题； 1934年Delaunay提出了Voronoi图的对称图，即空间三角剖分；,不存在四点共圆，且每个面是一个三角形； 每个三角形对应于一个voronoi图顶点（外接圆圆心）； 每个边对应于一个voronoi图边； 每个结点对应于一个voronoi图区域； Delaunay图的边界是一个凸壳； 如果以三角网中所有边的长度总和最小为原则，则具有较短对角线的三角网为最佳选择。,Delaunay三角网的特性,最优三角网,Lawson（1977）提出了根据最大最小(Max

8、-Min)角度法则建立局部几何形状最优的三角网： 在由两相邻三角形构成的凸四边形中，交换此四边形的两条对角线，不会增加这两个三角形六个内角总和的最小值。 Lawson 据此提出了局部最优方法(LOPLocal Optimization Procedure)： 交换凸四边形的对角线，可获得等角性最好的三角网。,带约束条件的狄洛尼三角网,带约束条件的狄洛尼法则： 只有当三角形外接圆内不包含任何其他点，且其三个顶点相互可视时，此三角形才是一个带约束条件的狄洛尼三角形； 带约束条件的狄洛尼Lawson LOP交换： 只有在满足带约束条件的狄格尼法则的条件下，由两相邻三角形组成的凸四边形的局部最佳对角线

9、(Locally Optimal Diagonal)才被选取。,三角网的生成算法,分治算法； 渐次插入算法； 三角网生长算法,Delaunay三角网基本算法,先将数据排序，分成互不相交的子集； 将每一子集建立三角网后，将子集合并生成最终的狄洛尼三角网； Lee and Schachter（1980）； Dwyer（1987）提出带约束条件的处理方法；,分治算法,设数据集V中含N个平面互不重叠的数据点，则： 1.将V按升序排列使(xi, yi) (xi+1, yi+1), 成立条件：(xi = or xi+1且yi yi+1) ； 2.将V分为大小相等的两部分VL和VR，VL包含数据前一半点，V

10、R包含剩余的点； 3.分别建立两部分数据的Delaunay三角网，并应用Lawson LOP进行优化； 4.计算每一半数据的凸闭包，搜索上面部分与下面部分的公共切线（最终三角网的一部分）； 5.从下面的公切线开始，沿相邻边直至最上面的公共切线将两个三角网合并，合并过程中同时进行优化； 6.重复以上2-5直到三角网建立完毕。,分治算法,分治算法,渐次插入算法,将未处理的点加入到已经存在的Delaunay三角网中，每次插入一点，重新定义Delaunay三角网。定义包含所有数据点并作为初始狄洛尼三角形的超三角形顶点： 从数据中取出一点P加入到三角网中； 搜寻包含点P的三角形，将P与此三角形三个顶点相

11、连，形成三个三角形； 由里到外应用Lawson LOP优化整个三角网； 重复以上过程直到所有点处理完毕； 删除所有包含一个或多个超三角形顶点的三角形；,渐次插入算法,基于矩形结构的基本算法如下： 设有矩形内有N个数据点，删除与矩形顶点重合的所有点(以矩形顶点为起点来进行计算）； 将矩形划分为N1/2块或更小的矩形区域； 对块中数据点进行排序； 将加入到矩形中的第一点与矩形的四个顶点相连，形成初始三角网； 加入第二个点到已有三角网中，将其与包含它的三角形顶点相连； 从里到外优化整个三角网； 重复以上步骤直至所有点处理完毕；,三角形生长算法,算法过程如下： 在数据集中任取一点，查找距离此点最近的点

12、，相连后作为初始基线； 在初始基线右边应用Delaunay法则搜索第三点； 生成Delaunay三角形，并以该三角形的两条新边作为新的基线； 重复前面过程直至所有基线处理完毕； 这种算法大量的时间花费在符合要求的邻域点的搜索方面，为了减少搜索时间，许多学者提出了许多不同的方法，如将数据分块并排列，以外接圆的方式限定其搜索范围。,三角形生长算法,径向扫描算法： 查找离数据重心最近的点作为起始点； 计算中心点与所有其它点的距离和方位； 根据方位、距离等将所有其他点按升序排列； 径向扫描数据点，将中心点与径向点相连，连接相邻线段任意两连续端点，生成辐射状三角形直至数据的边界； 通过检查由一对相邻三角

13、形形成的四边形两对角线的长度，从外部边界上的三角形开始由外向里顺序优化三角网,上面提到的算法都没有考虑当外围约束边界加入到三角网中时对三角网进行边界裁剪，因此这些算法对带约束边界的TIN构建来说是不完整的。边界裁剪或多边形裁剪对那种在限定区域内应避免等高线内插的应用是必须的，也是非常关键的。下面将给出一个同时处理平面点和限制条件，既能进行三角网构建也能进行边界剪切的完整算法。,凸闭包(convex hull)生成算法,完整的凸闭包插入算法,凸闭包插入算法包括如下几个步骤： 将数据点分为NK个块，也即NK个等边的行与列段。此处K是每一块中点的平均数量，缺省值为4；（数据的初始划分） 确定每一分块

14、的凸闭包（凸闭包的计算）； 应用狄洛尼法则建立凸闭包的狄洛尼三角网（凸闭包三角网）； 反复插入不在凸闭包中的其他点，更新已有三角网（其他数据点的插入）； 反复插入新的约束线段，更新已有三角网（约束线段的插入）； 删除所有内部外围边界或外部外围边界以外的三角形（外围边界裁剪）。,1、 数据的初始划分,数据分块是为了加速邻域点搜索，提高算法效率； 目前在Voronoi和Delaunay 几何算法中广泛采用分块的方法； 分块一般采用二维空间的排序方法，一般采用递归排序法；,2、 凸闭包的计算,平面点凸闭包的定义是包含这些平面点的最小凸多边形。 分块数据凸闭包的计算： 搜寻分别对应xy，xy最大值及x

15、y，xy最小值的各两个点。这些点为凸闭包的顶点，且总是位于数据集的四个角上，如右图（3-3-10(a)中的点79，12，6所示）。 将这些点以逆时针方向存储于循环链表中。 对链表中的点I及其后续点J调用递归子算法Convex(I，J)，以搜索线段IJ右边凸闭包上的所有点。,递归于算法Convex(I,J)： 检查数据块中位于线段IJ上及其右边的所有点，计算对IJ有最大偏移量的点K，对IJ右边的点赋正的偏移值，IJ左边的点赋负的值。 检测最大偏移值的符号： 如果值为正，将K插入到链表位于I与J之间的位置，继续调用函数Convex（I,K）和Convex(K，J)； 如果值为0，且K位于I，J之间

16、，则将K插入到链表中I，J之间，调用函数Convex（I,K）和Convex(K，J)； 否则，终止对Convex函数的调用,2、 凸闭包的计算,2、 凸闭包的计算,3、生成凸闭包三角网,假设凸闭包顶点数目为M，随机分布点的数目为N(通常情况下M远小于N)。将M个顶点按逆时针方向排序，然后按以下步骤建立凸闭包的狄洛尼三角网(图3311)： 建立一空的基线链表，将凸闭包的第一条边存入到此链表中； 应用狄洛尼法则，检测位于第一条基线左边的第三点。 建立狄洛尼三角形，将此三角形的所有(内部)边添加到基线链表中。三角形的新边以这种方式确定：从基线边的开始结点到第三个点，然后从第三个点到基线边的终止结点。 更新拓扑数据结构中边与三角形的相邻拓扑关系。 重复2一4以生成狄洛尼三角网，直至所有基线处理完毕。,4、其它数据点的插入,应用狄洛尼法则，搜寻其外接圆包含新点的所有三角形，以生成新点的影响三角网。此三角网的搜索是通过三角形重心的分块结构以及保持边和三角形邻接关系的拓扑数据结构来进行的。其具体过程是首先通过分块结构搜寻第一个待选三角形，然后由此三角形向外通过拓扑数据结构对其邻