第5期
赵晓东等:基于GIS的高质量约束Delaunay三角网格剖分
第25页
征线的方法进行约束重构,可以证明该重构方法是收敛的[4],具体步骤如下:1)对于任一条约束直线,查找与之相交的三角形,即该约束线穿越的所有三角形组成的影响域;2)删除该影响域内的所有三角形,形成一个多边形空腔,称为恢复域;3)以该约束直线为界将恢复域一分为二,形成两个多边形子域;4)对这两个多边形子域进行Delaunay三角剖分,得到包含约束直线的影响域内的三角剖分;5)重复上述步骤,直至所有的约束线都被加入。1.3 基于三角形的统一数据结构
Delaunay三角剖分涉及三角形和线段两类几何数据,如果将线段表示为退化的三角形势必增加算法特殊情况判断的冗余。如图1a所示,利用/影子0层表示完整的三角形结构,凸壳上的每一线段有一个顶点在无穷远处(算法中采用空指针)的/影子0三角形,特征线段有两个/影子0三角形。图1b中下端虚线三角形为子网合并中新建的/影子0三角形,阴影的三角形采用局部LOP优化算法[7],保证三角形的Delaunay

特性。
规则2:一个三角形的外接圆是唯一经过三角形3个顶点的圆。如果三角形的一个角度过小或面积过大的情况下满足了约束条件,则称该三角形为坏三角形。如图3所示,以外心顶点(外接圆的中心)作为插入点进行分割。
图3 每个坏三角形线在外心顶点插入分割[9]
Fig.3 Eachbadtriangleissplitbyinsertingavertex
atitscircumcenter
剖分细化具体算法如下:1)取约束线段集合中的每一条约束线段,检查它是否被其他点侵入,是则转第2步;否则转第3步。2)按规则1将约束线段分割,将新的约束线段加入约束线段集合,转第1步。3)取剖分三角形集合的三角形进行检查,全部合格,转第5步;否则,对于不满足约束条件的三角形按规则2插入点。4)如果插入点不侵入约束线段,将该点插入网格中,转第3步;否则,转第2步。5)算法收敛停止。
2 GIS支持下约束Delaunay三角网格剖分
高质量Delaunay三角网格意味着必须满足一定的约束条件,而约束条件是根据工程需要或者数值模拟的条件给定的,如流体动力学问题一般在边
图1 分治算法的三角形数据结构和子网合并[9]
Fig.1 Datastructureoftriangleandhalfwaythroughamerge
stepofthedividingandconqueringalgorithm
界、结构物和扩散源附近采取网格加密方法,这些都要对输入点集进行预处理;输出的剖分三角形内角不能太大也不能太小,面积梯度变化适中。因此,要实现本文提出的非结构网格生成算法,需要提取计算区域边界点的坐标,包括外边界和内边界上各节点光滑、间距的处理、内部约束特征线的设置等。如图4所示,这些预处理都可以在GIS的支持下完成,同时可以实现空间数据的管理,保证数据的拓扑准确性和剖分三角网格的正确性。2.1 边界点的输入
剖分算法输入的为点集的坐标值,非实际的拓扑数据,而且边界点组织直接影响到剖分输出的结果,需要在输入前进行必要的预处理。如图4所示,按照拓扑关系,将输入数据划分为Polygon、Polyline和Point3种矢量数据,其涵盖了流体动力学问题中的海岸边界、岛屿、开边界和水深等高线等所有输入
1.4 网格细化修正
剖分细化是在网格中插入顶点细化网格,使得
网格最大和最小角满足约束。本文采用Shewchuk的细化算法[9,10],它是对Ruppert和Chew提出算法[11,12]的综合改进算法,顶点插入使用LOP算法[7],保证Delaunay特性,遵循两个规则:
规则1:一条线段的直径圆是唯一且最小的包含该线段的圆。如图2所示,如果有一点位于直径园内,则称该线段被侵入。任何被侵入线段在其中点

位置插入顶点进行分割。
图2 线段被递归细分直至不被侵入为止[9]
Fig.2 Segmentsaresplitrecursivelyuntilno

are数据。其中,海岸边界采用Douglas-Peucker算法做,,
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三角网,然后再将各条约束线段通过局部更新,依次嵌入...
热门文档