基于三角网生成法的Delaunay三角网生成算法的研究与实现
- 格式：docx
- 大小：287.04 KB
- 文档页数：8
基于三角网生长法的Delaunay三角网生成算法
***************
【摘要】论文简要介绍了Delaunay三角网的性质以及基本生成算法，并重点介绍了三角网生长法的基本原理和算法步骤，并通过设计合理的数据结构，对算法进行实现。对算法进行分析并提出通过构建格网索引，进一步提高三角网生成效率。
【关键词】三角网生长法扩展TIN 格网索引
1. 引言
数字地形模型DTM（Digital Terrain Model）是指对地形表面形态属性信息的数字表达，是带有空间位置特征和地形属性特征的数字描述[1]。
DTM是GIS的基础数据来源，可用于土地利用现状的分析、合理规划及洪水险情预报等。DTM地形属性为高程时称为数字高程模型(DEM)。
DEM主要的三种表示模型为规则格网模型、等高线模型、不规则三角网模型（Triangular Irregular Network 简称TIN）。数字化等高线模型不适合计算坡度或制作地貌渲染图等地形分析，规则格网数据结构简单，计算方便；但存在数据冗余，数据采集较麻烦，难以表达复杂地形等缺陷。TIN即能够避免平坦地形时数据冗余，也能表达复杂地形，可以根据任意地形特征点表示DEM，因此被广泛应用。Delaunay三角剖分能最大程度的接近等边三角形，避免狭长三角形，并且能保持三角网的唯一性，使其成为生成TIN的最佳选择。
本论文将简要介绍和比较几种常用的Delaunay三角网生成算法（逐点插入法，三角网生长法，分割合并算法等），并且对三角网生长法算法原理进行研究分析和程序实现。
2. Delaunay三角网的性质
Delaunay三角网中的三角形必须满足以下几个性质：
（1） 空圆特性
每一个Delaunay三角形的外接圆不包括Delaunay三角网中的任何其他点。
（2） 最大最小角特性
在三角剖分中，Delaunay三角网的所有三角形的最小角之和最大。
即使得Delaunay三角形最大程度接近等边三角形。
（3） 唯一性
对于一组离散点，若不存在四点共圆的情况，离散点构成的Delaunay三角网是唯一的。
3. Delaunay三角网生成算法介绍
Delaunay三角网的生成常用算法有逐点插入法，分割合并算法，三角网生长法。生成三角网的算法不同在于初始三角网的生成以及三角网的扩展方法。
3.1 逐点插入法
逐点插入算法的基本思想是，在包含所有数据点的多边形中建立初始三角形，然后将余下的点进行逐一插入，查找该点所在的三角形，将该点与三角形的三顶点进行连接，生成三个新的三角形，用LOP算法优化三角网确保其成为Delaunay三角网。
所谓LOP优化算法是为了生成的三角形符合Delaunay三角形的空圆特性，最大最小角性，唯一性。其主要做法为：
（1）将两个具有公共边的三角形合并成一个四边形
（2）用空圆特性检查三角形，若四边形的第四点（除检查三角形的三点外）若在三角形的外接圆之内，就对四边形对角线进行对调处理。若不在，则不做处理。
3.2 分割合并算法
分割合并算法的基本思想是把点集进行划分到足够小，使其易于生成三角网，用LOP算法对子集进行优化，保证其成为Delaunay三角网，最后合并子集生成最终的三角网。
3.3 三角网生长法
三角网生长法的基本思想是先建立初始三角形，然后以初始三角形的三条边作为种子，分别“生长”出新的三角形，将新的三角形的三边又作为种子，依次生长新三角形。生长的新三角形必须是Delaunay三角形，故得满足空圆特性和最大最小角特性，因此按照这两个特性来生长Delaunay三角形。具体算法原理，算法步骤，算法实现以及改进将在后续详细讲述。
3.4 几种算法的比较
逐点插入算法和分割合并算法都较之三角网生长法，效率高。
三角网生长法，虽每次都是生成Delaunay三角形，但是每次都得遍历剩余的所有点，搜索到符合条件的第三点。因此效率不高，故可以通过改进其点的搜索策略来提高其生成效率。
逐点插入法，在三角网生成后期，随着点数的增多，其会使得三角形生成速率大大降低。
分割合并思想较之前面两种算法最好，但是其精髓在于如何合理分块，如何快速有效得进行子网合并和优化。
除了上述三种生成算法，还有凸包法，分治算法等，具体可以参照相关文献。
4. 三角网生成算法
4.1 算法原理
三角网生长算法是在生成的初始三角形的基础上扩展三角网，初始三角形通过选择最短边和与最短边构成最大角的点构成第一个三角形，然后取第一个三角形的三条边按照Delaunay三角网的特性进行扩展三角网。
4.2 算法实现
对于算法的程序实现，主要需要考虑如何设计合理的数据结构，算理清法步骤，掌握程序语言。以下将从数据结构，算法步骤以及程序问题逐一进行阐述。
4.2.1 数据结构
算法的实现以及算法的执行效率与设计的数据结构有密切的关系，一个良好的数据结构有利于对数据进行高效的管理（存储和检索），从而提高算法的执行效率。
（1） 离散点结构
离散点主要存储了其坐标，平面坐标(x,y)和高程值z。
class T_Point
{
public:
double x, y, z; // 点的坐标
T_Point();
virtual ~T_Point();
};
（2） 有向边结构
有向边存储了起始点号和终点号，并存储了与该边相邻的三角形编号。这样的三角形信息在LOP优化算法中很有用，在三角网生长法可以来判断改变是否是公共边（不可扩展）。useCount是用来记录这条边用了多少次，用了一次，说明不是公共边，可扩展，若是用了两次，说明不可扩展。
class T_Edge
{
public:
int startPt; // 起点
int endPt; // 终点
int TriID[2]; // 边相邻的左右三角形编号，无时为-1
int useCount; // 扩展情况，1，可扩展；2；不可扩展(为公共边)，也可以用flag来标记
T_Edge();
bool friend operator==(T_Edge L1, T_Edge L2); // 判断两条边是否相等
virtual ~T_Edge();
};
（3） 三角形结构
三角形结构按逆时针存储了构成三角形三边编号和三顶点编号。这样可以方便对三角形进行扩展，根据待扩展的三角形检索到其扩展边。
class T_Triangle
{
public:
T_Triangle();
int EdgeID[3];// 最好能够按照逆时针进行存储三条边编号
int PtID[3]; // 最好能够逆时针存储三个点编号
virtual ~T_Triangle();
};
（4） 三角网结构
三角网是由一组三角形构成的，三角形由一组边构成，边由点构成。故建立点表，边表以及三角形表，方便索引。
class T_Tin
{
public:
T_Tin();
virtual ~T_Tin();
vector PointList; // 点表
vector EdgeList; // 线表
vector TriList; // 三角表
// 成员函数省略
};
4.2.2 算法步骤
三角网生长法主要是分为两个步骤，生成初始三角形和扩展三角网。
（1） 生成第一个三角形
a) 选择最短边作为第一条边，得到第一边（Pt1Pt2），加入到边表
b) 选择第三点Pt3， Pt3为顶点的角（角Pt1 Pt3 Pt2 ）最大的点作为第三点，新边加入边表
c) 得到第一个三角形，将该三角形加入到三角表
（2） 扩展TIN（如右图1所示）
a) 三角形边表出一个三角形作为扩展三角形（如ABC）
b) 取该三角形可扩展边进行逐一扩展（如AB），可扩展边是指不是公共边，可以在此基础上在生成新的三角形。
c) 找与扩展边（如AB）组成三角形的第三点(P)
i. 第三点与扩展点C在扩展边异侧，扩展点是指扩展三角形（如ABC）中除扩展边端点（AB）的另外点C
ii. 使得角APB最大的点P作为第三点
d) 生成新边（如FA，FB）
i. 若新边在边表存在，则标记为不可扩展
ii. 若新边在边表不存在，则标记可扩展，且加入边表
e) 生成新三角形(如AFB)，加入三角形表，并将扩展边（如AB）标记为不可扩展，再扩展另一条可扩展边（如AC）
f) 直至三角形表为空 图1
4.2.3 程序中存在的问题
（1）数据结构的通用性不够
本程序设计的数据结构，点结构，有向边结构以及三角形结构都是非常好的，但是对于三角网的结构如果采用表结构，对LOP算法的实现会比较麻烦，因为经常需要更改局部的三角网，这样需要出一些三角形，同时需要进入一些新的三角形，这样会可能涉及到三角形的插入和删除，用向量表结构会不太方便。
（2）函数模块分块的粒度不合理
在生成三角网的函数CreateTin(),函数代码非常长，如果能够合理对函数模块进行划分，会使得代码的可读性和清晰性大大提高。
4.3算法优缺点
三角网生长算法的优点在于它每次生成的三角形都是Delaunay三角形，并且不需要对原有生成的Delaunay三角形作修改，即三角网生长法是依次生成三角形的。其缺点在于每次搜索符合条件的第三点（与扩展边构成新Deaunay三角形的点），都需要遍历所有的点，这样使得三角网生成的效率大大降低。故需要从改进点的搜索策略来提高算法效率。
4.4算法改进
在构成Delaunay三角网时，搜索符合条件的第三点，其实只需要搜索其临近的点。故采用分块索引或是二叉树索引的方式，建立点的索引方式，从而方便检索扩展边附近的点，找到符合条件的第三点。通过采用数据分块技术，使不规则的离散点分布“规则化”，由待定点的平面坐标，可以快速检索出所在格网号，从而快速检索处在该点所在的格网及相邻格网中的已知点，从而大大加速查询速度。
点数据分块方法的基本思路是：首先把离散点数据划分成许多大小一样的格网。格网大小取决于应用领域以及离散点分布情况。将离散点的编号按照点坐标投影到相应的格网中，即根据点坐标依次计算得到点所在网格并建立好离散点格网索引。同理对于边和三角形也可以建立格网索引。边的中点是唯一的，三角形的重心是唯一的，我们可以利用边的重点建立边的分块查询，利用三角形的重心建立三角形的分块查询。
