第三章 不规则三角网

不规则三角网（TIN）Ⅰ 数字高程模型（DEM）地球表面高低起伏，呈现一种连续变化的曲面，这种曲面无法用平面地图来确切表示。

于是我们就利用一种全新的数字地球表面的方法——数字高程模型的方法，这种方法已被普遍广泛采用。

数字高程模型即DEM（Digital Elevation Model），是以数字形式按一定结构组织在一起，表示实际地形特征空间分布的模型，也是地形形状大小和起伏的数字描述。

DEM有三种主要的表示模型：规则格网模型，等高线模型和不规则三角网。

格网（即GRID）DEM在地形平坦的地方，存在大量的数据冗余，在不改变格网大小情况下，难以表达复杂地形的突变现象，在某些计算，如通视问题，过分强调网格的轴方向。

不规则三角网（简称TIN，即Triangulated Irregular Network）是另外一种表示数字高程模型的的方法（Peuker等，1978），它既减少了规则格网带来的数据冗余，同时在计算（如坡度）效率方面又优于纯粹基于等高线的方法。

不规则三角网能随地形起伏变化的复杂性而改变采样点的密度和决定采样点的位置，因而它能够避免地形起伏平坦时的数据冗余，又能按地形特征点如山脊，山谷线，地形变化线等表示数字高程特征。

Ⅱ TIN的基本知识在TIN中，满足最佳三角形的条件为：尽可能的保证三角形的三个角都是锐角，三角形的三条边近似相等，最小角最大化。

TIN 是基于矢量的数字地理数据的一种形式，通过将一系列折点（点）组成三角形来构建。

形成这些三角形的插值方法有很多种，例如Delaunay 三角测量法或距离排序法。

ArcGIS 支持Delaunay 三角测量方法。

TIN 的单位是英尺或米等长度单位，而不是度分秒。

当使用地理坐标系的角度坐标进行构建时，Delaunay 三角测量无效。

创建TIN 时，应使用投影坐标系（PCS）。

TIN 模型的适用范围不及栅格表面模型那么广泛，且构建和处理所需的开销更大。

获得优良源数据的成本可能会很高，并且，由于数据结构非常复杂，处理TIN 的效率要比处理栅格数据低。

如何判断DTM法（不规则三角网法）中三角网是否正确并修改韩老师山西测量三角网法是利用实测地形碎部点、特征点进行三角构网，对计算区域按三棱柱法计算土方。

它是直接利用野外实测的地形特征点(离散点)构造出邻接的三角形，组成不规则三角网结构。

1、建网过程先从点集中选择一点作为起始三角形的一个端点，然后找离它距离最近的点连成一个边,以该边为基础,遵循角度最大原则或距离最小原则找到第三个点,形成初始三角形。

由起始三角形的三边依次往外扩展, 并进行是否重复的检测，最后将点集内所有的离散点构成三角网，直到所有建立的三角形的边都扩展过为止。

2、三角网特点三角网中的点和线的分布密度和结构完全可以与地表的特征相协调，直接利用原始资料作为网格结点；不改变原始数据和精度;能够插入地性线以保存原有关键的地形特征,以及能很好地适应复杂、不规则地形，从而将地表的特征表现得淋漓尽致致。

技术比较高经验多的人去了现场，虽然他自己没有去测量，但是根据你测回来的成图的三角网直接判断你的数据哪里不详细，哪里没有采集到位。

这是因为他知道现场的一条或者多条地性线，所谓地性线就是指能充分表达地形形状的特征线，他的判断依据就是地性线不应该通过三角网的任何一个三角形的内部,否则三角形就会“进入”或“悬空”于地面,与实际地形不符,产生的数字地面模型(DTM)有错。

3、三角网调整地性线与一般地形点一道参加完初级构网后，再用地形特征信息检查地性线是否成为了初级三角网的边，若是，则不再作调整；否则，按图下图作出调整，总之要务必保证三角网所表达的数字地面模型与实际地形相符。

如图上图（a）P1-P2所示，为地性线，它直接插入了三角形内部，使得建立的三角网偏离了实际地形，因此需要对地性线进行处理，重新调整三角网。

上图（b）是处理后的图形，即以地性线为三角边，向两侧进行扩展，使其符合实际地形。

①地物对构网的影响及处理方法等高线在遭遇房屋、道路等地物时需要断开，这样在地形图生成三角网时，除了要考虑地性线的影响之外，更应该顾及到地物的影响。

摘要作为空间数据基础设施中的“4D”产品之一和地理信息系统的核心数据库，数字高程模型（DEM）已在测绘、遥感、农林规划、城市规划、土木水利工程、地学分析等各个领域都有了广泛的应用。

数字高程模型的表示方法主要有规则格网模型、不规则三角网模型和等高线模型三种，而不规则三角网(TIN)是数字高程模型中最基本和最重要的一种模型，它能以不同层次的分辨率来描述地形表面，并可以灵活的处理特殊地形。

因此，围绕基于TIN 的DEM 的构建，本文主要论述了基于 TIN 结构的数字高程模型建模原理和方法，离散点的Delaunay 三角网生成算法，建立有约束条件的约束三角网，最后分析了建立的 TIN模型在土方计算方面的应用。

在本论文论述的过程中，针对传统算法进行了对比和分析后，在逐点插入法的基础之上，提出了一些新的细部改进的实现方法。

局部优化操作和改进的算法实现使得对大容量离散点的三角网构建速度更快，效率更高；对限制条件的嵌入满足由此计算出来的土方量更接近实际期望值。

本论文中主要的研究成果和内容如下： 1）在离散点的 Delaunay 三角网生成方面，本文中在插入点算法的基础上，建立凸包和矩形包容盒，建立虚拟网格，对原始离散点进行一级格网自适应分块，并建立索引关系。

在定位点所在三角形时引入快速点定位算法，简易的空外接圆及圆内测试公式，通过这些改进使得 Delaunay 三角网的剖分更加高效。

2）在约束 Delaunay 三角网理论基础之上，结合上面散点域的剖分方法，对已有的两步算法基础上改进，完成约束 Delaunay 三角网的构建。

在其过程中应用矢量点积等数学工具改善了计算中的凹凸点判断，继续采用上章的快速索引和最速定位方法，并且对约束线相切等特殊情形进行了处理，进一步完善了算法的稳健性。

3）对于在约束三角网构造基础上的 TIN 模型的应用，文中对其在土方量计算方面精度的优越性进行了分析，在可视化表达方面最后结合广东省东莞市某高尔夫球场工程给出了例证。

不规则三角网（TIN）Ⅰ数字高程模型（DEM）地球表面高低起伏，呈现一种连续变化的曲面，这种曲面无法用平面地图来确切表示。

于是我们就利用一种全新的数字地球表面的方法——数字高程模型的方法，这种方法已被普遍广泛采用。

数字高程模型即DEM（Digital Elevation Model），是以数字形式按一定结构组织在一起，表示实际地形特征空间分布的模型，也是地形形状大小和起伏的数字描述。

DEM有三种主要的表示模型：规则格网模型，等高线模型和不规则三角网。

格网（即GRID）DEM在地形平坦的地方，存在大量的数据冗余，在不改变格网大小情况下，难以表达复杂地形的突变现象，在某些计算，如通视问题，过分强调网格的轴方向。

不规则三角网（简称TIN，即Triangulated Irregular Network）是另外一种表示数字高程模型的的方法（Peuker等，1978），它既减少了规则格网带来的数据冗余，同时在计算（如坡度）效率方面又优于纯粹基于等高线的方法。

不规则三角网能随地形起伏变化的复杂性而改变采样点的密度和决定采样点的位置，因而它能够避免地形起伏平坦时的数据冗余，又能按地形特征点如山脊，山谷线，地形变化线等表示数字高程特征。

Ⅱ TIN的基本知识在TIN中，满足最佳三角形的条件为：尽可能的保证三角形的三个角都是锐角，三角形的三条边近似相等，最小角最大化。

TIN 是基于矢量的数字地理数据的一种形式，通过将一系列折点（点）组成三角形来构建。

形成这些三角形的插值方法有很多种，例如 Delaunay 三角测量法或距离排序法。

ArcGIS 支持 Delaunay 三角测量方法。

TIN 的单位是英尺或米等长度单位，而不是度分秒。

当使用地理坐标系的角度坐标进行构建时，Delaunay 三角测量无效。

创建TIN 时，应使用投影坐标系（PCS）。

TIN 模型的适用范围不及栅格表面模型那么广泛，且构建和处理所需的开销更大。

不规则三角网的构建曹宁0211555摘要：在GIS应用领域中，Delaunay三角网通常被应用在生成不规则三角网（TIN）模型，并用于描述地表形态。

本篇文章就目前较为成熟的算法做简要介绍，并对用于构建Delaunay三角网的渐次插入算法（闫浩文，2002）在VC++环境下实现的过程做较为详细的介绍。

关键词：不规则三角网；VC++；渐次插入算法Abstract:In GIS applications, the Delaunay triangulation Netcom often used to generate atriangulated irregular network (TIN) model, and is used to describe the surface morphology. This article is a brief introduction to the more sophisticated algorithms,and detailed introduce the implementation process of gradually insert of the Delaunay triangulation algorithm (Yan Hao, 2002) in VC + + environment.Keywords：TIN；VC++; gradually insert algorithm一、引言TIN（Triangulated Irregular Network）即不规则三角网，Delaunay三角网是其中的一种表现形式，也是一种主要的DTM的表示法。

Delaunay三角网：它是一系列相连的但不重叠的三角形的集合，而且这些三角形的外接圆不包含这个面域的其他任何点，它具有两个特有的性质：每个Delaunay三角形的外接圆不包含面内的其他任何点，称之为Delaunay三角网的空外接圆性质，这个特性已经作为创建Delaunay三角网的一项判别标准。

不规则三角网（TIN ）生成算法一、三角剖分的标准：空外接圆法：任意四点不能共圆最大最小角法：三角网内的最小角尽可能的大最短距离和准则：形成的三角形三边之和应满足最优解——三边之和最短张角最大准则：面积比准则： 三角形的内切圆面积/三角形面积或三角形面积/三角形周长的平方的值最小对角线法则：但插入另一个点时，寻找四边形对角线最短的那条边作为新的三角网二、Delaunay 符合的标准：三、递归生长算法的基本思路：四、凸闭包收缩法：先找到包含数据区域的最小凸多边形，并从该多边形开始从外向里逐层形成三角形网络五、逐点插入法生成TIN 的思路：首先提取整个数据区域的最小外边界矩形范围，以此作为最简单的凸闭包->按一定法则将数据区域的矩形范围进行格网划分，限定每个格网单元平均拥有的数据点数->根据数据点的（x,y ）坐标建立分块索引的线性链表->剖分数据区域的凸闭包形成两个超多边形->按照3建立的顺序链表顺序往4的三角形中插入数据点：先找到包含数据点的三角形，进而连接该点与三角形的三个顶点，简单剖分该三角形为三个新的三角形->分别调整新生成的三个三角形及其相邻的三角形，交换公共边->重复5~6，直到所有数据点都被插入到三角网中六、三角网TIN数据类型：无约束数据域——无约束TIN 约束数据域：内部约束及外部约束七delaunay法则：当三角形外接圆内不包含任意其他点，且其三个顶点相互通视时形成的三角网为一个带约束条件的delaunay法三角形八、带约束条件的delaunay Lawson LOP交换：在带约束的delaunay法则满足的条件下，由两相邻三角形组成的凸四边形的局部最佳对角线才被选取九、在TIN生成中如何考虑地形特征线三角剖分时要求TIN三角网中得三角形满足形态最优和无地形线穿越三角形的要求，主要有：三角形初始剖分->判断剖分三角形是否满足三角形形态比最大原则->判断特征线是否穿越剖分三角形->剖分点选择。

2。

1数字高程模型建模数字高程模型有两种模式[4]，一种是不规则三角网模型TIN，另一种是规则格网模型Grid。

两种模型可以相互转换，但一般大规模的地形都采用规则格网模型。

格网数字高程模型的建模方法可以有多种，最常用的方法是数字摄影测量方法，通过影像匹配自动生成数字高程模型。

当得不到立体影像，仅有地形图时，通常采用对现有地图进行扫描，获得矢量化等高线，再由等高线内插成数字高程模型。

当然，我们也可以通过外业测量的方法，获得大量高程点三维坐标，再内插成数字高程模型。

地面纹理影像可以从现有航空影像或航天遥感影像获得，也可根据地面物体的特征，人工赋予相应的纹理影像。

但不管用哪种方法，都要先将原始影像处理成数字正射影像，它有一致的比例尺，消除了投影误差，坐标与数字高程模型一致。

这样经过处理的数字正射影像才能与数字高程模型匹配，形成真实的景观模型。

由原始影像处理成数字正射影像可以有多种方法，通常有数字摄影测量方法和单片微分纠正方法。

不论哪种方法都是消除像片倾斜和投影差的过程，都要进行绝对定位使之归化比例尺和地面坐标。

2。

3三维建筑结构数据的获取与处理三维建筑结构是指房屋建筑、路桥、油罐、电视塔等各种三维实体，获得这些三维目标的框架数据主要有两种方法。

一种是用数字摄影测量方法，在立体模型上采集建筑物的框架坐标，然后通过建模软件将它们构造成体对象。

另一种方法是采用三维设计软件，如3Dmaxs，Multigen，Microstation等软件。

将设计好的三维实体导入并定位于地形景观模型中。

无论哪一种方法，都要对数据进行检核，使它们的连线正确，以利于粘贴侧面纹理。

三维实体数据检核的过程如下:(1)拓扑结构检查。

通过对每一地物的三维模型与航测像对中的立体影像的比对，检查三维模型的拓扑结构是否正确。

(2)建筑物顶部同高检查。

在现实中建筑物顶面绝大部分表现为同高的情况，而这就需要对三维建筑物模型的顶面进行同高检查，从而使点与平面符合。

第一章绪论1.1研究背景地球是人类生活和活动的承载体。

多年以来，我们为了更充分的认识自然客体和改造自然，总在不懈的努力尝试用不同的方式方法来描述、表达人所处的环境，其中地形图就是一个有代表性的测绘表述变迁的缩影。

从最开始的象形符号抽象的雏形到后来的在二维介质上对三维表面进行地形写景图，地貌写景图等描述是一个进步，但写景方式不具备可量测性，所以还是很局限的。

随着测绘技术发展，地形的表达也由写景式的定性表达过渡到了以等高线为主的矢量化表达。

航空摄影测量，遥感技术提供的影响都在对三维现实世界的模拟。

但是有一个矛盾体，那就是对于地形表面形态而言，一方面我们尽可能的从几何角度去理解和描述以解决实际应用中的可量测性；另外一个方面它本身是一种三维景观现象，对于其表述要考虑生理视觉感受，我们总是希望能够尽可能的直观形象逼真。

从20世纪四十年代开始的计算机图形学、计算机辅助制图等相关学科和理论的发展，使得在测绘领域，在图形表达表述方面发生了从模拟表达时代走向了数字表达时代，有了质的飞跃。

其中地理信息系统（GIS ）及数字高程模型（DEM ）学科或技术显得尤为重要。

地理信息系统，简称GIS （Geographical Information System ）,它源于20世纪60年代初期加拿大测量学家Tomlinson 的“把地图变成数字形式的地图，以便计算机进行处理与分析”的观点，但是在技术工具处理中，则是利用计算机存贮、处理地理信息，并且在计算机软、硬件支持下，把各种资源信息和环境参数按空间分布或地理坐标，以一定的格式或者分类输入、处理、存贮、输出，用以满足其应用需要的人机交互系统。

因此GIS 的本质是在二维地理空间基础上实现对地下、地表和空中诸地理信息的数字化表达和管理。

当然地理信息系统技术发展到当前，功能不再是当初的局限于查询、检索和制图，而是丰富到空间分析、建模、决策等诸多方面，在数据管理上则从简单的栅格数据、矢量数据管理转向多元数据融合，在现实生活中应用的很活跃，也很充分。