不规则三角网(TIN)生成的算法

用激光雷达数据创建不规则三角网的新计算方法摘要：不规则三角网（TIN）模型是基于规则格网地表表示之外的一种替代方法，应用于众多的数字化制图和地理信息系统中。

在不规则三角网中，不规则空间分布的采样点模拟地形时，粗糙地形用更多的点，平坦地形则采用较少的点表示。

尽管它简单，但是构建一个地区的TIN模型，需要进行样点选取、连接采样点构建三角形，以及用三角形进行表面建模三个步骤。

大部分样点选取可行算法都使用一个密集的数字高程模型（DEM）或一组数字化的等高线作为输入。

现在，光探测和测距（LIDAR）设备能够获得点云，它的可用性以及推广需要一种从新数据中进行样点选取的新计算方法。

本文阐述了用激光雷达（LiDAR）数据创建不规则三角网时样点选取的新计算方法。

关键词：三角剖分，TIN，LiDAR，DEM，地形表面1 引言与研究背景数字地形建模提供了一种健全的数字模式地形表述，非常重要，能够很容易的包含到数字制图与地理信息系统中。

数字地形模型（DTM）是用某种数字数据结构来表达地球表面的方法。

最常见的数字地形模型是数字高程模型(DEM)，包括规则格网模型和不规则格网模型。

常见的数字地形模型是用摄影测量以手动或者自动方式得到；然而，不管是手动还是自动方式，样点都不是随机选择的。

那么，规则格网模型（如：数字高程模型）能在何种程度表达地形？同时，如果想更新DEM将会怎样？TIN与DEM不同，是对地形表面的连续表达。

在GIS中，数字地形表达大部分能够用来分析和可视化研究。

不同的表达能够用来提供地形表面的数字模型，包括等高线图，数字高程模型以及不规则三角网模型。

等高线图用等高线来连接等高程点，进而描述地形表面。

等高线存储于“有序表”文件中。

尽管这种数据结构简单，但是长等高线可能有成千上万个点，所以会产生一个很大的“有序表”文件。

数字高程模型是地表点高度基于格网的表示。

规则格网模型是最简单而且最常见的地表数字表示形式。

DEM网格大小或者分辨率在确定地表描述可信度非常重要的参数。

GIS名词解释一建立DEM的方法之一【建立不规则三角网方法(TIN)】原理：对有限个离散点,每三个最临近点联结成三角形，每个三角形代表一个局部平面，再根据每个平面方程，计算每个网格点的高程，生成DEM。

TIN定义：将离散分布的实测数据点连成三角网，网中的每个三角形要求尽量接近等边形状，并保证由最近邻的点构成三角形，即三角形的边长之和最小。

【空间插值】常用于将离散点的测量数据转换为连续的数据曲面，它包括内插和外推两种算法。

前者是通过已知点的数据计算同一区域内其他未知点的数据，后者则是通过已知区域的数据，求未知区域的数据。

通常，在以下几种情况下要做空间插值：1、现有数据的分辨率不够，如遥感图象从一种分辨率转换到另一种分辨率。

2、现有数据的结构与所需结构不同，如将栅格数据转换到TIN数据。

3、现有数据没有完全覆盖整个区域，如只有一些离散点数据。

4、需要进行空间插值处理的原始数据包括：航片/卫片、野外测量采样数据、等值线图等。

【空间内插】定义：从已知点或分区的数据推求任意点或分区的数据的方法称为间数据的内插。

有点内插和区域内插两种。

【数字地面（形）模型】定义：描述地球表面形态多种信息空间分布的有序数值阵列，从数学的角度，可以用二维函数系列取值的有序集合来概括地表示数字地面模型的丰富内容和多样形式。

书中定义：用数字化的形式表达的地形信息。

【地理空间的特征实体】概念：地理空间实体特征是指具有形状、属性和时序特征的空间对象或地理实体。

；实体包括点、线、面、曲面和体等类型，它包括两种基本表达形式：矢量表示法、栅格表示法【E-R模型】常用的语义数据模型之一是实体--联系模型。

提供三种重要的语义概念，即实体、联系和属性。

实体: 就是对客观存在起独立作用的客体的抽象，用矩形符号表示；关系: 就是客体间有意义的相互作用或对应关系, 用菱形符号表示；属性: 对实体和联系特征的描述, 每个属性都有一个域，用椭圆表示【数据与信息的关系】数据是信息的一种表现形式，数据通过能书写的信息编码表示信息。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

创新论坛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）迭代以上两步直至所有基线都被处理。

/*程序名称：不规则三角网（TIN）的生成实例核心算法：三角形生长算法单位：南京大学金陵学院城市与资源学系日期：2009年11月9日至14日编程语言：Borland C可执行语句行数：373行*/#include<stdio.h>#include<conio.h>#include<math.h>#include<alloc.h>#include<graphics.h>struct Ps /*数据点的存储结构*/{int ID;float X;float Y;};struct Ts /*生成三角形的存储结构*/{int IB1;int IB2;int IB3;};void Open(char *fnm) /*打开源数据文件的函数*/{clrscr();textcolor(11);cprintf("TIN Create Demo");gotoxy(1,2);cprintf("Nov 2009");gotoxy(1,3);cprintf("Nanjing University Jinling College");printf("\n\nEnter the source data filename:\n\n>");scanf("%s",fnm); /*输入文件名*/while(fopen(fnm,"r")==NULL) /*若打开文件不成功则出现提示并重新输入*/{printf("Can't open this file.\n\n>");scanf("%s",fnm);}}int Size(char *fnm,int *ptr_N) /*读取文件头并检测数据量的函数*/{FILE *fp;int i=0,j=0,k=0;char c,t[5];fp=fopen(fnm,"r");c=fgetc(fp);while(c!='=') /*文件头为点的个数，格式为“N=200”等，故文件指针移动到‘=’时开始读取数据。