第26卷 第5期2010年9月地理与地理信息科学
GeographyandGeo-InformationScienceVol.26 No.5September2010
基于GIS的高质量约束Delaunay三角网格剖分
赵晓东,晏小宝,沈永明,王 亮
1
1
2
2
(1.大连大学院士创业园中日地层环境科学研究中心,辽宁大连116622;2.大连理工大学海岸和近海工程国家重点实验室,辽宁大连116023)
摘要:在分析现有非结构化网格剖分算法的基础上,提出了一种GIS支持下的改进分治算法实现约束Delaunay三角网格剖分。该方法利用了GIS的空间拓扑关系对算法输入数据进行预处理,基于三角形的统一数据结构实现了网格细化,对输出剖分网格进行准确的拓扑和约束条件的检查,并基于推进阵面算法思想,结合空间邻近拓扑关系实现了三角剖分节点和网格的重新编号,方便了实际问题中开边界条件的赋值,提高了计算效率。实例应用表明,该方法大大简化了数值模型非结构化网格剖分的前处理过程,集成了几种综合算法的优点,在保证原分治算法时间复杂度的基础上,提高了约束条件下Delaunay三角网格生成的质量。关键词:网格剖分;GIS;约束Delaunay三角剖分
中图分类号:P208 文献标识码:A 文章编号:1672-0504(2010)05-0024-05
0 引言
在应用有限元、有限差分和有限体积法对力学问题进行数值计算的前处理中,网格自动剖分占有重要的位置。目前,实现网格剖分的算法很多,而且不断有新的算法推出,其相关研究领域不仅针对数值模拟计算,对GIS数据表达、地学分析、计算机视觉、表面目标重构等众多领域也是一项重要的应用技术[1-3]。网格剖分可分为结构化网格(StructuredGrid)和非结构化网格(UnstructuredGrid)两种。非结构化网格易于控制网格单元大小、形状及网格点位置,可以实现合理分布网格的密度,提高计算精度,因此具有比结构化网格更大的灵活性和对复杂边界更强的适应性。生成二维非结构化网格的常用方法[4]有四叉树法(Quadtree)、Delaunay三角剖分法(DelaunayTriangulation,DT)和推进阵面法(Ad-vancingFrontMethod,AFM)以及几种方法的综合和改进。由于Delaunay三角网是Voronoi图的直线对偶图,具有空外接圆和最大最小角特性,还可以尽可能地避免病态三角形的出现,实现约束条件下的三角剖分,因此,在数值计算非结构化网格剖分和GIS三角网(TIN)的数据格式表达中广泛使用。
目前常见的构建Delaunay三角网的算法有:分治算法(Divide-and-conquer)、逐点插入算法(Incre-mentalInsertion)、生长算法和扫描线算法(Sweep-line)[3,5-7],其中以分治算法效率最高,时间复杂度
为O(NlogN)[5]。由于实际的不同需要,除几何约束条件外,对三角剖分的角度、大小和节点物理量的控制也都有相应约束,目前的剖分算法尚不能满足以上全部约束条件进行剖分。本文基于改进的分治
算法,提供了梯度变化和针对实际问题的单元和节点重编号,并利用GIS强大的空间数据处理和分析功能对算法做数据前后处理,保证了高质量约束Delaunay三角网格剖分的生成。
1 约束Delaunay三角化方法
分治算法[5]的基本思路是把输入点集分割为数个较小的点集,在各个子点集内生成小三角网,再逐级合并的一个递归过程。子点集最终只有两点或者三点,形成一条边、共线边或者三角形。算法必须将点集连接为凸区域(凸壳),对凹区域和多连通区域会产生域外三角形,无法保证约束边的存在。约束Delaunay三角化的分治算法的关键过程及实现方法如下。
1.1 点集划分
原分治算法只有Y轴方向的分割,这里改进为交替分割[8],即点域X轴方向的长度大于Y轴方向的长度,则以X轴方向对半分割点集,否则以Y轴方向对半分割点集。该过程为递归调用的分割过程。
1.2 约束特征线重构
在Delaunay三角剖分上,采用逐次加入约束特
收稿日期:2010-04-21; 修订日期:2010-06-10
基金项目:国家自然科学基金重点项目(50839001);国家自然科学基金项目(50874021、50779006);辽宁省高等学校科研项目计划(L20100321) 作者简介:赵晓东(1969-),男,博士,教授,从事GIS在采矿、岩土工程应用和水动模型耦合的研究。E-mail:xdong.zhao@gmail.com
cone算法都属于基于Delaunay三角剖分的算法。区域生长算法先初始化一个三角形作为...表示候选三角形倾向于外接圆半径最小的三角形;β大则表示对三角网格的质量要求...
基于约束Delaunay三角划分法在节理图上实现网格自动剖分_专业资料。分析了现有... 基于GIS的高质量约束Del... 暂无评价 5页 免费 基于GIS的高质量约束Del......
b ) 第6 期 蒲 浩等:基于约束 Delaunay 三角剖分的道路三维建模方法 ll3 Delete T ()从 T 中删除 ri I ! I $ I = Tadj end while ( left a T ...
约束Delaunay三角剖分与有... 5页 1财富值 基于GIS的高质量约束Delau... ...约束 Delaunay 剖分生成表面模型的表面网格李吉刚 ( 北京航空航天大学 机械工程...
带内外边界约束的平面点... 69人阅读 4页 2.00 基于Delaunay三角剖分...约束Delaunay三角剖分...
带断层约束的Delaunay三角剖分混合算法_天文/地理_自然科学_专业资料 暂无评价
基于SIFT特征提取与Delaunay三角网格剖分算法在图像匹配中的研究_天文/地理_自然科学_专业资料。l l 算法分析 船 基于 SIF T特征提取与 Delaunay 三角网格剖分...
基于边界特征点提取的约束Delaunay三角剖分算法_专业资料。在地形表达上不规则三角网应用广泛,实际中用到最多的也是Delaunay三角网剖分算法。针对约束数据域下的De...
带约束折线的平面散点集Delaunay三角剖分_专业资料。首先将原始散点与约束点一起进行三角剖分,形成初始Delaunay三角网,然后再将各条约束线段通过局部更新,依次嵌入...
热门文档