基于最小距离简单多边形的Delaunay三角剖分算法

简单多边形的Delaunay三角剖分,在计算机图形学及三维建模领域有着广泛的应用.提出了一种时间复杂度为O((n-4)2)的基于三角形顶点距离最小的简单多边形Delaunay三角剖分算法.通过三角形顶点的最小距离,形成简单多边形的初始三角网,而后对初始三角网进行Delaunay剖分,并对算法的时间复杂度进行了分析.通过实例表明,此算法在时间复杂度和三角形形态质量上都得到了很大改进.     

优化变形能的平面多边形同构剖分

平面多边形间的同构三角剖分是平面形状渐进过渡与插值的基础,降低对应三角形的变形程度是获得高质量应用的关键.文中提出一种基于变形能优化的2个平面多边形的同构剖分算法,其中包含同构剖分生成和变形能最小化2个模块.首先根据用户指定的对应特征点对多边形进行顶点重采样,得到顶点一一对应的2个多边形;然后利用带约束的Delaunay剖分对其中的一个多边形进行三角化,得到源网格;再用重心坐标将源网格的内部顶点嵌入到另一个多边形得到同构剖分(目标网格);最后逐一检查三角形的变形能,对源网格中变形能超过阈值的三角形进行细分,用同构剖分模块生成新的目标网格.实验及数据统计分析表明,该算法可以得到较好的同构三角剖分,提升网格质量,并能很好地避免纹理细节失真.     

基于凹凸顶点判定的简单多边形的三角剖分

本文提出了一种基于凹凸顶点判定的简单多边形的三角剖分,该算法首先计算简单多边形顶点的凹凸性,然后用环形追踪算法到一个三角剖分,最后通过局部变换得到一个较好的三角剖分。     

三维不规则三角网格的精确裁剪算法

给出了一种基于约束Delaunay三角剖分的三维不规则三角网格的精确裁剪算法。算法结合TIN数据的生成特点,首先将TIN投影到二维平面,然后利用约束Delaunay三角剖分把裁剪多边形的每条边嵌入三角网中,再利用边-三角形的拓扑关系删除裁剪多边形外部多余三角形,最后利用边-点的拓扑关系对裁剪多边形顶点高程进行插值,使生成裁剪后的TIN模型。对不同复杂程度的三维TIN模型进行裁剪实验,发现二维投影策略极大地提高了三维TIN裁剪效率。算法的程序实现简单,且符合工程需求。     

基于三角基的平面多边形变形

本文讲解在VC 6.0环境下解通过对初始多边形和目标多边形进行Delaunay三角剖分,给出描述三角形网格各顶点空间位置的内在结构矩阵,然后插值相应的三角网格结构矩阵,实现多边形之间的形状变化。     

基于三角基的平面多边形变形

本文讲解在VC＋＋6．0环境下解通过对初始多边形和目标多边形进行Delaunay三角剖分,给出描述三角形网格各顶点空间位置的内在结构矩阵,然后插值相应的三角网格结构矩阵,实现多边形之间的形状变化。     

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

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

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

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

GIS中TIN模型的实现算法

文章在总结采用前人的三角剖分算法的基础上,提出了一种快速,有效,由不规则点集生成TIN的算法,并通过Visual C++语言实现.所生成的三角网满足Delaunay准则;并通过实例验证了算法的有效性.     

统一于NIP的多边形三角剖分算法

本文提出一个简洁的、完整的、统一于非自交多边形(NIP)的多边形三角剖分算法,该算法分成两部分:其一是将任意多边形转化为非自交多边形;其二是非自交多边形的三角剖分。最后给出该算法在三维立体造型中的应用。     

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

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

An algorithm for triangulating multiple 3D polygons

We present an algorithm for obtaining a triangulation of multiple, non‐planar 3D polygons. The output minimizes additive weights, such as the total triangle areas or the total dihedral angles between adjacent triangles. Our algorithm generalizes a classical method for optimally triangulating a single polygon. The key novelty is a mechanism for avoiding non‐manifold outputs for two and more input polygons without compromising optimality. For better performance on real‐world data, we also propose an approximate solution by feeding the algorithm with a reduced set of triangles. In particular, we demonstrate experimentally that the triangles in the Delaunay tetrahedralization of the polygon vertices offer a reasonable trade off between performance and optimality.     

Perceptually stable regions for arbitrary polygons

Zou and Yan have recently developed a skeletonization algorithm of digital shapes based on a regularity/singularity analysis; they use the polygon whose vertices are the boundary pixels of the image to compute a constrained Delaunay triangulation (CDT) in order to find local symmetries and stable regions. Their method has produced good results but it is slow since its complexity depends on the number of contour pixels. This paper presents an extension of their technique to handle arbitrary polygons, not only polygons of short edges. Consequently, not only can we achieve results as good as theirs for digital images, but we can also compute skeletons of polygons of any number of edges. Since we can handle polygonal approximations of figures, the skeletons are more resilient to noise and faster to process.     

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

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

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

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

基于Delaunay三角网的简单面状要素自动注记

为使地图标注中简单面状要素的自动注记更加美观且高效,提出了一套简单面状要素的注记方案.该方案先用重心法试着将文本标注在重心附近,但当重心法不能将文本标注于多边形内部时,则用改进的Delaunay三角网骨架线法将文本顺着骨架线标注,以适应绝大多数多边形.重心法以O(n)的效率快速标注文本,而改进的三角网建网算法提高了建网效率,保证了骨架线方法的可行性.实验结果表明:该方案注记视觉效果良好,注记效率高.     

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

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

任意多边形的Delaunay三角剖分

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

一种基于单调多边形的三角剖分算法

提出了一种基于单调多边形三角化算法,被三角化的多边形可以含有任意 个内孔。先根据边界y(x)方向的局部极值顶点作水平（垂直）分割线,将多边形划分成单连 通y(x)单调多边形,然后再将各单调多边形三角化。算法考虑了各种几何奇异情况,因此比 较稳定。