A new insertion sequence for incremental Delaunay triangulation

Incremental algorithm is one of the most popular procedures for constructing Delaunay triangulations （DTs）. However, the point insertion sequence has a great impact on the amount of work needed for the construction of DTs. It affects the time for both point location and structure update, and hence the overall computational time of the triangulation algorithm. In this paper, a simple deterministic insertion sequence is proposed based on the breadth-first-search on a Kd-tree with some minor modifications for better performance. Using parent nodes as search-hints, the proposed insertion sequence proves to be faster and more stable than the Hilbert curve order and biased randomized insertion order （BRIO）, especially for non-uniform point distributions over a wide range of benchmark examples.

一种生成Delaunay三角网的合成算法

经过２０ 多年的研究，自动生成Ｄｅｌａｕｎａｙ 三角网的算法已趋于成熟。它们基本上可分为分治算法、逐点插入法、三角网生长法等３ 类。其中前两类较第３ 类在应用上更加广泛。但即使这两类算法也分别存在着时间和空间效率上的缺陷，使它们的应用受到了一定的限制。提出了一个融以上两类算法优点于一体，兼顾空间与时间性能的合成算法。经测试，它的运算效率大大高于逐点插入法，在大多数情况下，也高于分治算法，在分割阈值约为总数据量的十分之一时，效率最高。

Delaunay三角剖分算法改进与对比分析

针对Delaunay算法的计算速度问题,从数据结构和算法两个方面加以改进。对Delaunay三角剖分的代数拓扑分析,设计一种顺序存贮的Hash数据结构,实现临时单纯形对象的快速和顺序存取、查询、插入和删除等操作;以单纯形边对象的活性分析为核心,以Hash数据结构进行操作,消去生长法的递归过程;此外,提出基于微切平面的生长法,将基于空间四面体的空球搜索降维至局部二维的空圆搜索。对汽车挡泥板和兔子模型进行三角剖分实验,实验结果表明,消去递归的生长法和基于微切平面的生长法和传统的生长法三角剖分效果相同,但是计算速度比传统方法效率更高。

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

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

大量约束边条件下Delaunay三角网的快速生成

讨论了建立约束Delaunay三角网算法的研究现状,采用“逐点插入法”和“多对角线交换算法”构成“两步法”,在此基础上,从建立高精度三角网模型的需求出发,研究以大数据量等高线为约束边进行Delaunay三角剖分的改进算法。针对“逐点插入法”,采用网格分块的方法对构网点集和已生成的三角网建立索引,提高了点的查询速度和点在三角网中的定位速度,提高了三角网的生成效率;针对“多对角线交换算法”,增加了一些特殊情况的处理,提高了算法的健壮性和交换速度。

基于逐点插入法的Delaunay三角网快速生成算法

为满足由海量离散点数据快速生成Delaunay三角网,提出了一种基于传统的逐点插入法生成Delaunay三角网的算法,对传统逐点插入算法的点定位以及LOP算法进行优化。首先对离散点进行分块排序,按行依次插入各点,采用方向搜索技术,以最新生成的三角形作为初始三角形,可大幅缩短点定位过程的搜索路径,快速定位到插入点所在的三角形。通过确定插入点的影响范围,只更新影响范围内的三角形,避免重复计算。运用合理的数据结构,简化计算过程,可进一步提高效率。实验证明,改进后的算法可大幅提高三角网的生成速度和质量。

面向二维Delaunay构网的点定位算法优化

逐点插入法是构建Delaunay三角网的主要方法之一,而在众多三角形中能否快速找到插入点所在三角形是影响整个逐点插入法构网速度的重要因素。在分析现有点定位算法的基础上,结合三角形重心的几何性质,提出了一种新的点定位算法,简化了待插点位于三角形两条边外侧时的寻找下一三角形的计算步骤,避免了求三角形重心坐标和相交边的过程,并将新算法应用到点云数据地形建模中。实验结果表明,上述算法较目前其它点定位算法能够有效的缩短搜索路径,避免了目前已有算法存在的搜索路径长、搜索路径求解计算量大等问题,较其它算法能提高Delaunay三角网构网过程中点定位的效率,并减少点云数据地形建模时间。

基于虚拟网格的高效Delaunay三角网生成算法研究

针对传统逐点插入算法存在时间效率比较低的问题,设计了高效的存储结构,通过引入虚拟网格技术,在三角形定位和点的插入顺序方面作了改进和优化,提出了一种改进的D-三角网生成算法,提高了点插入过程中查找相应三角形的速度,有效的减少了重构三角形的数量,大大改进了逐点插入算法的时间效率。实验结果表明,改进后的算法具有较低的时间复杂度,能快速地生成三角网。

Delaunay三角网建立的改进算法

本文深入研究了Delaunay三角网建立算法中的逐点插入法，详细介绍了算法的实现步骤，分析了其中影响算法效率的关键环节，并采用数据点集分块管理、三角形快速定位、改变点插入顺序等方法进行了算法优化，对三角形快速定位方法进行了改进。测试实验的结果说明，算法改进后Delaunay三角网建立的效率提高了4～6倍。

一种改进的Delaunay三角化算法研究

Delaunay三角化在诸多应用领域具有极其广泛用途,也一直是计算机图形图像学和科学计算可视化技术的重要研究内容。针对二维约束Delaunay三角化问题,提出一种快速生成算法。该算法首先建立环形矩形,分环分治平面散乱点;然后依据Delaunay三角形的性质,从外环到内环分治逐步插入新点,一环插入完毕后,整理有效Delaunay三角形;依次循环快速生成二维约束Delaunay三角网格。本算法计算过程简单,计算效率高,程序编写十分容易无需复杂的递归过程,技巧性地解决了二维约束Delaunay三角化问题。实例证明,该算法具有较好的应用效果。

基于分治算法与逐点插入法的Delaunay三角网建立算法的改进

Delaunay三角化在诸多应用领域都具有极其广泛的用途,也一直是GIS领域的重要研究内容。本文针对在Delaunay三角网建立中比较常用的分治算法即逐点插入法的缺点提出一些改进方案,在对逐点插入法改进的前提下提出将分治算法与逐点插入法相结合的综合算法。该综合算法既具有分治算法的高效率又具有逐点插入法的内存消耗小的优点,同时又较好地解决了分治算法与逐点插入法各自的缺点。

基于符号体积值的Delaunay逐点插入法

传统Delaunay逐点插入法需在全局范围内进行点定位操作,或涉及到面的法向量计算,效率较低。提出一种基于符号体积值的Delaunay逐点插入法。设计简要的数据结构,利用四面体带符号体积值的符号,判断新插入点所在方位,逐步搜索将该新插入点包含在其内部的中心四面体,完成局部范围的点定位;进一步利用体积值符号进行Delaunay空洞可视面测试;对多点共面或共球的退化情况,将点坐标加以细微扰动,提高算法健壮性。实验结果表明,基于符号体积值的Delaunay逐点插入法的点定位操作效率较高,计算量相对减少。

面向并行的动态增量式Delaunay三角剖分算法

三角剖分是计算机图形学中的重要话题。并行三角剖分算法的发展对传统三角剖分算法提出了新需求,其中之一即是给定一个点数不断增大的点集,实现对该点集三角剖分的快速增量更新。虽然现今已有一些增量三角剖分算法,但都无法支持新增点落入原有三角剖分之外的情况。为解决此问题,提出了三角剖分的外扩技术,基于插入法设计了增量三角剖分算法TID。该算法能够支持任意次、任意数量、任意位置点的增量添加。TID算法能够对任意分布的点集均给出唯一三角剖分结果。对TID算法的性能评估表明,TID算法比现有算法具有更高的计算效率,且增量功能引入的额外开销较小。此外,该算法已成功作为局地三角剖分算法用于并行三角剖分算法中。

一种快速二维Delaunay三角网点定位算法

在构建二维Delaunay三角网的逐点插入法中,定位待插点所在三角形的快慢是影响整个算法构网速度的关键因素。针对目前已有算法存在的搜索路径长、搜索路径求解计算量大等问题,结合三角形重心的几何性质,对点定位算法进行改进,避免求三角形重心和相交边的过程。实验结果表明,文中算法较目前其他点定位算法能够有效地缩短搜索路径,减少点定位的计算时间,提高Delaunay三角网构网过程中点定位的效率。

Delaunay三角形网络逐点插入法的优化算法

Delaunay三角形网络逐点插入法虽简单易行,但效率低下。针对其效率低下原因,提出一种改进的Delaunay三角形网络逐点插入生成算法。将已知插入点X坐标大小排序,当X坐标相等时,以Y坐标大小顺序排序构建新的插入点顺序,并得到插入点坐标集合中的最大值和最小值。适当放大插入点坐标中最大值、缩小坐标最小值后,得到X、Y坐标新的两个最大值和两个最小值,用4个值构建4个临时新插入点,可以构建出Delaunay三角形网络矩形的凸壳。按照新的插入点顺序逐点插入构建三角形网络,只判断插入点与以X坐标最大的两个边界矩形顶点为顶点的三角形位置关系。生成三角形网络后删除与4个临时顶点相关的三角形,就是所需要的三角形网络。通过证明每个插入点必定落在X坐标最大的两个边界矩形顶点为顶点构成的三角形上,可以减少插入点与已生成三角形位置关系的判断次数,较大程度提高逐点插入法的效率。将新算法与常规算法计算复杂度比较,结果表明,改进的算法能提高逐点插入效率,运算量稳定,达到逐点插入法的最好水平。

平面域Delaunay三角网点定位算法研究综述

不规则三角网常用于地形的可视化,其生成算法一直是国内研究热点。Delaunay三角剖分算法是构建不规则三角网的主要算法。讨论了平面域离散点生成Delaunay三角网算法的研究现状,其中逐点插入法中影响构网效率的关键因素是任意插入点定位的速度。总结了目前国内主流的点定位算法,对国内该领域现有文献研究存在的主要问题作了详细分析,并展望了未来可能的研究走向,以期为国内Delaunay三角网生成算法研究提供理论与方法上的指导意见。

Delaunay三角网的构建理论研究

在GIS应用领域中,Delaunay三角网通常被用于生成不规则三角网(TIN)模型,并用于描述地表形态。详细叙述了的现有的Delaunay三角网三种生成算法——逐点插入法、逐步生长法和分割-归并算法,并进行了比较。最后分析了Delaunay三角网构建中存在的问题及未来研究方向。

平面域中的Delaunay三角算法

对目前广泛使用的Delaunay三角网格生成方法的基本原理进行阐述,对目前流行的几类DT(Delaunay Triangulation)算法,逐点插入算法、分治算法、三角网生长算法的原理进行了分析,对它们的特点进行了介绍。

基于Delaunay三角剖分的多尺度POI提取技术研究与实现

简要概括了电子地图图面表达中多尺度POI分布的重要性,分析了Delaunay三角剖分算法和POI分级原则,提出了基于Delaunay三角剖分增量算法,添加三角网面积、边长及POI权重作为约束条件的多尺度POI提取技术,并在多城市电子地图制作中实践,验证了该方法的可行性。

一种改进的D-TEN生成算法及其应用

详细介绍了Delaunay TEN的生成算法——逐点插入法。利用空间八叉树索引及方向查找技术优化影响算法时间效率的关键步骤——插入点定位;结合壳内插入及壳外插入方法改进初始网格生成及加点过程。实验分析表明,点定位算法不仅能够快速对点进行定位,并且其效率与离散点规模无关;壳外插入法将插入点的位置扩展到网格外部,使初始网格的生成更加灵活。最后,结合空间插值技术,将D-TEN应用于矿床真3D建模技术中。