基于GIS的高质量约束Delaunay三角网格剖分  

High-Quality Constrained Delaunay Triangulation Based on GIS

作　　者：赵晓东[1] 晏小宝[1] 沈永明[2] 王亮[2] 

机构地区：[1]大连大学院士创业园中日地层环境科学研究中心,辽宁大连116622 [2]大连理工大学海岸和近海工程国家重点实验室,辽宁大连116023

出　　处：《地理与地理信息科学》2010年第5期24-28,共5页Geography and Geo-Information Science

基　　金：国家自然科学基金重点项目(50839001);国家自然科学基金项目(50874021;50779006);辽宁省高等学校科研项目计划(L20100321)

摘　　要：在分析现有非结构化网格剖分算法的基础上,提出了一种GIS支持下的改进分治算法实现约束Delaunay三角网格剖分。该方法利用了GIS的空间拓扑关系对算法输入数据进行预处理,基于三角形的统一数据结构实现了网格细化,对输出剖分网格进行准确的拓扑和约束条件的检查,并基于推进阵面算法思想,结合空间邻近拓扑关系实现了三角剖分节点和网格的重新编号,方便了实际问题中开边界条件的赋值,提高了计算效率。实例应用表明,该方法大大简化了数值模型非结构化网格剖分的前处理过程,集成了几种综合算法的优点,在保证原分治算法时间复杂度的基础上,提高了约束条件下Delaunay三角网格生成的质量。The unstructured mesh generation is one of the key technical issues in many fields such as mechanical computation and numerical simulation.Based on the analysis of existing unstructured mesh generation algorithms,the improved divide-and-conquer algorithm supported by GIS is proposed to deal with constrained Delaunay triangulation.This method makes use of the GIS spatial topological relations to handle the pre-processing of input algorithm data,implements Delaunay refinement using a triangle-based data structure,and checks the output meshes with accurate topology and constraints.Based on the idea of advancing front algorithm and spatial topological relations between the mesh nodes and triangulation,the re-numbering algorithm is also proposed to facilitate the assignment of the open boundary conditions as well as improving the computational efficiency.The application to the practical simulation shows that the proposed method can simplify numerical model pre-processing of unstructured mesh generation,preserve the advantages of several algorithms with the original running time,and improve the quality of constrained Delaunay triangulations.

关 键 词：网格剖分 GIS 约束DELAUNAY三角剖分 

分 类 号：P208[天文地球—地图制图学与地理信息工程]