1、1 邻接三角形 1 X Y Z 2 X Y Z 3 X Y Z 4 X Y Z 5 X Y Z 6 X Y Z 7 X Y Z 8 X Y Z 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 顶点 5 6 8 7 5 4 2 3 6 5 7 4 6 5 4 4 8 8 8 7 2 1 X 3 1 2 6 4 5 3 4 X X 5 8 7 X 6 2 8 6 7 X X 点文件 三角形文件 1 1 1 2 5 4 4 3 2一、一、TINTIN的三角化原则的三角化原则与Grid结构相比, TIN能以更加灵活的方式在不同层次和空间上表达更复杂的地形表面,当地形数据
2、中含有特征线如山脊线、山谷线、断裂线等时, TIN比Grid更能方便地表示之。DTMs的发展早期,由于计算机硬件的限制,主要研究Grid的存储、内插与应用,因此Grid在理论与应用上比TIN要成熟得多。但由于结构的不同, Grid的许多成熟的技术并不能完全移植到TIN中。 4-1 TIN的理论体系构成的理论体系构成3从结构上讲, TIN是一典型的矢量数据结构。它主要通过节点(地形采样点)、三角形边和三角形面之间的关系来显式或隐式地表达地形散点的拓扑关系,因此设计一个高效的、结构紧凑的、维护方便的TIN存储与组织结构对TIN的应用与库的维护是至关重要的。TIN的基本单元三角形的几何形状直接决定着
3、TIN应用质量。由于地形的自相关性,相互愈接近的地形采样点,其之间的关联程度愈大;同时,理论与实践均证明,狭长的三角形其插值精度比规则的三角形插值精度可信度要低。 4TIN结构DEM中对三角形的几何形状有着严格的要求。三条原则: 尽量接近正三角形; 保证最近的点形成三角形; 三角形网络唯一。5TIN的三角化算法分类二、二、TIN的三角化算法的三角化算法 6 早在1850年的Dirichlet及1908年Voronoi在其论文中都讨论过Voronoi图的概念。设想在一大片林区内设置n个火情观察塔p1,p2,p3,.,pn,， 每个观察塔pi负责其附近林区V(pi)的火情发现及灭火的任务。若把上述
4、n个观察塔换成n个火源，这n个火源同时点燃，并以相同的速度向所有方向蔓延，那么燃烧熄灭处所形成的图便是Voronoi图。又称泰森多边形（Thiessen Polygons）。 4-2 Voronoi图与图与Delaunay三角网7一、泰森多边形的概念是： 将分布在平面区域上的一组离散点用直线分割，使每个离散点都包含在一个多边形之内。进行分割的原则是：每个多边形内置包含一个离散点，而且包含离散点Pi的多边形中的任意一点Q到Pi的距离都小于Q点到任意其他离散点Pj（i!=j）的距离。 把每两个相邻的泰森多边形中的离散点用直线连接后生成的三角形称为泰森多边形的直线对偶，又称为Delaunay三角形。
5、这些连线与泰森多边形的边垂直。这些三角形便组成了三角网。 Delaunay三角形的外接圆圆心是与三角形相关的Voronoi多边形的一个顶点。Delaunay三角形是Voronoi图的偶图。8Delaunay三角网与Voronoi图 9二、Delaunay三角网的性质1）给定离散点集的D-三角网是唯一的；2）三角网的外边界构成了点集P的凸多边形“外壳”；3）空外接圆性质：没有任何点在三角形的外接圆内部，反之，如果一个三角网满足此条件，那么它就是Delaunay三角网。4）最大的最小角度性质：在由点集V所能形成的三角网中，D-三角网中三角形的最小角度是最大的。10由于D-三角网的性质，决定了D-三
6、角网具有极大的应用价值。同时，它也是二维平面三角网中唯一的、最好的。生成TIN的关键是构网技术，目前已提出许多构网算法。Miles证明D-三角网是“好的”三角网；Sibson认定“在一个有限点集中，只存在一个局部等角的三角网，这就是D-三角网”；Lingas进一步论证了“在一般倩况下，D-三角网是最优的”；Tsai认为，“在不多于3个相邻点共圆的欧几里德平面中，D-三角网是唯一的”。 有鉴于此，D-三角网成为了一种主要的DTM表示法。11一、基本准则 Delaunay三角形产生准则的最简明的形式是：任何一个Delaunay三角形的外接圆的内部不能包含其它任何点Delaunay 1934。 4-
7、2 Delaunay三角网的建立方法的建立方法12 Lawson 1977提出了一个 局 部 优 化 过 程 L O P（Local Optimization Procedure）方法。先求出包含新插入点p的外接圆的三角形，这种三角形称为影响三 角 形 （ I n f l u e n c e Triangulation）。删除影响三角形的公共边（图b中粗线）;将p与全部影响三角形的顶点连接，完成p点在原Delaunay三角形中的插入。13二、三种主流算法二、三种主流算法 经过二十多年的研究，国内外已经出现了不少成熟的D-三角网生成算法，如：Shmaos和Hoey提出的分治算法，Lee和Scha
8、chter，Rex A.Dwyer等相继对其做了改进；Lawson提出的逐点插入法，Watson，Sloan等先后进行了发展和完善；此外，还有Green和Sibson提出的三角网生长算法等。分割-合并算法逐点插入算法三角网生长算法14分割-合并算法（分治算法） Shamos 和Hoey首先提出了分割-合并算法的思想,Lee 和Schachter将分治算法思想应用于D-三角网的生成, 并表明该算法的时间复杂度为O (N logN )。 分割-归并法的基本思路是，递归地分割点集至足够小, 使其易于生成三角网, 然后把子集中的三角网合并, 经优化生成最终的三角网. 15三角网生长算法 三角网生长法的
9、思路是, 先找出点集中最近两点连接成一条边, 然后按Delaunay 三角网的判别法则找出第三点, 再依次处理全部区域. ABC1C2C316逐点插入算法 Sibson 和Green提出了一个平均时间复杂度为O (N 2) 的逐点插入算法。 基于迭代原理的逐点插入法，其基本思想为： 包含所有数据点的一个多边形中建立初始三角网，然后将余下的点逐一插入，采用LOP算法或Watson的空外接圆算法优化，确保其成为D-三角网。 17逐点插入过程逐点插入过程三角形的定位影响域的确定影响域内三角网重构18三、算法比较三、算法比较逐点插入法虽然实现较简单，占用内存较小，但它的时间复杂度差，运行速度慢。特别是
10、在大多数情况下,为了保证精确性,所取的离散点数往往很多,算法的效率将直接影响其实用性.分治算法构网速度最快，其缺点是需要大量递归运算，占用较大的内存空间、数据预处理及优化工作量较大。三角网生长算法的优点是占用内存空间较小, 但时间效率较低。19 在实际应用中，DEM模型之间可以相互转换。大部分DEM数据都是规则格网DEM，但由于实际需要，两种格式的DEM之间往往需要相互转换。一、格网DEM转成TIN 格网DEM转成TIN可以看作是一种规则分布的采样点生成TIN的特例，其目的是尽量减少TIN的顶点数目，同时尽可能多地保留地形信息，如山峰、山脊、谷底和坡度突变处。规则格网DEM可以简单地生成一个精
11、细的规则三角网，针对它有许多算法，绝大多数算法都有两个重要的特征：1）筛选要保留或丢弃的格网点；2）判断停止筛选的条件。其中两个代表性的方法算法是保留重要点法和启发丢弃法。 4-4 规则网格与TIN结构DEM的转换 20保留重要点法保留重要点法 该方法是一种保留规则网格DEM中的重要点来构造TIN的方法，它是通过比较计算格网点的重要性，保留重要的格网点。重要点（VIP,Very Important Point）是通过3*3的模板来确定的，根据八邻点的高程值决定模板中心是否为重要点。格网点的重要性是通过它的高程值与8邻点高程的内插值进行比较，差分超过某个阈值的格网点保留下来。被保留的点作为三角网
12、顶点生成Delaunay三角网。21由3*3的模板得到中心点P和8邻点的高程值，计算中心点P到直线AE，CG，BF，DH的距离，左图表示，再计算4个距离的平均值。如果平均值超过阈值，P点为重要点，则保留，否则去除P点。22启发丢弃法（启发丢弃法（DH, Drop Heuristic） 该法将重要点的选择作为一个优化问题进行处理。算法给定一个格网DEM和转换后TIN节点中的数量限制，寻求一个TIN与规则格网DEM的最佳组合。首先输入整个格网DEM，迭代进行计算，逐渐将那些不太重要的点删除，处理过程直到满足数量限制条件或满足一定精度为止。 23算法的输入是算法的输入是TINTIN，然后每次去掉一个
13、节点，得到节点越来越少的，然后每次去掉一个节点，得到节点越来越少的TINTIN。很显。很显然，可以将格网然，可以将格网DEMDEM作为输入，此时所有格网点视为作为输入，此时所有格网点视为TINTIN的节点，其方的节点，其方法是将格网中法是将格网中4 4个节点的其中两个相对节点连接起来，这样将每个格网个节点的其中两个相对节点连接起来，这样将每个格网剖分成剖分成2 2个三角形。个三角形。取取TINTIN的一个节点的一个节点OO及与其相邻的其他节点，及与其相邻的其他节点，OO的邻点（称的邻点（称DelaunayDelaunay邻接点）邻接点）为为A,B,C,DA,B,C,D，使用，使用Delauna
14、yDelaunay三角构造算法，将三角构造算法，将OO的邻点进行的邻点进行DelaunayDelaunay三角重构。三角重构。24判断该节点判断该节点OO位于哪个新生成的位于哪个新生成的DelaunayDelaunay三角三角形中，如图三角形形中，如图三角形BCEBCE，计算，计算OO点的高程和点的高程和过过OO点与三角形点与三角形BCEBCE交点交点OO的高程差。若的高程差。若高程差高程差d d大于阈值大于阈值de de ，则，则OO为重要点，保留，为重要点，保留，否则可删除。否则可删除。对对TINTIN中所有的点，重复进行上述判断过程；中所有的点，重复进行上述判断过程；直到直到TINTIN
15、中所有的节点满足条件中所有的节点满足条件ddedde结束。结束。25 两种方法比较，VIP方法在保留关键网格点方面（顶点、凹点）最好，DH方法在两次丢弃数据点时确保信息丢失最少，但要求计算量大。各种方法各有利弊，实际应用中根据不同的需要，如检测极值点，高效存储，最小误差，可以选择使用不同的方法。26二、TIN转成格网转成格网DEM TIN转成格网DEM可以有两种方法：将TIN看作普通的不规则数据点生成规则格网DEM按照要求的分辨率大小和方向生成规则格网，对每一个格网搜索最近的TIN数据点，按线性或非线性插值函数计算格网点高程。将规则格网覆盖在TIN上，计算每个格网点落在哪个TIN三角形内（面），根据该三角面格顶点的高程进行线性内插，得到格网点的高程。
