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

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

确定多边形凸凹顶点的快速算法及其应用

提出一种确定任意多边形凸凹顶点的快速算法，该算法的时间复杂性为Ｏ（ｎ）次乘法和Ｏ（ｎ）次比较。还介绍把该算法用于求平面点集的凸包以及对任意的平面多边形进行Ｄｅｌａｕｎａｙ三角剖分。     

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

在不允许改变原有点集的场合,实现约事束Ｄｅｌａｕｎａｙ三角剖分的一种有效算法是,将边界点与内点一起进行标准Ｄｅｌａｕｎａｙ三角剖分,然后强行嵌入不在剖分中的约束边,最后删除城外三角形。其中,任意一条待嵌入约束边所经三角形构成的多边形区域称为该约束边的域,影响域内部的每条边称为对象线。     

基于图的任意域内点集的Delaunay三角剖分算法

本文提出了一种基于图的二维任意域内点集的Ｄｅｌａｕｎａｙ三角剖分算法．该算法首先求出任意域内点集的约束最小生成树，然后逐次加入一边构造三角形网格，最后通过局部优化变换，得到二维任意域内点集的Ｄｅｌａｕｎａｙ三角剖分．本文还给出了该算法在有限元网格自动生成过程中的应用.     

Trimmed曲面的三角剖分算法研究

基于多岛屿任意形状平面域的 扩展Ｄｅｌａｕｎａｙ三角剖分准则，提出了一种通用的Ｔｒｉｍｍｅｄ曲面三角剖分算法。     

一种常用的二维任意域的Delaunay三角剖分算法的健壮性补充

由于对任意给定的平面点集通过Ｄｅｌａｕｎａｙ三角剖分进行处理可得到具有整体最优性的三角形网络,因而该方法得到了广泛的重视。但研究发现,常用的二维任意域Ｄｅｌａｕｎａｙ三角剖分算法＾［１,２］是有缺陷的,它在构成Ｄｅｌａｕｎａｙ三角形候选点的选择过程中,可以使候选点出现“位置违约”的错误,即在候造节点链表中,虽然可出现依据算法的判据有条件成为Ｄｅｌａｕｎａｙ三角形的构成点,但采用该点构成Ｄｅｌａｕｎ     

散乱点集Delaunay三角剖分的分布并行算法

为了加快大数据集Ｄｅｌａｕｎａｙ三角剖分的速度,提出了一种能对任意散乱点集进行Ｄｅｌａｕｎａｙ三角剖分的分布并行算法,算法具有容错性和自动负载平衡的能力,文中对其设计和实现方法进行了详细讨论,对算法的复杂性进行了分析,实验结果表明该算法的加速效果明显。     

三维任意区域中点集的三角剖分算法

本文在已有算法基础上，发展了一种三维任意区域中点集的三角剖分算法。该算法不仅可用于三维点集的标准Ｄｅｌａｕｎａｙ三角剖分，而且可用于带有约束表面及内部含有孔洞情况，可以处理非凸区域的三角剖分问题。算法对点在空间的位置滑任何限制。     

多连通多边形三角化找桥算法的研究及实现

已有的多边形三角化剖分算法,对多连通任意多边形的处理方法不一,算法大多复杂,可靠性低,而且往往只适合于特定的多边形剖分。本文结合现有的多边形三角剖分算法,提出了一个简洁高效、高可靠性的多连通任意多边形三角化剖分的找桥算法,该算法可用于各种多连通任意多边形的三角化剖分处理,并且成功运用于本单位研制开发的城市三维数码景观系统中,收到了较好的效果。     

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

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

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

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

通用点线面集Delaunay三角剖分与动态编辑

总结并提出了一种通用点线面集Delaunay三角剖分与动态编辑的统一算法。可以实现离散点的Delaunay三角剖分,约束线、面的Delaunay三角剖分,任意多边形内带特征约束(包括点、线、面)的三角剖分,一般Delaunay三角剖分的外边界都是其离散点集的凸包,且内岛屿一般没有挖掉,本算法实现了Delaunay三角剖分时内、外边界的保界处理。     

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

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

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

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

用VC语言实现任意多边形的Delaunay完全三角剖分算法

多边形三角剖分是计算几何的一个几何基元，它可以简化问题规模，在计算机图形学、模式识别等方面有重要的应用。本文针对已有的Ddaunay三角剖分算法的不足，提出新算法，并采用Visual C语言MFC类进行链表的管理，使得编程容易实现。整个算法简洁通用。最后给出了在实际中的应用。     

三维重构中任意平面多边形轮廓的自适应Delaunay三角剖分*

根据Delaunay三角剖分唯一、最优的特点,详细阐述了Delaunay三角剖分应用于特定的任意多边形轮廓的实现算法,介绍了相关的轮廓预处理技术,并对本算法提出了两点改进,给出了该三角剖分的应用实例。     

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

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

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

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

A note on lee and schachter's algorithm for delaunay triangulation

Lee and Schachter have presented an algorithm for the Delaunay triangulation of a set of points whose convex hull is a rectangular region. An addendum to that algorithm is presented which gives the Delaunay triangulation of a set of points with an arbitrary convex hull. Timing results are also given.