一种高准确度的约束Delaunay三角网生成算法研究.pdf

《一种高准确度的约束Delaunay三角网生成算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第25卷第1期地理与地理信息科学Vo1．25No．12009年1月GeographyandGeo-InformationScienceJanuary2009一种高准确度的约束Delaunay三角网生成算法研究宋晓眉，张晓东，李建林(中国农业大学信息与电气工程学院，北京100083)摘要：约束线段的嵌入是CDT两步法的关键步骤之一，目前该方面的研究还不够完善，主要忽视了影响区域是凹多边形和影响区域内包含悬挂点的情况。该文研究带有约束条件的Delaunay三角网的生成问题，考虑了约束线段影响区域的特殊情况，采用递归割耳法嵌入约束线段，先将影响区域

2、调整为简单多边形，再递归寻找并割去多边形的耳，最终将影响区域重新三角剖分。该方法可有效提高约束Delaunay三角网的质量。关键词：嵌入约束线段；逐点插入法；递归割耳法；凹凸点中图分类号：P208文献标识码：A文章编号：1672-0504(2009)01～OO99一O4从A到D的方向寻找四边形对角线，可以找到对角线0引言BF、BE和CE。由于第一个四边形脚是凹多边现阶段约束Delaunay三角网(Constrained形，则算法不处理对角线BF；第二个四边形BFEC是DelaunayTriangulation，CD'I、)生成算法的两步法研凸

3、多边形，则交换对角线(图lb)；最后凸四边形CDEF究较多，主要是先生成无约束三角网，再嵌入约束线交换对角线(图le)，第一轮对角线交换结束。第二轮对三角网进行调整。传统的CDT两步法约束线段对角线交换开始后，算法对凸四边形交换对角的嵌入方法很多，对影响区域的处理主要包括两种：线(图ld)。由于算法中没有对新对角线与约束边的一是将影响区域的三角形全部删除后重新建网ll]，相交判断，故不会对凸四边形ACDF进行对角线交其中文献[1]算法较简单且效率较高，但忽略了影响换，约束边永远不会嵌入三角网，程序陷人死循环。区域的一个特殊情况，即影响区域可能

4、存在悬挂综上所述，现阶段两步法的约束线段嵌入研究点l_3](悬挂点不能参与重新建网)。二是对影响区域尚不完善，主要忽视了影响区域多边形是凹多边形和的三角形组成的凸四边形交换对角线_4]，通过多次包含悬挂点的情况。本文采用将影响区域的三角形交换对角线可实现在任意影响域中强行嵌入约束全部删除后递归割耳的约束线段嵌入方法重新建网，边u]，即“多对角线交换算法”；交换后的对角线仍与可有效解决上述问题。文中两步法采用逐点插入法约束边相交，经过多次新对角线与约束边的相交判生成Delaunay三角网；寻找约束线影响区域，消除可断再对凸四边形交换对角线可以嵌

5、入约束边，但算能存在的悬挂点并进行预处理，将影响区域所有点法效率很低。文献[4]省略了新对角线和约束边相顺序连成一个简单多边形；运用递归割耳法剖分多交的判断。如图1a中，线段AD是约束线段，按照边形并进行Iop优化，得到约束Denaulay三角网。DD。E_一一。一(b)(c)(d)图1对角线交换的问题Fig．1Problemsinchangingdiagonallines的自动建立无约束Delaunay三角网的算法基本可1逐点插入法归为4类：逐点插入法、分而治之算法、三角网生1934年Delaunay由Voronoi图演化出Delau—成算

6、法和合成算法。逐点插入法在时间复杂度方面nay三角引，该三角网广泛用于TIN的生成及与不如分而治之和合成算法，但可满足现实需要，且占2．5维分析有关的领域。目前，人们广泛接受和采用用内存少、算法易实现。逐点插入法主要分为3步：收稿日期：2OO8一l1—_2O基金项目：国家“十一五”科技支撑计划项目(2006BAD10A01)作者简介：宋晓眉(1983～)，男，硕士研究生，从事空间数据信息挖掘研究。E～mai1：sxmgreat@sina．com第1期宋晓眉等：一种高准确度的约束I)elaunay三角网生成算法研究第101页CA(a)寻找约束区

7、域(b)约束区域中出现悬挂点(c)连接AG、BG(d)移除线段AB图5消除悬挂点的过程Fig．5Processofeliminatinghoistedpoints2．2递归割耳法8，按照多边形ABCDEF的顺时针方向，在线段FA重新三角剖分影响区域是嵌入约束线段的关键前进方向点B位于右侧，则点A在多边形中显示凸步骤之一。本文采用递归割耳法将影响区域重新三点性；在线段AB前进方向点C位于左侧，则点B在角剖分。首先提出两个定义：多边形中显示凹点性。定义1多边形上点的通视。任意一个多边形、P1P2P3P4⋯Pn，边节点集LPSet={P1，P2，P

8、3，P4，⋯，FPn}，n为正整数。设点集GPSet={多边形内的点}。任取两点Px，Py∈LPSet，设点集LinePointSet一{点EDEDPx和点Py连线