对构建Delaunay三角网中凸壳算法的研究与改进

在介绍Delaunay不规则三角网基本概念和TIN数据结构的基础上,主要对平面离散点构建凸壳的格雷厄姆算法进行了研究和改进,提出了一种“斜率扫描线法”,并进行了编程实现。实验表明改进后的算法实现简单,容易理解,对于D-TIN模型的生成行之有效。     

基于凸壳技术的Delaunay三角网生成算法

该文提出了一种针对散乱点集的快速构建Delaunay的算法。该算法首先对散乱点按有向角进行排序,以排序后的点顺序为基础,利用凸壳特性快速将散乱点联结成三角网,最后利用拓扑结构快速将其优化为Delaunay三角网。在联网过程中,充分利用有序点子集的凸壳特性,避免了所有的交点测试,从而保证了对散乱点集生成Delaunay三角网的效率。     

四叉树高效Delaunay三角网生成算法

实现了一种以地形为应用背景的大规模离散点快速生成TIN的算法,该算法首先对大规模离散点按一定的阈值进行四叉树分割,然后对四叉树的每个叶子块分别以凸壳技术构三角网,而后再自底向上合并具有相同父亲节点的块,最后进行全局优化,生成Delaunay三角网.经实际地形数据验证结果表明：同样的算法,采用四叉树分块比采用平均分块策略有着更高的执行效率.     

基于最优凸壳技术的Delaunay三角剖分算法

提出了一种基于最优凸壳技术的Delaunay三角剖分算法。该算法对离散点进行扫描线方式排序,利用最优凸壳技术进行凸壳的生成和三角网联结,最后利用有向边的拓扑结构进行三角网优化。该算法不但避免了所有的交点测试,而且使得新加入点与凸壳边的平均比较次数不大于4,从而实现了高效的三角剖分。     

高阶Delaunay三角网及生成算法研究

Delaunay三角剖分是构建数字地形模型的有效方法,但是该方法会引起人工大坝和局部极值问题,使得地形模型不能很好地反映原始地形的真实面貌。在Delaunay三角网的基础上提出了一种高阶Delaunay三角网,并给出了高阶Delaunay三角网生成算法。实验结果表明,高阶Delaunay三角网能够有效地减少地形中局部极小的数量,因此,采用高阶Delaunay三角网建立的地形模型更接近于实际地形。     

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

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

构建Delaunay三角网的改进算法

在编程实现利用凸壳三角剖分法构建Delaunay三角网时，原算法由于没有对一些特殊情况加以考虑和处理，可能会使算法的后继步骤无法进行。在分析介绍潜在问题出现原因的基础上，对特殊情况加以考虑和处理，并对生成凸壳和初始三角网的方法做了一些改进，使程序在编写和运行上都具有更高的效率。     

基于二维凸壳的平面点集Delaunay三角网算法

提出了一种基于并行二维凸壳算法的平面点集的Delaunay三角网生成算法。该算法基于颜坚等在文献[20]中提出的并行二维凸壳算法,在构建凸壳时记录被替换的边和被删除的点,形成一个初始三角网;再在初始三角网的各个三角形内部,采用逐点插入法构建局部的Delaunay三角网;最后,对各个局部Delaunay三角网的边界边进行局部优化,得到原点集的Delaunay三角网。文中给出了算法的正确性说明,实验结果也表明该算法稳定高效。     

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

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

一种改进的Delaunay三角网生成算法

Delaunay三角网在GIS/VR中用途广泛,分割-归并法和逐点插入法是目前普遍用于生成Delaunay三角网的两种算法.在研究基于这两种算法的合成算法后,对其进行了两点改进.一是简化凸壳的生成;二是三角形快速定位,通过确定向量之间的关系来解决点的定位问题,避免了复杂运算.实验结果证明,改进后的算法不仅继承原算法兼顾空间和时间的性能,且执行效率有明显提高.     

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.     

基于不规则三角网构建的网格生长算法

提出一种基于离散点Delaunay三角网快速构建的网格生长算法,采用分治算法将离散点表达为唯一网格,利用稀疏矩阵完成网格数据的压缩存储,通过标识码实现有值单元格与离散点之间的高效检索,从而提高网格构建的效率。依据有值单元格的密度获取预设正方形搜索空间,并在三角网扩展时根据需要动态建立正方形搜索空间,从而保证网格生长的准确性。实验结果表明,该算法的时间复杂度为O(nlogn),对于少量或海量离散点均具有较好的适应性。     

基于三角形不规则网模型的快速体素化方法

为了改善在大数据量时体素化效率不高的缺点,针对三角形不规则网（TIN）模型的三角网特性,提出了一种快速简单的体素化算法。首先通过细划三角面片,将面体素化转换为简单的点体素化生成体表面模型,然后利用深度缓存原理快速寻找初始种子体素进行体内填充。实验结果表明,对于精细复杂的大规模TIN模型,算法能确实有效地生成逼近原模型的26-连通的体素模型,且具有高效的时间效率。     

两维区域三角剖分的新算法

提出一种两维区域三角剖分的新算法,算法首先递归应用求两维点集凸包的Graham扫描法,在原始区域的点集中求出一系列的凸包,同时原始两维区域也被这些凸包划分为多个独立的子区域,然后对相邻两个凸包之间的子区域进行三角剖分,从而实现对整个原始两维区域的三角剖分.和以往得算法相比,提出的算法的时间效率大大提高了,并且在作者参与的军队2110建设项目应用中也体现了良好的效果.     

一种基于四叉树的TIN的LOD算法

通过在不规则采样点集上构建一个四叉树结构，并联合基于四叉树的LOD算法和基于TIN的三角网简化算法，提出并实现了一种TIN的LOD算法。意在把适用于格网数据的高效方法应用于不规则采样点集，得到地形的一个高效的多分辨率表达。     

基于分块优化的不规则三角网的快速构成方法

采用基于分块的方式,提高了TIN的运行效率,并提出采用四边形对角线最短原则、增加内插点或减小块连接中距离阀值等优化处理方法,很好地改善了TIN的构网效果。实验结果表明,该算法建立的三角网无交叉和重复,并具有Delaunay三角网的特性,同时兼顾了空间和时间性能,具有较高的执行效率。