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

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

二维几何特征自适应有限元网格生成(一)--几何特征识别

发现二维形体边界均匀离散点集Delaunay三角剖分所具有的4个性质．根据这4个性质所描述的Delaunay三角剖分和形体几何特征之间的关系提出几何特征自动识别方法,并建立网格自适应机制,实现三维形体几何特征和部分力学特性自适应有限元网格自动生成．     

平面散乱点集约束Delaunay三角形剖分切割算法

文章提出了一种基于切割的平面散乱点集约束Delaunay三角剖分算法。该算法的基本思路是首先对平面散乱点集作约束最大空圆凸多边形剖分,然后对多边形的内部再作约束Delaunay三角形剖分。文章还证明了平面散乱点集的约束最大空圆凸多边形剖分是唯一的以及约束Delaunay三角剖分的不唯一性仅仅体现在约束最大空圆凸多边形的内部。使用约束最大空圆凸多边形的概念消除了由于“退化”现象（三个以上的点共圆）带来的算法上的潜在错误。     

三维物体表面重建的分支处理算法研究

根据平面点集Delaunay三角剖分的特性,将Delaunay三角剖分应用到分支问题上,改进和实现了一种分支问题处理算法。将相邻层轮廓线投影到同一个剖面上形成一个带约束边的平面点集,并将它们Delaunay三角化,根据这些三角形组来生成新的轮廓线,使轮廓线一一对应。实验结果表明该算法实现的效果较符合实际情况,能有效地处理各种不同情况。     

约束三角剖分在雨量等值线的应用

雨量等值线在水文、防汛领域应用广泛,Delaunay三角剖分具有空外接圆和最大的最小角度两个良好性质,对于非规则分布的离散点数据进行三角剖分内插是生成等值线的最常用的算法,但实际应用中往往都术是凸壳进行三角化,而是有限定边（或限定点）对三角剖分进行约束。该文在标准Delaunay三角剖分基础上,分析了逐点插入法的基本原理,基于此提出了一种解决有限定边的约束三角网格剖分生成等值线的方法,给出了限定边进行三角剖分的算法,同时对边界采用网格加密和邻域内插算子进行边界附件插值,提高等值线的边界拟合精度,并在雨量等值线生成中得到较好应用。     

一种三维离散点数据生成非结构四面体算法

3D离散点数据的Delaunay三角剖分是构造曲面网格的关键技术之一。针对常用的基于三角网递推原理的Delaunay四面体局部构造生成算法中往往存在的四面体不相容问题,本文提出在当前点的局部计算中构造新四面体时,除了参考当前局部计算之前已生成的四面体集约束关系外,同时考虑当前点局部计算过程中生成的四面体集约束关系的非结构四面体生成算法,从而改善了新生成四面体与已有四面体的不相容性。文中最后给出的实验结果验证了本文算法的有效性。     

带特征线约束的Delaunay三角剖分最优算法的研究及实现

为了提高特征线约束的Delaunay三角剖分的速度和功率,从两个方面进行改进;一是生成无约束的Delaunay三角网时,采用进行剖分算法;二是在约束线上插入点时,应用取三角形外接圆与特征线交点的方法。并行剖分算法具有较好的加速性能;“交点”插入算法考虑了特征线的影响域及Delaunay三角形规则的边界条件,在满足全局Delaunay三角剖分的前提下,使插入的点最少,对原有的网格影响最小。     

约束三角剖分在雨量等值线的应用

雨量等值线在水文、防汛领域应用广泛,Delaunay三角剖分具有空外接圆和最大的最小角度两个良好性质,对于非规则分布的离散点数据进行三角剖分内插是生成等值线的最常用的算法,但实际应用中往往都不是凸壳进行三角化,而是有限定边(或限定点)对三角剖分进行约束。该文在标准Delaunay三角剖分基础上,分析了逐点插入法的基本原理,基于此提出了一种解决有限定边的约束三角网格剖分生成等值线的方法,给出了限定边进行三角剖分的算法,同时对边界采用网格加密和邻域内插算子进行边界附件插值,提高等值线的边界拟合精度,并在雨量等值线生成中得到较好应用。     

用随机增量局部转换算法实现三维点集的Delaunay三角剖分

Delaunay三角剖分作为计算几何中的一个核心问题,尤其适用于三维网格生成.因此就需要开发出高效、健壮性的算法来实现.本文在原有算法的基础上提出了随机增量局部转换的算法来实现三维点集的Delaunay三角剖分.采用不退化的四点生成最初的三角剖分,每次加入一点,通过局部交换使新的三角剖分保持Delaunay性质,直到处理完所有点.还讨论了局部交换的思想和对不同面类型的处理方法,给出了两个剖分实例.     

利用Voronoi图改进离散数据重构曲面算法

本文利用Delaunay三角剖分和 Voronoi图的性质,实现了一种对散乱点重构闭合曲面的方法。该方法在搜索策略上进行了改进：首先对输入点进行三角剖分,产生相互独立的四面体,构建一个凸包;然后利用Delaunay三角剖分产生Voronoi图;最后根据Voronoi图的性质,选择包含在形体内部的四面体,提取出边界三角形,完成散乱点边界重构。计算复杂度和Delaunay四面体数量成正比,在自动形状重构时形状边界提取过程的计算复杂度为O(n),算法适用于各种涉及图形重构的工程应用。     

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

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

基于Delaunay三角网的任意多边形三角剖分算法研究

文章通过分析现有多边形三角剖分算法,给出一种基于Delaunay三角网的任意复杂多边形三角剖分的改进算法。算法首先忽略多边形顶点与边线间的逻辑关系,将其看做散乱顶点的集合,然后采用Delaunay三角化方法对点集进行合理剖分,再依据多边形顶点及边线间的逻辑关系,逐一将那些不合理的三角网剔除,最终重新组合出符合要求的三角网格。     

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

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

任意多边形的Delaunay三角剖分

任意多边形的三角剖分是计算机图形学领域中的一个基本算法，其用途非常广泛，本文利用著名的Ｄｅｌａｕｎａｙ三角剖分的优化性质，提出了一个简洁、通用的任意多边形Ｄｅｌａｕｎａｙ三角剖分算法，并给出了该算法在有限元网络自动生成过程的应用。     

一种任意多面体剖分成四面体的改进算法

针对原相关算法中存在的不足,提出了凸顶点的凸空间从原多面体中完整剖分出去的充要条件。引入平面切角和空间切角的概念,使剖分思想更加直观、简化。对空间多边形进行Delaunay三角剖分时,充分考虑了凸空间的结构特点,采用了透视投影的思想,使投影后的平面多面形保持了原空间多边形的拓扑结构和顶点的凹凸性,保证了三角剖分的合理性、正确性。基于空间相关性的思想,对凸顶点的邻接点生成有向空间包围盒,快速排除与凸空间不相交的面,加快了多面体剖分的速度;最后给出了改进后的剖分算法,对相关应用有着极大的实用价值。     

简单多边形快速Delaunay三角剖分算法

简单多边形的Delaunay三角剖分,在计算机图形学及地学问题三维建模领域有着广泛的应用。文中在借鉴他人的基础上,提出了一种时间复杂度为O(mn)的基于三角形权值最大的简单多边形Delaunay三角剖分算法。三角剖分结果中的三角形形态达到了最优或次优,并进行了理论上的严格证明,对算法的时间复杂度进行了分析,并给出了一个实例。实验结果表明,该方法对于随机生成的简单多边形域三角化速度快,平均计算时间呈近似线性。     

增删点后的Voronoi 图生成算法

Voronoi 图可广泛应用于模式识别、计算机图形学、计算机辅助设计、地 理信息系统等领域。利用Voronoi 图及其对偶图Delaunay 三角网构建的不规则三角网TIN 能充分地反映地形地貌特征,对TIN 的统一管理和动态调用可较好地应用到数字高程模型 的建立中。通过联机增量和减量算法来来实现增删点后的Voronoi 图的生成,具有能够动态 修改点集、速度快、效率高等优势。     

Point placement algorithms for Delaunay triangulation of polygonal domains

In some applications of triangulation, such as finite-element mesh generation, the aim is to triangulate a given domain, not just a set of points. One approach to meeting this requirement, while maintaining the desirable properties of Delaunay triangulation, has been to enforce the empty circumcircle property of Delaunay triangulation, subject to the additional constraint that the edges of a polygon be covered by edges of the triangulation. In finite-element mesh generation it is usually necessary to include additional points besides the vertices of the domain boundary. This motivates us to ask whether it is possible to trinagulate a domain by introducing additional points in such a manner that the Delaunay triangulation of the points includes the edges of the domain boundary. We present algorithms that given a multiply connected polygonal domain withN vertices, placeK additional points on the boundary inO(N logN + K) time such that the polygon is covered by the edges of the Delaunay triangulation of theN + K points. Furthermore,K is the minimum number of additional points such that a circle, passing through the endpoints of each boundary edge segment, exists that does not contain in its interior any other part of the domain boundary. We also show that by adding only one more point per edge, certain degeneracies that may otherwise arise can be avoided.