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

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

改进的Delaunay三角网渐次插入生成算法

提出一种改进的Delaunay三角网渐次插入生成算法。在边界初始化阶段,无须对插入点进行排序,只须按链表顺序插入,在LOP算法中,因交换对角线而产生的新三角形只须遵循Delaunay三角化原则由里向外更新邻接三角形。实验结果表明,改进的算法能提高效率,加快Delaunay三角网的构建速度。     

基于三角形法向量的离散点三维构网方法

构建平面不规则三角网的算法已经很成熟,但普遍的算法都是基于某一投影平面,不能满足三维空间离散点的构网要求.本文在研究二维构网生长算法及现有空间三维构网方法的基础上,提出利用空间三角形的法向量实现三维构网,详细讨论该算法的细节问题,并探讨提高构网速度的方法.通过实验证明该算法能快速、有效、稳定地对复杂物体表面离散点构建空间三角网,达到建模效果,同时也体现出其应用范围的广阔性.     

基于三角形法向量的离散点三维构网方法

构建平面不规则三角网的算法已经很成熟,但普遍的算法都是基于某一投影平面,不能满足三维空间离散点的构网要求。本文在研究二维构网生长算法及现有 空间三维构网方法的基础上,提出利用空间三角形的法向量实现三维构网,详细讨论该算法的细节问题,并探讨提高构网速度的方法。通过实验证明该算法能快速、 有效、稳定地对复杂物体表面离散点构建空间三角网,达到建模效果,同时也体现出其应用范围的广阔性。     

平面域中散乱点的Delaunay三角化算法

基于三角网生长算法和分治算法的思想,提出并实现了一个平面域散乱点的三角网格重构算法.算法首先利用分治算法的思想将散乱点集进行分割,然后在四个极值点确定初始三角形的基础上,基于边的扩展原则构造新的三角形,使网格不断向周围扩展直到所有的待扩展的边全部能构成三角形为止,最终构造出整个散乱点集的三角网格.     

几何数据压缩的一种新算法

本文提出一种几何数据压缩的新算法,其基本思想是在已知物体网格边界的条件下,首先寻找边界的凹点,然后建立网格结点的特殊树结构,即横切面树,并将横切面树中相邻节点内网格结点之间的关系表示为链表（三角形条带）,按契约数结构及链表（三角形条带）编码、存储帮传输网格结点的连接关系,这种算法不同于Gabriel Taubin算法,它具有对顶点坐标、属性坐标及三角形连接关系压缩无损等许多优点。     

结合二叉树和Graham扫描技术的高效Delaunay三角网构建算法*

为了提高不规则三角网的构建速度,提出了一种高效构建Delaunay三角网算法。首先对平面上的离散点集按一定的阈值进行分块,建立子块索引二叉树,然后利用Graham扫描技术对各子块构建Delaunay三角网,最后自底向上合并具有相同父节点的子块。通过具体实验与其他构网算法比较,该算法在构网速度上具有明显的优越性。     

改进的平面域Delaunay三角网生成算法

讨论了离散点建立Delaunay三角网算法的研究现状,并采用网格划分提高构网速度。由于三角形定位的速度是影响构网速度的关键因素,改进了基于点线关系方向定位算法,充分利用点与三角形的拓扑关系,减少点线关系的方向定位算法中计算重心的次数,从而提高了三角形定位的效率和构网速度。通过测试证明了算法的高效型和稳定性。     

三维DTM构建算法改进与实现

逐点插入法是一种依次插入数据点来进行三角剖分的方法,此方法可以用于实现平面或三维域上离散数据点的Delaunay三角网的构建.在原算法的基础上提出改进.通过对离散数据点集在XOY二维平面上的排序使之有序化以及对三角形进行分类的方法提高生成delaunay三角网构网速度,并运用到三维DTM的构建实现中.通过程序运行测试显示,随着点数的增加速度增长的幅度也增加,这对于需要大点数DTM的构建有着很好的应用价值.     

Delaunay三角网高效构建及地形仿真应用

针对基于离散点的Delaunay三角网构建过程中待插入点的定位耗时问题,提出Delaunay三角网高效构建算法,并将其用于三维地形仿真应用中。对大量数据点进行分块排序预处理后,运用空间自相关理论使下一个待插入点总是紧邻新近插入点,融合最短路径定位算法和三角形面积法,结合三角形重心与点、有向线段的关系遍历三角形,减少遍历时间。在对三角网进行LOP局部优化时,采用Delaunay四叉树保存待调整的所有边的节点信息,提高遍历效率。实验结果证明,该算法构建的三维地表真实感较强,并且具有较低的时间复杂度。     

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

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

基于快速Delaunay三角化的散乱点曲面重建算法

针对现有三维重建算法速度较慢的问题,提出了一种基于快速Delaunay三角化的散乱数据点的三维重建算法。首先,提出一种新的平面Delaunay三角化插入点目标三角形定位算法,利用插入点的方向搜索线与三角形是否相交以及交点个数加速目标三角形定位,不用额外判断点是否在三角形内;其次,自动检测曲面漏洞,利用凸壳的边界拼接方法进行漏洞弥补。实验结果表明,本算法不仅能较好地重建出三维模型,而且有较高的效率。     

以优先点为中心的Delaunay三角网生长算法

目的 Delaunay三角网具备的优良性质使其得到广泛的应用,构建Delaunay三角网是计算几何的基础问题之一,为了高效、准确地构建大规模点集的Delaunay三角网,提出一种基于优先点的改进三角网生长算法.方法 算法以逆时针次序的一条凸包边为初始基边,使用基边对角最大化并按照逆时针次序选定第3点构建一个Delaunay三角形,通过待扩展边列表中的数据判断新生成的两条边是否需要扩展,采用先进先出的方式从待扩展边列表中取边作为基边,以优先点为中心构建局部Delaunay三角网使优先点尽快成为封闭点,再从点集中删除此封闭点.结果 对于同一测试点集,改进算法运行时间与经典算法运行时间的比率不超过1/3,且此比率随点集规模增长逐步下降.相比经典算法,改进算法在时间效率上有较大提升.结论 本文改进算法对点集规模具有较好的自适应性与较高的构网效率,可用于大规模场景下Delaunay三角网的构建.     

基于均匀网格的Delaunay三角网算法在随机聚合网屏中的应用

Delaunay三角网一直是一个重要而有意义的研究课题，并具有极其广泛的用途。经过20多年来的研究，它的生成算法已趋于成熟。为了满足印刷、印染系统中随机聚合网屏生成的实时性需要，将一种将的算法引处到FM网屏技术中，并首先简要介绍了Delaunay三角网的牧场考及生成算法的分类；然后主要介绍了一种基于均匀网格的Delaunay三角网生成算法在随机聚合网屏中的应用；最后给出了算法的正确性证明。经测试，该算法的运算速度相当快，具有接近于线性的时间复杂性，能够满足排版印刷、印染系统中随机聚合网屏生成的需要。     

改进的自连接Delaunay三角网生成算法

本文提出了一个改进的自连接Ｄｅｌａｕｎａｙ三角网生成算法。在原算法的基础上引进了封闭点的概念,在三角网的生成过程中动态地剔除封闭点,从而大大加快了生成新三角形时对点的查找过程。其次,通过对边扩展过程的研究,发现对除了第一个三角形以外的其他三角形实际上只有两条可扩展的边,新算法对这一点也进行了改进。最后,给出了实验的结果数据。     

基于Delaunay三角网的模型拼合算法研究

模型拼合在地理建模、铁(公)路路线三维设计等领域应用十分广泛，研究如何快速高效地获得拼合模型的算法很有必要。基于Delaunay三角网模型的拼合算法，提出了一种快速获取模型拼合交线的方法和快速搜索交线范围内三角形的算法，采取拼合交线入网及初始D-三角网的裁剪2个关键步骤来实现D-三角网模型拼合。对模型拼合的整个过程进行了详细的阐述，采用VC^ 6．O语言实现了算法，并利用实验数据对算法进行测试，验证了算法的正确性与可行性。     

Delaunay三角网构建方法比较研究

Delaunay三角网构建是3维场景可视化领域的一个热点也是难点问题。归纳总结了现有Delaunay三角网构建研究中的3类方法——逐点插入法、三角网生长法和分治法,以及在各自原理框架下的不同实现算法;比较分析了3种不同方法的优缺点和各自代表性算法的时间复杂度,并详细讨论了Delaunay三角网构建方法在大规模场景渲染和地形可视化领域中未来3个研究方向：混合算法研究、算法支撑技术研究和分布式并行算法研究。     

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

提出一种基于凹凸顶点判定的简单多边形Ｄｅｌａｕｎａｙ三角剖分算法。该算法首先求出简单多边形的凹凸顶点，然后，逐次割去一个权值最大的三角形构造三角形网络，修改多边形顶点链表，并重新计算受影响的顶点的凹凸性。重复这个过程，直到边界顶点链表空为止。     

An almost distribution-independent incremental Delaunay triangulation algorithm

This paper presents a new incremental insertion algorithm for constructing a Delaunay triangulation. Firstly, the nearest point is found in order to speed up the location of a triangle containing a currently inserted point. A hash table and 1–3 deterministic skip lists, combined with a walking strategy, are used for this task. The obtained algorithm is compared with the most popular Delaunay triangulation algorithms. The algorithm has the following attractive features: it is fast and practically independent of the distribution of input points, it is not memory demanding, and it is numerically stable and easy to implement.     

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.