DEM分析与可视化-第4章.ppt

1、第四章 不规则三角网结构DEM的建立,江文萍 武汉大学资源与环境科学学院 2015.10,2,3,一、TIN的三角化原则 与Grid结构相比, TIN能以更加灵活的方式在不同层次和空间上表达更复杂的地形表面,当地形数据中含有特征线如山脊线、山谷线、断裂线等时, TIN比Grid更能方便地表示之。 DTMs的发展早期,由于计算机硬件的限制,主要研究Grid的存储、内插与应用,因此Grid在理论与应用上比TIN要成熟得多。 但由于结构的不同, Grid的许多成熟的技术并不能完全移植到TIN中。,4-1 TIN的理论体系构成,4,从结构上讲, TIN是一典型的矢量数据结构。它主要通过节点(地形采样点

2、)、三角形边和三角形面之间的关系来显式或隐式地表达地形散点的拓扑关系,因此设计一个高效的、结构紧凑的、维护方便的TIN存储与组织结构对TIN的应用与库的维护是至关重要的。 TIN的基本单元三角形的几何形状直接决定着TIN应用质量。 由于地形的自相关性,相互愈接近的地形采样点,其之间的关联程度愈大; 同时,理论与实践均证明,狭长的三角形其插值精度比规则的三角形插值精度可信度要低。,5,TIN结构DEM中对三角形的几何形状有着严格的要求。 三条原则: 尽量接近正三角形; 保证最近的点形成三角形; 三角形网络唯一。,6,TIN的三角化算法分类,二、TIN的三角化算法,7,早在1850年的Dirich

3、let及1908年Voronoi在其论文中都讨论过Voronoi图的概念。设想在一大片林区内设置n个火情观察塔p1,p2,p3,.,pn,， 每个观察塔pi负责其附近林区V(pi)的火情发现及灭火的任务。若把上述n个观察塔换成n个火源，这n个火源同时点燃，并以相同的速度向所有方向蔓延，那么燃烧熄灭处所形成的图便是Voronoi图。又称泰森多边形（Thiessen Polygons）。,4-2 Voronoi图与Delaunay三角网,8,一、泰森多边形的概念是： 将分布在平面区域上的一组离散点用直线分割，使每个离散点都包含在一个多边形之内。进行分割的原则是：每个多边形内置包含一个离散点，而且包

4、含离散点Pi的多边形中的任意一点Q到Pi的距离都小于Q点到任意其他离散点Pj（i!=j）的距离。 把每两个相邻的泰森多边形中的离散点用直线连接后生成的三角形称为泰森多边形的直线对偶，又称为Delaunay三角形。这些连线与泰森多边形的边垂直。这些三角形便组成了三角网。 Delaunay三角形的外接圆圆心是与三角形相关的Voronoi多边形的一个顶点。Delaunay三角形是Voronoi图的偶图。,9,Delaunay三角网与Voronoi图,10,二、Delaunay三角网的性质 1）给定离散点集的D-三角网是唯一的； 2）三角网的外边界构成了点集P的凸多边形“外壳”； 3）空外接圆性质：没

5、有任何点在三角形的外接圆内部，反之，如果一个三角网满足此条件，那么它就是Delaunay三角网。 4）最大的最小角度性质：在由点集V所能形成的三角网中，D-三角网中三角形的最小角度是最大的。,11,由于D-三角网的性质，决定了D-三角网具有极大的应用价值。同时，它也是二维平面三角网中唯一的、最好的。 生成TIN的关键是构网技术，目前已提出许多构网算法。Miles证明D-三角网是“好的”三角网；Sibson认定“在一个有限点集中，只存在一个局部等角的三角网，这就是D-三角网”；Lingas进一步论证了“在一般倩况下，D-三角网是最优的”；Tsai认为，“在不多于3个相邻点共圆的欧几里德平面中，D

6、-三角网是唯一的”。 有鉴于此，D-三角网成为了一种主要的DTM表示法。,12,一、基本准则 Delaunay三角形产生准则的最简明的形式是：任何一个Delaunay三角形的外接圆的内部不能包含其它任何点Delaunay 1934。,4-2 Delaunay三角网的建立方法,13,Lawson 1977提出了一个局部优化过程LOP（Local Optimization Procedure）方法。 先求出包含新插入点p的外接圆的三角形，这种三角形称为影响三角形（Influence Triangulation）。 删除影响三角形的公共边（图b中粗线）; 将p与全部影响三角形的顶点连接，完成p点在原

7、Delaunay三角形中的插入。,14,二、三种主流算法 经过二十多年的研究，国内外已经出现了不少成熟的D-三角网生成算法，如：Shmaos和Hoey提出的分治算法，Lee和Schachter，Rex A.Dwyer等相继对其做了改进；Lawson提出的逐点插入法，Watson，Sloan等先后进行了发展和完善；此外，还有Green和Sibson提出的三角网生长算法等。 分割-合并算法 逐点插入算法 三角网生长算法,15,分割-合并算法（分治算法） Shamos 和Hoey首先提出了分割-合并算法的思想,Lee 和Schachter将分治算法思想应用于D-三角网的生成, 并表明该算法的时间复杂

8、度为O (N logN )。 分割-归并法的基本思路是，递归地分割点集至足够小, 使其易于生成三角网, 然后把子集中的三角网合并, 经优化生成最终的三角网.,16,三角网生长算法 三角网生长法的思路是, 先找出点集中最近两点连接成一条边, 然后按Delaunay 三角网的判别法则找出第三点, 再依次处理全部区域.,17,逐点插入算法 Sibson 和Green提出了一个平均时间复杂度为O (N 2) 的逐点插入算法。 基于迭代原理的逐点插入法，其基本思想为： 包含所有数据点的一个多边形中建立初始三角网，然后将余下的点逐一插入，采用LOP算法或Watson的空外接圆算法优化，确保其成为D-三角网

9、。,18,19,三、算法比较 逐点插入法虽然实现较简单，占用内存较小，但它的时间复杂度差，运行速度慢。特别是在大多数情况下,为了保证精确性,所取的离散点数往往很多,算法的效率将直接影响其实用性. 分治算法构网速度最快，其缺点是需要大量递归运算，占用较大的内存空间、数据预处理及优化工作量较大。 三角网生长算法的优点是占用内存空间较小, 但时间效率较低。,20,在实际应用中，DEM模型之间可以相互转换。大部分DEM数据都是规则格网DEM，但由于实际需要，两种格式的DEM之间往往需要相互转换。 一、格网DEM转成TIN 格网DEM转成TIN可以看作是一种规则分布的采样点生成TIN的特例，其目的是尽量

10、减少TIN的顶点数目，同时尽可能多地保留地形信息，如山峰、山脊、谷底和坡度突变处。规则格网DEM可以简单地生成一个精细的规则三角网，针对它有许多算法，绝大多数算法都有两个重要的特征： 1）筛选要保留或丢弃的格网点； 2）判断停止筛选的条件。 其中两个代表性的方法算法是保留重要点法和启发丢弃法。,4-4 规则网格与TIN结构DEM的转换,21,保留重要点法,该方法是一种保留规则网格DEM中的重要点来构造TIN的方法，它是通过比较计算格网点的重要性，保留重要的格网点。重要点（VIP,Very Important Point）是通过3*3的模板来确定的，根据八邻点的高程值决定模板中心是否为重要点。格

11、网点的重要性是通过它的高程值与8邻点高程的内插值进行比较，差分超过某个阈值的格网点保留下来。被保留的点作为三角网顶点生成Delaunay三角网。,22,由3*3的模板得到中心点P和8邻点的高程值，计算中心点P到直线AE，CG，BF，DH的距离，左图表示，再计算4个距离的平均值。如果平均值超过阈值，P点为重要点，则保留，否则去除P点。,23,启发丢弃法（DH, Drop Heuristic）,该法将重要点的选择作为一个优化问题进行处理。算法给定一个格网DEM和转换后TIN节点中的数量限制，寻求一个TIN与规则格网DEM的最佳组合。首先输入整个格网DEM，迭代进行计算，逐渐将那些不太重要的点删除，

12、处理过程直到满足数量限制条件或满足一定精度为止。,24,算法的输入是TIN，然后每次去掉一个节点，得到节点越来越少的TIN。很显然，可以将格网DEM作为输入，此时所有格网点视为TIN的节点，其方法是将格网中4个节点的其中两个相对节点连接起来，这样将每个格网剖分成2个三角形。 取TIN的一个节点O及与其相邻的其他节点，O的邻点（称Delaunay邻接点）为A,B,C,D，使用Delaunay三角构造算法，将O的邻点进行Delaunay三角重构。,25,判断该节点O位于哪个新生成的Delaunay三角形中，如图三角形BCE，计算O点的高程和过O点与三角形BCE交点O的高程差。若高程差d大于阈值de ，则O为重要点，保留，否则可删除。 对TIN中所有的点，重复进行上述判断过程； 直到TIN中所有的节点满足条件dde结束。,26,两种方法比较，VIP方法在保留关键网格点方面（顶点、凹点）最好，DH方法在两次丢弃数据点时确保信息丢失最少，但要求计算量大。各种方法各有利弊，实际应用中根据不同的需要，如检测极值点，高效存储，最