约束四面体部分和三维物体表面重建

该文提出了约束曲面和约束最大空球凸多面体的概念，在此基础上设计了一种在空间区域上约束Delaunay四面体部分的算法，该算法的基本思路是首先对空间区域进行约束最大空球凸多面体剖分，然后在各个约束最大空球凸多面体内部做Delaunay四面体剖分，利用约束Delaunay四面体剖分算法，该文进一步设计了一种三维物体表面重建算法。     

空间散乱点集Delaunay四面体剖分切割算法

提出最大空圆凸多边形和最大空球凸多面体的概念 .在此基础上 ,提出一种空间散乱点集 Delaunay四面体剖分算法 ,即对空间散乱点集首先进行最大空球凸多面体剖分 ,然后在多面体内部作 Delaunay四面体剖分 .这种方法消除了“退化”现象 (平面 3个以上点共圆或空间 4个以上点共球面 )引起的潜在错误 .最后分析了一类常见的 De-launay四面体剖分算法的潜在错误     

空间散点集Delaunay四面体剖分切割算法

提出最大空圆凸多边形和最大空球凸多面体的概念，在此基础上，提出一种空间散乱点集Delaunay四面体剖分算法，即对空间散乱点集首先进行最大空球凸多面体剖分，然后在多面体内部作Delaunay四面体剖分，这种方法消除了“退化”现象（平面3个以上点共圆或空间4个以上点共球面）引起的潜在错误，最后分析了一类常见的Delaunay四面体剖分算法的潜在错误。     

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

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

3维任意域内点集的Delaunay四面体化研究

Delaunay空球准则广泛应用于3维四面体剖分算法,但标准的Delaunay四面体化只适用于点集的凸包区域,且要求不存在多点共球。为了将Delaunay四面体化更广泛地应用于网络剖分,通过引入局部优化三角形面代替Deluany严格的空球准则,提出了3维任意域内点集Deluanay四面体化(DTETAD)的概念,并首先通过若干关键定理的证明,研究了一个四面体划分是DETEAD的充要条件,然后建立了DTETAD的空球准则。该研究成果为拓展Delaunay算法在更广泛范围的应用提供了理论依据。     

任意多面体的四面体剖分算法

该文提出一种将任意多面体剖分为四面体的算法,该算法首先依据顶点凸凹性算法判定多面体顶点的凸凹性性质,再寻找符合剖分条件的凸顶点,将该凸顶点的凸空间从原多面体中剖分出去,得到一个新的多面体,剖分出来的凸空间再分为多个四面体;再重复对新的多面体进行剖分,直到剖分完毕。该算法的平均时间复杂度为O(N+M),其中N为多面体的凸顶点数目,M为多面体的凹顶点数目。     

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

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

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

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

三维散乱点云快速曲面重建算法

提出了一种基于Delaunay三角剖分的三维散乱点云快速曲面重建算法。算法首先计算点云的Delaunay三角剖分, 从Delaunay四面体提取初始三角网格, 根据Voronoi体元的特征构造优先队列并生成种子三角网格, 然后通过区域生长的方式进行流形提取。实验结果表明, 该算法可以高效、稳定地重构具有复杂拓扑结构、非封闭曲面甚至是非均匀采样的点云数据。与传统的基于Delaunay的方法比较, 该算法仅需要进行一次Delaunay三角剖分, 无须极点的计算, 因此算法的重构速度快。     

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

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

散乱数据曲面造型的凸组合Bezier三角曲面片插值方法

本文讨论了在计算机辅助设计和计算机图形学的散乱数据曲面造型中一种有效的凸组合Ｂｅｚｉｅｒ三角曲面片插值方法。构造曲面的方法是对三角剖分的每一条边,得到一个插值已知条件的５次Ｂｅｚｉｅｒ三角曲面片,它与共此边的相邻５次Ｂｅｚｉｅｒ三角曲面片满足Ｃ＾２连续条件,然后对三角剖分的每一个三角形,将三边对应的Ｂｅｚｉｅｒ三角曲面片作凸组合,使之仍然插值已知条件并满足Ｃ＾２连续条件,从数值例子看,效果是不错的     

约束数据域的Delaunay三角剖分算法研究及应用

研究了一种约束Delaunay三角网生成算法,它充分利用分治算法与生长算法的优点,对离散点、构网中实时生成的边及三角形采用分块进行网格索引,有效地减少了搜索目标点、边及三角形的时间,从而提高了构网速度,并将该算法用于地面模型的构建中,实现了地形三维可视化。     

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

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

基于四叉树结构的数字地表模型快速生成算法设计

为了研究数字地表模型的快速生成方法，在总结传统Delaunay三角化算法的基础上，给出了一个基于四叉树结构的数字地表模型快速生成算法的详细设计，该算法的基本思想是首先利用四叉树结构来对离散点进行分割，然后对四叉树叶节点进行Delaunay三角化，再两两合并四叉树节点三角网的凸壳，以快速生成地表表格网模型，该算法是以四叉树为基本单位为实现限定边和限定多边形的快速嵌入，最后给出了算法在不同情况下的测试结果，并对测试结果进行了具体分析，给出了算法的时间效率分析和空间复杂性分析，实测数据结果表明，该算法有着较好的性能，而且也非常稳定，通过实测结果分析和算法的时间效率分析，可以得到算法的时间效率近似为O(nlog(n）），通过算法的空间复杂性分析可以看出，算法可以自动适应不同的点空间分布情况，而且采用四叉树结构也非常有利于限定边和限定多边形的嵌入。     

Triangulating input-constrained planar point sets

We present a linear-time algorithm for computing a triangulation of n points in 2D whose positions are constrained to n disjoint disks of uniform size, after O(nlogn) preprocessing applied to these disks. Our algorithm can be extended to any collection of convex sets of bounded areas and aspect ratios, assuming no point lies in more than some constant number of sets (bounded depth of overlap), and each set contains only a constant number of query points.     

有界曲面剖分的边界递归法

本文针对有界曲面剖分提出了边界递归方法，引进了一种紧凑且富有方法特色的数据结构。在此基础上，外接曲面拟圆准则结合单侧性准则的使用，使得剖分优化过程加快，剖分总体速度得以提高，剖分效果也很好。剖分的输出数据又能方便地被有限元其它环节所处理，是一种合理可行的剖分方法。     

Constrained delaunay triangulations

Given a set ofn vertices in the plane together with a set of noncrossing, straight-line edges, theconstrained Delaunay triangulation (CDT) is the triangulation of the vertices with the following properties: (1) the prespecified edges are included in the triangulation, and (2) it is as close as possible to the Delaunay triangulation. We show that the CDT can be built in optimalO(n logn) time using a divide-and-conquer technique. This matches the time required to build an arbitrary (unconstrained) Delaunay triangulation and the time required to build an arbitrary constrained (non-Delaunay) triagulation. CDTs, because of their relationship with Delaunay triangulations, have a number of properties that make them useful for the finite-element method. Applications also include motion planning in the presence of polygonal obstacles and constrained Euclidean minimum spanning trees, spanning trees subject to the restriction that some edges are prespecified.An earlier version of the results presented here appeared in theProceedings of the Third Annual Symposium on Computational Geometry (1987).     

Algorithm for constrained delaunay triangulation

A direct algorithm for computing constrained Delaunay triangulation in 2-D is presented. The algorithm inserts points along the constrained edges (break lines) to maintain the Delaunay criterion. Since many different insertions are possible, the algorithm computes only those that are on the Delaunay circles of each intersected triangle. A shelling procedure is applied to put triangles together in such a way that completeness and correctness are guaranteed.