不规则三角网的算法设计与实现

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

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

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

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

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

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

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

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

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

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

TIN三角形的建立的算法及实现研究摘要：不规则三角网(TIN)是数字高程模型(DEM)中最基本和最重要的一种模型，它能以不同层次的分辨率来描述地形表面，可以灵活的处理特殊地形。

因此，TIN的构建和重构、基于TIN模型的等值线追踪以及对TIN模型的三维可视化都是GIS中的重要研究领域。

关键词：不规则三角网；构建不规则三角网；生长算法；TIN数据结构。

一：TIN三角网的几种算法1、分割合并算法分割合并算法的思想很简单，就是将复杂问题简单化，首先将数据点分割成易于进行三角剖分的子集，如一个子集中包括三个、四个点，然后对每个子集进行三角剖分，并用LOP算法保证三角剖分为DT三角网。

当每个子集剖分完成后，对每个子集的三角剖分进行合并，形成最终完整体三角网。

不同的实现方法可有不同的点集划分方法、子三角网生成方法及合并算法等。

分割合并算法的步骤为：1）把数据以横坐标为主、纵坐标为辅按升序进行排序。

2）如果数据集中的数据个数大于给定的阀值，则把数据域划分为个数近似相等的左右两个子集并对每个子集做如下工作：（1）计算每一个子集的凸壳。

（2）以凸壳为数据边界，对每一数据域进行三角剖分，并用LOP进行优化，使之成为DT三角剖分；（3）找到链接左右子集两个凸壳的底线和顶线；（4）由底线到顶线，合并两个子三角网。

3）如果数据小于阀值，则直接输出三角剖分结果。

在第一步中，主要工作是对数据点进行排序，目的是使三角网不互相重叠和交叉。

一般以横坐标为主、纵坐标为辅按升序排列。

第二步是该算法的主体，包括连续分割、凸壳生凸壳三角剖分、子网合并等内容，集中体现了该算法的基本思想，即分割（数据点分割），合并（子三角网合并）。

数据点分割：是以递归的方式将数据点划分成大小相同的子集，一般要求每一个子集能采用同样的算法进行处理。

在三角网剖分情况下，规范化子集包含至少三个点但不高于六个点（数据分割阀值）。

当数据以横坐标为主排序后，递归划分的结果是垂直于横轴的连续条带。

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

1 引言地球表面高低起伏，呈现一种连续变化的曲面，这种曲面无法用平面地图来确切表示。

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

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

由于地理信息系统的普及，DEM作为数字地形模拟的重要成果已经成为国家空间数据基础设施（NSDI）的基本内容之一，并被纳入数字化空间框架（DGDF）进行规模化生产，已经成为独立的标准基础产品[5]。

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

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

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

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

基于三角形的表面建模可适合所有的数据结构，且三角形在形状和大小方面有很大灵活性，能很容易地融合断裂线，生成线或其他任何数据，因此基于三角形的方法在地形表面建模中得到了越来越多的注意，已经成为表面建模的主要方法之一。

VB语言简洁易学，对于学习GIS的学生来说无疑是接受很容易而且较快的一门计算机编程和开发语言，也是大多数学生最熟悉和了解的语言。

正是基于对生成不规则三角网算法的研究和满足学GIS的学生对VB 语言的喜爱和熟悉的情况下，本文就主要介绍用三角网生长算法生成不规则三角网及其在VB6.0环境下的实现。

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

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

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

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

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

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

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

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

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

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

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

创新论坛217一种简单的不规则三角网生成算法研究◆吴双江 海丽 巢琥不规则三角网（TIN ）是专为产生DEM 数据而设计的一种DEM 数据模型。

本文介绍了一种简单的生成TIN 的算法，并通过编程实现了TIN 的构建。

引言不规则三角网（Triangulated Irregular Networks ，TIN ）是专为产生DEM 数据而设计的一种DEM 数据模型。

TIN 的优点是高效率的存储，数据结构简单，易于更新，它克服了高程矩阵中冗余数据的问题，而且能更加有效地用于各类以DEM 为基础的空间分析和计算。

本文介绍一种简单的生成TIN 的算法，并通过C++语言编程实现TIN 的构建。

1 TIN的特性和三角化准则最常用的TIN 构网方法是Delaunay 三角剖分法，构成的D-三角网具有以下特性：满足最小角最大化的最佳三角形条件；任意三个离散点构成的Delaunay 三角形的外接圆中不包括其他离散点；由于D-三角网与V-图具有对偶性，一旦离散点集的平面坐标固定不变，所连接的三角网具有唯一性，不随起始点的不同而变化。

根据TIN 的特性，便产生了以下4种常用的TIN 三角化准则:1.1空外接圆准则：在TIN 中，每个三角形的外接圆均不包含点集的其余任何点。

1.2张角最大准则：一点到基边的张角为最大。

1.3面积比准则：三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小。

1.4对角线准则：两个三角形组成的凸四边形的两条对角线之比，比值限定值须给定，即当计算值超过限定值才进行优化。

一般而言，应尽量保持三角网的唯一性，即在同一准则下由不同的位置开始建立三角形网络，其最终的形状应是相同的，在这一点上，空外接圆准则、张角最大准则可以做到。

对角线准则含有主观因素，使用得不多。

2 TIN生成算法研究2.1 三角网生长算法分析TIN 的生成算法有多种，其中三角网生长算法是比较容易实现的。

三角网生长算法的基本步骤是：（1）以任一点为起始点；（2）找出与起始点最近的数据点相互连接形成D-三角形的一条边作为基线，按D-三角网的判别法则，找出与基线构成D-三角形的第三点；（3）基线的两个端点与第三点相连，成为新的基线；（4）迭代以上两步直至所有基线都被处理。

不规则三角网的原理和应用1. 引言不规则三角网是一种在地理信息系统（GIS）和计算机图形学中常用的数据结构，用于表示地形、地貌和其他空间数据。

本文将介绍不规则三角网的原理和应用。

2. 不规则三角网的原理不规则三角网是由一组不重叠的三角形组成的网络，其中每个三角形的边都共享一条边。

它可以用于将二维或三维空间上的数据进行离散化表示。

以下是建立不规则三角网的基本原理：•节点选择：首先需要选择一组合适的节点来构建三角网。

节点可以是地理位置、数据采集点或其他感兴趣的位置。

这些节点将成为三角网的顶点。

•三角剖分：根据节点的位置，在节点之间进行三角形的剖分。

通常使用Delaunay三角剖分方法，保证所有三角形的内接圆不包含其他节点，这样可以避免形成过于细长或扭曲的三角形。

•节点连接：将每个三角形的顶点连接起来形成三角网。

每个三角形的边都共享一条边，这样可以保证三角网的连续性。

3. 不规则三角网的应用不规则三角网在地理信息系统和计算机图形学中有广泛的应用。

以下是几个常见的应用场景：3.1 地形分析不规则三角网可以用于对地形进行离散化表示和分析。

通过节点的高程信息，可以计算每个三角形的面积、坡度和曲率等地形属性。

这对于地质学、测绘学和环境科学等领域的地形分析非常重要。

3.2 地理可视化不规则三角网可以用于地理可视化，将地理数据以更直观的方式呈现出来。

通过对三角形进行插值，可以根据节点上的数据对整个区域进行表面重建，从而生成地形模型或地图。

这对于城市规划、区域分析和地理导航等应用非常有用。

3.3 网格生成在计算机图形学中，不规则三角网可以用于网格生成。

根据给定的节点，可以通过插值方法生成一系列网格点，用于绘制曲线、表面或其他图形。

这对于计算机辅助设计、虚拟现实和游戏开发等领域非常重要。

3.4 数据插值不规则三角网可以用于数据插值，将离散的数据点进行填充。

通过插值方法，可以根据已知节点的属性估计其他位置的属性。

这对于气象学、地质学和农业等领域的数据分析非常有用。