基于约束Delaunay三角剖分进行数模建

基于约束Delaunay三角剖分进行数模建摘要分析了各种三角网生成算法，选定逐点插入算法进行三角构网，并对该算法进行了优化处理。在数据点集不变的情况下，提出了交换对角线的算法以进行数字地面模型的建构，使得数模成果真实地反映了地面情况。关键词数字地面模型Delaunay三角网约束边嵌入算法1前言数字地面模型（DigitalTerrainModal，简称DTM）是地表勘测成果的数字化表现形式，它广泛应用于公路勘测设计一体化、地理信息系统等领域中。其主要实现形式是不规则三角网（TriangulationIrregularNet，简称TIN）。Delaunay三角网〔1〕具有空外接圆，以及最小角最大的性质，可最大限度的保证网中三角形满足近似等边（角）性，避免了过于狭长和尖锐的三角形的出现，是公认的最优三角网。鉴于此，对二维域内点集进行Delaunay三角剖分是当今流行的TIN构网技术。本文主要介绍了用逐点插入算法来生成Delaunay三角网，并讨论了如何在不改变点集的情况下实现约束边的嵌入，这符合数据采集及数模生成的规则，可以方便地处理地表上的陡坎线、断裂线等，真实地反映地表情况。2建立无约束三角网关于Delaunay三角网的生成算法，已经有了二十多年的研究，现在已趋于成熟，其主流算法有三种：分割－归并法，逐点插入法，三角网生长法。其中三角网生长法已不常见，分割－归并法和逐点插入法各有优缺点，分治算法由于递归执行，因而需要较大的内存空间，消耗系统资源，但时间复杂度要好。逐点插入法实现简单，占用内存较小，其时间复杂度差一些，但可以从数据的组织和管理上采用新方法，使之在时间和空间上达到最佳，并且逐点插入是一种动态剖分方法，有利于以后对DTM的维护和更新，是一种较好的构建DTM的剖分方法。综合分析各算法，本文采用逐点插入法进行构网，分析了该算法中制约运行速度的因素，在数三角网拓扑关系、三角形的查找、LOP算法（LocalOptimizationProcedure）等方面进行了优化处理，使之有了较高的执行效率。2.1数据结构在采用逐点插入进行Delaunay三角剖分的过程中，存在大量的查询操作，利用数据结构提供三角形之间的拓扑信息，能够有效地提高算法效率。边结构应包含点与三角形的信息，三角形结构应包含点与边的信息，再考虑到构网过程中动态的数据更新，算法中采用了双向链表结构，以方便于剖分过程中新旧边（三角形）的添加、删除工作。三角形拓扑关系如图1。2.2算法原理逐点插入法是Lawson在1977年提出的，该算法思路简单，易于编程实现。基本原理为：对于已有的三角网络，向其中插入一点，该点与包含它的三角形三个顶点相连，形成三个新的三角形，然后逐个对它们进行空外接圆检测，通过交换对角线的方法来保证所形成的三角网为Delaunay三角网。2.3算法基本步骤逐点插入算法主要执行步骤如图2所示。在按图4(a)进行剖分时，添加了三条新边及三个新三角形NT，删除了旧三角形T。同样，在图4(b)的情况中，记录点所在的边E，根据拓扑关系，找出该边的左右相邻三角形T1，T2，添加四条新边和四个新三角形NT，删除T1，T2以及边E。构网的关键是对新剖分出的三角形用LOP算法进行优化，其基本过程为：新三角形与周围的三角形构成共用同一条对角线的四边形，逐个对四边形中的两个三角形进行空外接圆检测，如果满足空外接圆准则，则略过。如果不满足，则用另一对角线替换现有对角线，在交换对角线后，又会产生相应的新四边形，继续进行空外接圆检测。这种方法可连续进行,直到全部满足空外接准则为止。这个过程是随着数据点P的逐次插入，与三角剖分同时进行的，可以通过递归调用优化程序来实现。2.4算法分析通过以上的分析来看，逐点插入进行Delaunay三角剖分算法的效率取决于寻找包含新加入点的三角形及LOP优化过程，即构网过程中的第(3)、(4)步。下面介绍一些优化方法，以提高算法的速度。快速查询包含新加入点的三角形是算法效率的关键，通常做法是遍历各个三角形，利用点在多边形中原理进行判断，则算法复杂度最坏为O(n2),n为点数。本文采取三角形面积法来判断点与三角形的关系，同时结合三角形之间的拓扑关系，可方便的找到包含新点的三角形。该方法简单易行，其基本原理是通过多边形面积公式来计算三角形面积，然后根据面积结果判断点是否在三角形内。该面积结果有正有负，这与三角形三个顶点的排列顺序有关。如图5，约定三角形的顶点按照顺时针方向排列，已知P1，P2，P3的坐标分别为(x1，y1)、(x2，y21)、(x3，y3)，分别计算数据点P与三角形三个顶点所形成的新三角形ΔPP1P2，ΔPP2P3，ΔPP3P1的面积S1，S2，S3，此时点P在三角形T内，三个面积同为负值：S10，S20，S30而P'点在三角形T外。计算三角形ΔP'P1P2，ΔP'P2P3，ΔP'P3P1的面积S'1，S'2，S'3,可知:S'10，S'20，S'30这说明若点在三角形外，则至少有一个面积是大于零的。通过这种大于零的面积可以指明三角形的查找方向，如S'30，则点P'必在对应边P3P1的另一侧，然后根据拓扑关系，找到边P3P1的相邻三角形，继续用三角形面积法判断，直至它们同时小于零为止，这样便找到了目标三角形。以此方法编制点与三角形的关系函数Point－in－Triangle（P，T），找到目标三角形，若与三角形某顶点重合，则记录该点，函数返回0；点在三角形内，记录该三角形，函数返回1；点在三角形的某个边上，记录该边，返回2。对三角形都进行空外接圆检测，常见做法是计算其中一个三角形的外接圆圆心及半径，然后利用第四顶点到圆心的距离来判断是否满足空外接圆法则。这个过程要多次执行开方、平方等运算，执行效率较低，在程序中占用大量CPU时间。本文采用了简单直观的方法来判断，如图6，求出E两侧相对应的两对顶角∠P1、∠P4的弧度值：(1)∠P1＋∠P4π，第四顶点P4在三角形ΔP1P2P3的外接圆之外，对角线不需交换。(2)∠P1＋∠P4=π，P4在圆周上，对角线选择任意，程序规定不需交换。(3)∠P1＋∠P4π，P4在圆周外，对角线不需交换。建立测试是否交换对角线的函数SwapTest（E）,若需交换则返回TRUE，不需交换返回FALSE。已知上述函数，交换对角线进行LOP优化。程序中采用了双向链表结构，且结构中建立了良好的拓扑关系，在优化过程中，可以方便地进行三角形的动态添加及删除。3嵌入约束边重新构网按前所述，无约束的Delaunay三角剖分业已完成，现在进行约束边的嵌入。对于约束边，其两端点必定在剖分结果中。考虑到已知离散数据点是确定的，不可改变的，在这样不能添加附加点的情况下，只有通过交换对角线的方法来实现约束边的嵌入。这里规定几个术语，待嵌入约束边的一端点称为起始点，另一端点称为目标点。待嵌入约束边所经过的三角形构成的多边形区域称为影响域〔2〕，如图7。影响域内与约束边相交的边称为影响域的对角线。我们的目标即是从起始点出发，按照一定的规则逐步交换域内对角线，最终使起始点与目标点相连，即得到了所需的约束边。3.1对角线交换算法基本思想程序中使用了四边形对角线交换算法，其基本思想是：从约束线起点出发，在影响域内，对所遇到的对角线进行可交换性判断，若可交换，则交换，不可交换就判断下一条，达到最后一条对角线后，第一轮交换结束。然后从头再来，开始下一轮，直到将约束边嵌入为止。如图8。对角线交换之后，会产生新的对角线。对新对角线的处理，是随交换同时进行的动态添加过程。这在算法步骤中，有详细的阐述。3.2对角线交换算法步骤已知Delaunay三角剖分完毕，构网成果中包含三角形间的拓扑关系。约束边起点OP，目标点TP，约束边标记为CE，对角线交换步骤如图9。根据以上过程编制约束构网函数OnConstraintNet()。4程序的实现在实际工作中，用VC＋＋在微机上编程实现上述算法，三角构网核心算法实现如下：voidOnConstructTriNet(){Triangle＊t0=headt;//三角形链表表头Point＊p0=headp;//点链表表头while(p0){intn=Point－in－Triangle(p0,t0);if(n==0){//重点//提示“重点”，是否删除，继续下一点}elseif(n==1){//点在三角形内，需优化//生成三条新边、三个新三角形，删除旧三角形，建立新的拓扑关系//记录三个新四边形的对角线e1，e2，e3Optimize－Edge(e1);Optimize－Edge(e2);Optimize－Edge(e3);}//调用优化函数else{//点在边上//生成四条新边、四个新三角形，删除旧边、旧三角形，建立新的拓扑关系//记录四个新四边形的对角线e1，e2，e3，e4Optimize－Edge(e1);Optimize－Edge(e2);Optimize－Edge(e3);Optimize－Edge(e4);}//调用优化函数p0=p0－next;}//读取下一点OnConstraintNet();}//约束构网//删除不必要的三角形//删除不必要的边//数模成果保存5结论本文讨论了Delaunay三角网的生成算法，以及在Delaunay三角剖分中强行嵌入约束边的多对角线交换算法，探讨了一个从构网到约束的DTM构建全过程。在分析逐点插入算法各制约因素的基础上，提出了优化方法，结合有利的三角网拓扑关系，大大提高了该算法的执行效率。然后在无约束构网成果中嵌入约束边，使数模真实地反映现实情况，满足工程实际的要求。参考文献〔1〕闵卫东，唐泽圣，二维任意域内点集的Delaunay三角划分的研究，计算机学报，1995，18(5)：357－437〔2〕卢朝阳，吴成柯，陆心如，简单多边形的优化三角剖分，电子学报，1991，19(2)：82－87