Two algorithms for constructing a Delaunay triangulation

This paper provides a unified discussion of the Delaunay triangulation. Its geometric properties are reviewed and several applications are discussed. Two algorithms are presented for constructing the triangulation over a planar set ofN points. The first algorithm uses a divide-and-conquer approach. It runs inO(N logN) time, which is asymptotically optimal. The second algorithm is iterative and requiresO(N ²) time in the worst case. However, its average case performance is comparable to that of the first algorithm.This work was supported in part by the National Science Foundation under grant MCS-76-17321 and the Joint Services Electronics Program under contract DAAB-07-72-0259.     

Duality of constrained Voronoi diagrams and Delaunay triangulations

We introduce theconstrained Voronoi diagram of a planar straight-line graph containingn vertices or sites where the line segments of the graph are regarded as obstacles, and show that an extended version of this diagram is the dual of theconstrained Delaunay triangulation. We briefly discussO(n logn) algorithms for constructing the extended constrained Voronoi diagram.This work was partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada.     

简单多边形快速Delaunay三角剖分算法

简单多边形的Delaunay三角剖分,在计算机图形学及地学问题三维建模领域有着广泛的应用。文中在借鉴他人的基础上,提出了一种时间复杂度为O(mn)的基于三角形权值最大的简单多边形Delaunay三角剖分算法。三角剖分结果中的三角形形态达到了最优或次优,并进行了理论上的严格证明,对算法的时间复杂度进行了分析,并给出了一个实例。实验结果表明,该方法对于随机生成的简单多边形域三角化速度快,平均计算时间呈近似线性。     

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

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

三维点集Voronoi图的算法实现

对现有三维点集Voronoi图的生成算法进行深入研究,提出并实现由Delaunay三角剖分构建Voronoi图的算法．首先采用随机增量局部转换计算Delaunay三角剖分,然后再根据对偶特性构建Voronoi图．该算法健壮性很高,适用于处理各种非完全共面三维点集．     

平面点集Delaunay三角剖分的分治算法

为发展图形网格化技术,研究了平面点集的三角剖分算法.根据经典算法中在实际应用中遇到的共性问题,提炼了3个工具算法;为了更好地表示平面区域划分的拓扑信息,引入了双链接边表(DCEL)的数据结构.在此基础上,设计并实现了平面集Delaunay三角剖分分治算法,并对特殊退化情况进行了处理,通过计算表明了该算法时间复杂度为0(N* logN).实验数据结果验证了该算法的正确性、健壮性.     

Point placement algorithms for Delaunay triangulation of polygonal domains

In some applications of triangulation, such as finite-element mesh generation, the aim is to triangulate a given domain, not just a set of points. One approach to meeting this requirement, while maintaining the desirable properties of Delaunay triangulation, has been to enforce the empty circumcircle property of Delaunay triangulation, subject to the additional constraint that the edges of a polygon be covered by edges of the triangulation. In finite-element mesh generation it is usually necessary to include additional points besides the vertices of the domain boundary. This motivates us to ask whether it is possible to trinagulate a domain by introducing additional points in such a manner that the Delaunay triangulation of the points includes the edges of the domain boundary. We present algorithms that given a multiply connected polygonal domain withN vertices, placeK additional points on the boundary inO(N logN + K) time such that the polygon is covered by the edges of the Delaunay triangulation of theN + K points. Furthermore,K is the minimum number of additional points such that a circle, passing through the endpoints of each boundary edge segment, exists that does not contain in its interior any other part of the domain boundary. We also show that by adding only one more point per edge, certain degeneracies that may otherwise arise can be avoided.     

Delaunay三角网动态更新算法的研究进展

通过对Delaunay三角网动态更新算法进行研究,综述了Delaunay三角网中插入和删除点、约束线算法以往研究.详细介绍点定位、LOP优化、对角线交换等关键技术的研究进展,并对比各种方法的优缺点,分析已解决的问题和仍存在的问题.最后对更新算法研究不足之处进行总结,并提出若干可能的研究方向.     

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

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

Delaunay三角网格的一种快速生成法

１．引 言 在计算流体力学中,采用非结构网格有许多优点,如易于生成复杂区域的网格和作网格自适应．最常见的非结构网格是非结构三角网格,而生成非结构三角网格的方法主要有前沿推进法［１－４］和 Ｄｅｌａｕｎａｙ三角剖分法［５－８］两大类．本文仅考虑后者并只讨论生成给定点集的 Ｄｅｌａｕｎａｙ三角网格． 目前流行的生成Ｄｅｌａｕｎａｙ三角网格的算法是Ｂｏｗｙｅｒ－Ｗａｔｓｏｎ算法［６,７］．Ｂｏｗｙｅｒ－Ｗａｓｏｎ算法是以逐点加入的方式进行的,如何提高该算法的运算效率是一个十分重要的问题［８－１３］．用 Ｂｏ…     

Delaunay三角网通用合并算子及分治算法的简化

Delaunay三角网在未来地学数值模拟中将发挥重要作用。分治算法是一种著名的经典构网算法,但其子网合并过程十分复杂,限制了其应用。提出使用通用算子的概念,并用从以往算法中独立出来的算子和3个新算子来简化分治算法的子网合并。扩展三角形算子用于构造每个新三角形并维护三角网的拓扑关系和边界链表。凹边界填充算子对边界链表用递归来自动完成凹边界的智能三角形填充。子网合并算子先用一个新三角形连接两个子三角网,再合并边界链表,调用凹边界填充算子填充子网间的缝隙区域。所有算子都基于有向边的数据结构和用链表管理的三角网外边界,借助链表操作,使算法的构建简洁而又高效。除分治法外,这些算子还被成功用于构建其他算法。由随机点集以及LiDAR点云的测试表明,所有算法的构网均准确无误且分治算法的执行效率较高。     

Optimistic parallel Delaunay triangulation

The paper describes a new parallel algorithm of Delaunay triangulation based on randomized incremental insertion. The algorithm is practical, simple and can be modified also for constrained triangulation or tetrahedralization. It was developed for architectures with a lower degree of parallelism, such as several-processor workstations, and tested on up to 8 processors. Published online: November 20, 2002 This work was supported by the Ministry of Education of The Czech Republic, project MSM 235 200 005     

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

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

一种网格和节点同步生成的二维Delaunay网格划分算法

应用Lawson算法对网格的Delaunay性质进行维护,利用单元尺度场控制生成网格的疏密分布;找到任一不满足尺度场要求的单元,在其可插度最大的边上按一定法则插入新节点,加密网格,实现内节点的生成与网格划分同步进行.该算法避免了搜寻包含三角形的过程,提高了效率.通过多次划分实验表明,该算法的时间复杂度约为O(N1.2).同时,由于在不满足单元尺寸要求的单元边上插入新节点,直接对单元的边长进行控制,使得网格的质量和自适性更加良好.     

A faster divide-and-conquer algorithm for constructing delaunay triangulations

An easily implemented modification to the divide-and-conquer algorithm for computing the Delaunay triangulation ofn sites in the plane is presented. The change reduces its (n logn) expected running time toO(n log logn) for a large class of distributions that includes the uniform distribution in the unit square. Experimental evidence presented demonstrates that the modified algorithm performs very well forn2¹⁶, the range of the experiments. It is conjectured that the average number of edges it creates—a good measure of its efficiency—is no more than twice optimal forn less than seven trillion. The improvement is shown to extend to the computation of the Delaunay triangulation in theL _p metric for 1<p.This research was supported by National Science Foundation Grants DCR-8352081 and DCR-8416190.