三维约束Voronoi剖分

分析了约束面(点、线段、凸多边形)在三维Voronoi网格存在的条件,提出一种构造三维约束Voronoi剖分的算法.该算法的基本思想是在限定线的球覆盖基础上,借助限定面的约束Regular三角化生成关于限定面对称分布的生长点.理论上,对任意的分段线性复合形约束,该算法可以生成满足此约束的Voronoi网格.最后,给出了实例验证以说明文中算法的有效性.

一种断层面约束下的Delaunay三角剖分与等值线生成算法

传统等值线算法在生成等值线图时,往往采用先生成等值线后抠除断层多边形的方法,或者采用先抠除断层多边形再直接生成等值线的方法。这两种方法均忽略了断层处的层位信息,因而在断层面附近的精度达不到现代油气资源勘探的要求。对断层面与解释层位交点进行精细处理,通过对断层数据的细分加密得到断层面的精确控制点序列,使用Clough-Tocher插值方法进行插值,获得断层面处层位点的高程,提高等值线在断层面处的精度。研究断层面约束的Delaunay三角剖分,设计光滑等值线快速生成算法。形成断层面约束下的层位等值线自动生成技术模块。结果表明,该方法不仅提高等值线绘制的精度,同时也有效降低等值线查找的复杂度,提高了计算效率。

基于特征约束的四面体剖分方法研究

针对地下空间复杂曲面约束情况,文中提出一种对多地层表面模型进行约束Delaunay四面体剖分构建地质体模型的方法,即利用Delaunay三角网构建地层约束,通过限定四面体单元半径边长比和最小二面角等特征约束控制网格质量剖分生成地质体的四面体格网模型。以陕西省某地区为例,应用此方法构建顾及地下空间约束及可视化效果较好的三维地质模型。实验表明,该方法可生成满足约束条件要求且格网质量较高的地质模型,可为地下矿体开采等实际生产提供数据支持。

基于Delaunay三角剖分生成Voronoi图算法

针对Delaunay三角网生长算法和间接生成Voronoi图算法构网效率不高的问题,提出了一种Delaunay三角网生长法间接生成Voronoi图的改进算法。该算法以点集凸壳上一边快速生成种子三角形,定义了半封闭边界点的概念,在三角形扩展过程中动态删除封闭点及半封闭边界点,加快Delaunay三角网生成速度。然后又定义了有序目标三角形的概念,该算法能迅速查找点的有序目标三角形,生成无射线的Voronoi图;考虑凸壳上点的特性,借助三个无穷点生成带射线的Voronoi图。通过实验结果分析表明,改进的算法执行效率有了很大提高。

无线传感器网络中基于Voronoi覆盖及Delaunay三角剖分图的最小刚性拓扑控制算法

为同时满足覆盖与节能应用需求,本文提出了无线传感器网络中一种最小刚性拓扑控制算法MRTc(Minimal rigid topology control algorithm based on Voronoi coverage and Delaunay triangulation).该算法基于Voronoi覆盖机制,准确控制节点工作状态,实现活动节点对目标区域的完全覆盖.在此基础上,MRTc利用Delaunay三角剖分图的特点,构建出适用于无线传感器网络的最小刚性拓扑结构.该结构有效约束了网络平均节点度,且同时具有容错性、覆盖性和稀疏性.此外,MRTc引入节点功率控制策略,在维持网络完全覆盖的基础上最小化节点能耗.仿真结果进一步验证了本文提出的MRTc算法的有效性.

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

在分析现有非结构化网格剖分算法的基础上,提出了一种GIS支持下的改进分治算法实现约束Delaunay三角网格剖分。该方法利用了GIS的空间拓扑关系对算法输入数据进行预处理,基于三角形的统一数据结构实现了网格细化,对输出剖分网格进行准确的拓扑和约束条件的检查,并基于推进阵面算法思想,结合空间邻近拓扑关系实现了三角剖分节点和网格的重新编号,方便了实际问题中开边界条件的赋值,提高了计算效率。实例应用表明,该方法大大简化了数值模型非结构化网格剖分的前处理过程,集成了几种综合算法的优点,在保证原分治算法时间复杂度的基础上,提高了约束条件下Delaunay三角网格生成的质量。

Delaunay三角网剖分的约束边嵌入改进算法

重点研究约束边强行嵌入D-三角网的问题。约束边嵌入是解决D-三角网转变为CD-三角网的一种非常有效的方法,而CD-三角网才能真实地虚拟地形地貌。针对基于凸凹判定的对角线交换算法存在的缺陷,提出"分裂约束边"的思想完善算法的健壮性,并引入快速点定位算法以提高算法的执行效率。

约束Delaunay三角剖分中强行嵌入约束边的多对角线交换算法

在不允许改变原有点集的场合，实现约束Ｄｅｌａｕｎａｙ 三角剖分的一种有效算法是：将边界点与内点一起进行标准Ｄｅｌａｕｎａｙ 三角剖分，然后强行嵌入不在剖分中的约束边，最后删除域外三角形．其中，任意一条待嵌入约束边所经三角形构成的多边形区域称为该约束边的影响域，影响域内部的每条边称为对角线．文中对一般形状影响域中对角线的可交换性进行了研究，并在此基础上，结合对已有算法的分析和借鉴，提出并证明了两种强行嵌入约束边的多对角线交换算法，即递减算法与循环算法．

基于带约束三角剖分的三维巷道建模方法

提出了具有可行性的巷道模型实现方法,将巷道模型抽象为顶盘面、底盘面和侧面3部分。在获取巷道顶盘(或底盘)边界测量数据的条件下,提出了采用约束三角剖分的方法生成巷道模型的上下底盘面,利用两段成面法生成巷道模型的侧面,最后将这些面组合成巷道模型。该方法可以一次性地生成某一开采层面的全部巷道模型,并已成功地运用到以GeoView为平台的"数字紫金"项目中,取得了良好的效果。

一种带岛屿约束数据域的三角网剖分算法研究

文中对多边形内部三角剖分算法及具有属性的带岛屿的约束数据域的D -三角剖分算法进行了研究 ,提出了一种适用于多边形内部的基于“最小内角优先原则”D -三角剖分算法及适用于多边形内、外部构网通用三角剖分算法 ,算法充分考虑到了构网数据域中存在多种不同属性块 ,并成功将算法应用于工程项目之中。

任意多边形内带特征约束的散列数据的最优三角剖分

给出了一种新的基于Ｄｅｌａｕｎａｙ三角形化的任意多边形边界内散列数据的优化三角剖分算法。该算法可允许散列数据带任意复杂的折线及封闭多边形环的特征约束。算法用统一的数据结构来记录散列数据、约束特征和三角剖分信息，并且引入了辅助窗的概念。

Delaunay三角网剖分中嵌入约束边的局部调整算法

提出了一种建立约束Delaunay三角网 (CDT)的算法 ,该算法对约束数据集先建立非约束Delaunay三角网 ,然后嵌入约束边对其影响域按角度最大原则进行局部调整 ,同时使其满足CDT的性质。详细地说明了在CDT中嵌入约束边的过程 ,同时给出了三角网拓扑关系更新的方法 ,最后对算法的时间效率进行了分析。该算法执行效率高 。

带内边界约束散乱数据的Delaunay三角剖分算法研究

带内边界约束条件点集的三角剖分是有限元分析、计算机图形学及真实感图形等许多领域常遇到的一个基本问题。在已有算Delauney法的基础上通过插入中点恢复约束边界,较好地实现了带内边界约束散乱数据的三角剖分。

约束数据域的Delaunay三角剖分与修改算法

顾及地形特征线的散点域 (约束数据域 )三角剖分是建立高精度数字地面模型的基础 ,在 GIS、地学分析、计算几何、多分辨率 DTM等领域中有着广泛的应用。本文研究了约束数据域的 Delaunay三角剖分问题 ,简要分析了现存的算法特点并提出了约束数据域的

Delaunay三角网剖分中的约束边嵌入算法

约束边嵌入是解决D-三角网转变为CD-三角网的一种非常有效的方法,而CD-三角网才能真实地虚拟地形地貌。该文研究了约束边嵌入D-三角网的问题,介绍了约束边嵌入算法的一些基本概念,分析了现存算法的特点,提出了改进的约束边嵌入算法——"插入-交换"算法。该算法能有效地处理各种特殊情况,程序实现简单,符合工程需求。

约束Delaunay三角剖分动态算法研究

提出了动态建立约束 Delaunay三角剖分 ( CDT)的算法 ,即在三角网剖分中可以动态地插入点或约束边 ,因此 ,该算法构建 CDT的点集是可以动态扩充的。通过对动态算法的执行过程分析得出 ,在约束边已知的条件下 ,应尽早在三角剖分中嵌入约束边。这样 ,相对于传统算法 ,不仅能减少嵌入约束边的时间 ,同时也能减少插入点重新构网的时间。最后 ,通过实例比较了动态算法构建 CDT、传统算法构建 CDT和只构建标准 Delaunay三角剖分三者间的时间效率 ,得出动态算法优于传统算法的结论。

带岛屿约束的三角形空间剖分算法的改进方法

本文针对数值模拟中三角形有限元网格的具体要求,对经典的Bowyer-watson算法作了局部改进,利用具有岛屿约束的Delaunay剖分方法来构建三角形网格,使其适用于有岛屿、关键点和特征线约束的区域剖分的要求。此方法在(苏州,无锡,常州)以下简称苏锡常地区地下水流数值模拟中得到了应用,结果表明此方法自动生成带岛屿约束的三角形网格是可行的。

一种新的带特征约束的Delaunay三角剖分算法

本文提出了一种新的带特征的约束条件的散乱数据Delaunay三角剖分算法 .本算法通过在特征线上加入若干数据点 ,使得在保留特征线的同时 ,最终的剖分结果也满足全局Delaunay特性 .与现有同类算法相比 ,本算法更充分地利用了Delaunay三角剖分中的圆准则 ,从而大大减少了所需加入的附加点数 .实验结果证实了本算法的这一特性 .

基于约束Delaunay三角划分法在节理图上实现网格自动剖分

分析了现有的在节理图上自动生成有限元网格方法的不足之处,提出了应用约束Delaunay三角划分法来实现网格剖分。该方法将所有的节理线看作特征约束线,在散乱点约束的Delaunay三角划分的基础上,逐次嵌入约束线,然后再应用细化算法进行网格加密,得到符合数值计算精度要求的网格。

运用加权Voronoi图进行点集剖分的两种方法

在加权Voronoi图定义的基础上,提出了点集剖分的两种新方法:基于线的剖分法和基于角度的剖分法.运用新方法对点集进行加权Voronoi剖分,可以得到各点更加合理、有效的影响区域.