第五章 不规则三角网TIN建立1.pptVIP

* * 第一节 概述 1.1 TIN的基本概念 基于不规则三角网的数字高程模型（Based on Triangulated Irregular Network DEM）就是用一系列互不交叉、互不重叠的连结在一起的三角形来表示地形表面。 什么是TIN？？ TIN的基本要素 用来描述TIN的基本要素有三个：节点、边、面。 节点是相邻三角形的公共顶点，也是用来构建TIN的采样数据。 边是指两个三角形的公共边界，是TIN不光滑性的具体反映。边同时还包含特征线、断裂线及区域边界。 面是由最近的三个顶点所组成的三角形面，是TIN描述地形表面的基本单元。TIN中的每一个三角形都描述了局部地形倾斜状态，具有唯一的坡度值。 数据和TIN的类型 构建TIN的原始数据根据数据点之间的约束条件可分为无约束数据域和约束数据域两种类型。 无约束数据域是指数据点之间不存在任何关系，即数据分布完全呈离散状态，数据点之间在物理上相互独立。 约束数据域则指部分数据点之间存在某种关系，这种关系一般通过线性特征来维护。 约束条件又可分为两种：一种是边界约束，指数据点被一多边形所包围，该多变形为边界约束条件；另外一种为内部约束条件，即数据点之间存在某种限制。 TIN的体系结构 在TIN中，对三角形的几何形状有严格的要求。一般应满足以下三条原则： 1、尽量接近正三角形 2、保证最近的点形成三角形 3、三角形网络唯一 分析可知：TIN的数据组织、三角形划分准则、算法和程序构成了TIN的基本理论体系框架。 1.2 TIN的三角剖分准则 第一节 概述 TIN的三角剖分准则是指TIN中三角形的形成法则，它决定着三角形的几何形状和TIN的质量。 目前在GIS、计算几何和计算机图形学领域常见的三角剖分准则有以下6种： （1）空外接圆准则：在TIN中，过每个三角形的外接圆均不包含点集的其余任何点。 （2）最大最小角准则：在两相邻三角形形成的凸四边形中，这两三角形中的最小内角一定大于交换凸四边形对角线后所形成的两三角形的最小内角。 （3）最短距离和准则：指一点到基边两端的距离和为最小。 1.2 TIN的三角剖分准则 第一节 概述 （4）张角最大准则：一点到基边的张角为最大。 （5）面积比准则：三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小。 （6）对角线准则：两三角形组成的凸四边形的两条对角线之比超过给定限定值时，对三角形进行优化。 通常将在空外接圆准则、最大最小角准则下进行的三角剖分称为Delaunay三角形，简称DT。 事实上，在任何三角剖分准则下得到的TIN，只要通过LOP法则（局部优化过程，Local optimal procedure,LOP）对其进行优化处理，就能得到唯一的DT三角网络。 LOP法则的基本思想是运用DT三角网的空外接圆性质对由两个有公共边的三角形组成的四边形进行判断，如果一个三角形的外接圆中含有第四个顶点，则交换四边形的对角线。 第一节 概述 1.3 三角剖分算法分类与特点 TIN的三角剖分就是按照三角剖分准则，将地形采样点用互不相交的直线段连接起来，并按一定的结构存储。 现以地形采样数据的分布情况为依据对TIN的三角剖分算法进行归类。 探测优化算法 特征线算法 沿等高线分布数据 层次三角形算法 循环迭带算法 VIPs算法 规则分布数据 三角形增长算法 逐点插入算法 空外接圆算法 分割合并算法 不规则分布数据 TIN算法类型 第二节 TIN的建立 5.2.1 无约束散点域的三角剖分算法与实现 Tsai于1994年根据实现过程，把DT三角剖分分成三类：分割合并算法、三角网增长算法和逐点插入算法。 分割合并算法 分割合并算法的思想很简单，就是将复杂问题简单化，首先将数据点分割成易于进行三角剖分的子集，然后对每个子集进行三角剖分，并用LOP算法保证三角剖分为DT三角网,最后对各子集根据一定规则进行合并，进而形成整体三角网。 分割合并算法的基本步骤： 第一步：把数据集以横座标为主，纵坐标为辅按升序进行排序。 第二步：对数据集进行分割，如果数据子集中的个数大于给定的阀值，把数据域划分为采样点个数近似相等的左右两个子集，并对每一子集做如下工作： 1 计算每一子集的凸壳 2 以凸壳为数据边界，对每一数据子集进行三角剖分，并用LOP法则进行优化，使之成为DT三角剖分 3找出连接左右子集两个凸壳的底线和顶线 4 由底线到顶线合并两个子三角网。 子集凸壳的生成 所谓凸壳是指数据点的自然极限边界，为包含所