基于三角网生成法的Delaunay三角网生成算法的研究与实现

基于三角网生长法的Delaunay三角网生成算法***************【摘要】论文简要介绍了Delaunay三角网的性质以及基本生成算法，并重点介绍了三角网生长法的基本原理和算法步骤，并通过设计合理的数据结构，对算法进行实现。对算法进行分析并提出通过构建格网索引，进一步提高三角网生成效率。【关键词】三角网生长法扩展TIN格网索引1.引言数字地形模型DTM（DigitalTerrainModel）是指对地形表面形态属性信息的数字表达，是带有空间位置特征和地形属性特征的数字描述[1]。DTM是GIS的基础数据来源，可用于土地利用现状的分析、合理规划及洪水险情预报等。DTM地形属性为高程时称为数字高程模型(DEM)。DEM主要的三种表示模型为规则格网模型、等高线模型、不规则三角网模型（TriangularIrregularNetwork简称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。classT_Point{public:doublex,y,z;//点的坐标T_Point();virtual~T_Point();};（2）有向边结构有向边存储了起始点号和终点号，并存储了与该边相邻的三角形编号。这样的三角形信息在LOP优化算法中很有用，在三角网生长法可以来判断改变是否是公共边（不可扩展）。useCount是用来记录这条边用了多少次，用了一次，说明不是公共边，可扩展，若是用了两次，说明不可扩展。classT_Edge{public:intstartPt;//起点intendPt;//终点intTriID[2];//边相邻的左右三角形编号，无时为-1intuseCount;//扩展情况，1，可扩展；2；不可扩展(为公共边)，也可以用flag来标记T_Edge();boolfriendoperator==(T_EdgeL1,T_EdgeL2);//判断两条边是否相等virtual~T_Edge();};（3）三角形结构三角形结构按逆时针存储了构成三角形三边编号和三顶点编号。这样可以方便对三角形进行扩展，根据待扩展的三角形检索到其扩展边。classT_Triangle{public:T_Triangle();intEdgeID[3];//最好能够按照逆时针进行存储三条边编号intPtID[3];//最好能够逆时针存储三个点编号virtual~T_Triangle();};（4）三角网结构三角网是由一组三角形构成的，三角形由一组边构成，边由点构成。故建立点表，边表以及三角形表，方便索引。classT_Tin{public:T_Tin();virtual~T_Tin();vectorT_PointPointList;//点表vectorT_EdgeEdgeList;//线表vectorT_TriangleTriList;//三角表//成员函数省略};4.2.2算法步骤三角网生长法主要是分为两个步骤，生成初始三角形和扩展三角网。（1）生成第一个三角形a)选择最短边作为第一条边，得到第一边（Pt1Pt2），加入到边表b)选择第三点Pt3，Pt3为顶点的角（角Pt1Pt3Pt2）最大的点作为第三点，新边加入边表c)得到第一个三角形，将该三角形加入到三角表（2）扩展TIN（如右图1所示）a)三角形边表出一个三角形作为扩展三角形（如ABC）b)取该三角形可扩展边进行逐一扩展（如AB），可扩展边是指不是公共边，可以在此基础上在生成新的三角形。c)找与扩展边（如AB）组成三角形的第三点(P)i.第三点与扩展点C在扩展边异侧，扩展点是指扩展三角形（如ABC）中除扩展边端点（AB）的另外点Cii.使得角APB最大的点P作为第三点d)生成新边（如FA，FB）i.若新边在边表存在，则标记为不可扩展ii.若新边在边表不存在，则标记可扩展，且加入边表e)生成新三角形(如AFB)，加入三角形表，并将扩展边（如AB）标记为不可扩展，再扩展另一条可扩展边（如AC）f)直至三角形表为空图14.2.3程序中存在的问题（1）数据结构的通用性不够本程序设计的数据结构，点结构，有向边结构以及三角形结构都是非常好的，但是对于三角网的结构如果采用表结构，对LOP算法的实现会比较麻烦，因为经常需要更改局部的三角网，这样需要出一些三角形，同时需要进入一些新的三角形，这样会可能涉及到三角形的插入和删除，用向量表结构会不太方便。（2）函数模块分块的粒度不合理在生成三角网的函数CreateTin(),函数代码非常长，如果能够合理对函数模块进行划分，会使得代码的可读性和清晰性大大提高。4.3算法优缺点三角网生长算法的优点在于它每次生成的三角形都是Delaunay三角形，并且不需要对原有生成的Delaunay三角形作修改，即三角网生长法是依次生成三角形的。其缺点在于每次搜索符合条件的第三点（与扩展边构成新Deaunay三角形的点），都需要遍历所有的点，这样使得三角网生成的效率大大降低。故需要从改进点的搜索策略来提高算法效率。4.4算法改进在构成Delaunay三角网时，搜索符合条件的第三点，其实只需要搜索其临近的点。故采用分块索引或是二叉树索引的方式，建立点的索引方式，从而方便检索扩展边附近的点，找到符合条件的第三点。通过采用数据分块技术，使不规则的离散点分布“规则化”，由待定点的平面坐标，可以快速检索出所在格网号，从而快速检索处在该点所在的格网及相邻格网中的已知点，从而大大加速查询速度。点数据分块方法的基本思路是：首先把离散点数据划分成许多大小一样的格网。格网大小取决于应用领域以及离散点分布情况。将离散点的编号按照点坐标投影到相应的格网中，即根据点坐标依次计算得到点所在网格并建立好离散点格网索引。同理对于边和三角形也可以建立格网索引。边的中点是唯一的，三角形的重心是唯一的，我们可以利用边的重点建立边的分块查询，利用三角形的重心建立三角形的分块查询。5.实验通过VisualC++6.0平台，用程序实现了三角网生长法生成Delaunay三角网。（1）鼠标实时点离散点，生成三角网图5-1鼠标点的离散点图5-2生成的Delaunay三角网（2）在原有三角网的基础上继续点离散点（如图5-3所示），重新生成如图5-4所示的三角网图5-3鼠标继续点离散点图5-4重新生成三角网（3）随机生成离散点，生成三角网图5-5生成随机点图5-6生成三角网【参考文献】[1]鲍蕊娜，李向新等.基于凸壳技术的Delaunay三角网生成算法研究[J].科学技术与工程，2011，11（4）[2]张剑清，潘励等.摄影测量学[M].武汉大学出版社2009，武汉[3]徐旭，李源等.一种基于插入法的Delaunay三角网生成算法[J].电脑与信息技术，2010，18（4）