不规则三角网TIN的建立

第五章 不规则三角网（TIN）生成的算法在第四章，基于三角网和格网的建模方法使用较多，被认为是两种基 本的建模方法。

三角网被视为最基本的一种网络，它既可适应规则分布数 据，也可适应不规则分布数据，即可通过对三角网的内插生成规则格网网 络，也可根据三角网直接建立连续或光滑表面模型。

在第四章中同时也介 绍了 Delaunay 三角网的基本概念及其产生原理，并将三角网构网算法归纳 为两大类：即静态三角网和动态三角网。

由于增量式动态构网方法在形成 Delaunay 三角网的同时具有很高的计算效率而被普遍采用。

本章主要介绍 静态方法中典型的三角网生长算法和动态方法中的数据点逐点插入算法； 同时，还将给出考虑地形特征线和其他约束线段的插入算法。

而其他非 Delaunay 三角网算法如辐射扫描法 Radial Sweep Algorigthm（Mirante & Weingarten, 1982）等本文将不再介绍。

5.1 三角网生长法5.1.1 递归生长法递归生长算法的基本过程为如图 5.1.1 所示：3 213 21（a）形成第一个三角形 (b) 扩展生成第二个和第三个三角形 图 5.1.1 递归生长法构建 Delaunay 三角网（1）在所有数据中取任意一点 1（一般从几何中心附近开始），查找1距离此点最近的点 2，相连后作为初始基线 1-2； （2）在初始基线右边应用 Delaunay 法则搜寻第三点 3，形成第一个Delaunay 三角形； （3）并以此三角形的两条新边（2-3，3-1）作为新的初始基线； （4）重复步骤（2）和（3）直至所有数据点处理完毕。

该算法主要的工作是在大量数据点中搜寻给定基线符合要求的邻域 点。

一种比较简单的搜索方法是通过计算三角形外接圆的圆心和半径来完 成对邻域点的搜索。

为减少搜索时间，还可以预先将数据按 X 或 Y 坐标分 块并进行排序。

使用外接圆的搜索方法限定了基线的待选邻域点，因而降 低了用于搜寻 Delaunay 三角网的计算时间。

[测绘]不规则点建立TIN和等高线的方法！不规则点建立TIN对于不规则分布的高程点，可以形式化地描述为平面的一个无序的点集P，点集中每个点p对应于它的高程值。

将该点集转成TIN，最常用的方法是Delaunay三角剖分方法。

生成TIN的关键是Delaunay三角网的产生算法，下面先对Delaunay三角网和它的偶图V oronoi图作简要的描述。

V oronoi图，又叫泰森多边形或Dirichlet图，它由一组连续多边形组成，多边形的边界是由连接两邻点线段的垂直平分线组成。

N个在平面上有区别的点，按照最近邻原则划分平面：每个点与它的最近邻区域相关联。

Delaunay三角形是由与相邻V oronoi多边形共享一条边的相关点连接而成的三角形。

Delaunay三角形的外接圆圆心是与三角形相关的V oronoi多边形的一个顶点。

Delaunay三角形是V oronoi图的偶图，如图所示。

此主题相关图片如下：对于给定的初始点集P，有多种三角网剖分方式，而Delaunay三角网有以下特性：1）其Delaunay三角网是唯一的；2）三角网的外边界构成了点集P的凸多边形“外壳”；3）没有任何点在三角形的外接圆内部，反之，如果一个三角网满足此条件，那么它就是Delaunay三角网。

4）如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大，从这个意义上讲，Delaunay三角网是“最接近于规则化”的三角网。

下面简要介绍Delaunay三角形产生的基本准则：Delaunay三角形产生准则的最简明的形式是：任何一个Delaunay三角形的外接圆的内部不能包含其它任何点[Delaunay 1934]。

Lawson[1972]提出了最大化最小角原则：每两个相邻的三角形构成的凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。

Lawson [1977]又提出了一个局部优化过程LOP（Local Opti mization Procedure）方法。

不规则三角网（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 模型的适用范围不及栅格表面模型那么广泛，且构建和处理所需的开销更大。

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

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

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

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

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

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

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

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

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

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

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

引言对于复杂的地表形态一般用构建三角形网络的形式来拟合。

也就是说，可以用数学表面来代替传统意义上的实际地球表面。

由此，就涉及到TIN 的概念，TIN 是指不规则的三角形三角化网络，也可以说成基于不规则三角网的数字高程模型（Based on TriangulatedIrregular Net-work DEM），简写为Based on TIN DEM，简称TIN。

它是用一系列互不交叉、互不重叠的连接在一起的三角形来表示地形表面，即可以对已采集的规则的或不规则分布的地理数据进行三角建网，当整个区域的TIN 网络建立之后，就可以进行进一步的TIN 数据处理和应用等，如TIN 转换成DEM 等高线，地层剖面分析，流域计算及可视性分析等。

那么，TIN 是如何建立起来的呢，它有没有更加精确、优化、高效的TIN 三角建网方法呢，它又是怎样保存及输出的呢？这些问题将在下文中进一步讨论并分为几个方面进行详细介绍。

1 TIN 数据存储结构实际野外数据收集中采集的一般都是点状数据，即采集时使用测量仪器收集到的是地表每个测量站点的点号及相关地理坐标。

那么要形成TIN 三角形就必须建立点和点之间的联系以及每个TIN 三角形之间的联系。

这样，为了数据运算处理的高效性，对采集的地理数据在室内进行数据读取时又加以规划，分成了以下几类分别存储，如下表：根据以往经验，一个良好的存储结构对于软件的开发和程序的执行都是至关重要的，因为它不仅能够使程序在读取不同格式数据的基础上大大减少读取的复杂度和时间，而且能够大大提高程序的执行效率，并且也方便后续的各种对数据的处理和应用研究等。

这样，测量的点状数据读取结束后，就可以在TIN 的建立过程中建立边类和三角形类，并根据点状数据通过相应算法将其相关信息存储到对应的边和三角形中。

这就涉及到了TIN 三角网的建立问题，关于TIN 的建立算法和实现过程将在以下章节中进行详细介绍。

为利用程序软件读取野外采样数据后显示于界面的TIN 点状数据：也就是说，野外数据采集后，就可以将采集到的数据导入到计算机中或转换为软件指定的读取格式，而后在软件对数据进行读取的过程中就先将所有的采集数据进行TIN 点类归类了。