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

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

一种基于插入法的Delaunay三角网生成算法

文章讨论了建立离散点Delaunay三角剖分算法的研究现状,针对＂逐点插入法＂采用网格分块的方法对构网离散点集和已生成的三角网建立索引,提高了点在三角网中的定位效率和三角网的生成效率。     

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

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

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

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

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

Delaunay三角网在GIS／VR中具有很广泛的用途，而分而治之算法和逐点插入法是目前普遍用于生成Delaunay三角网的两种算法。本在研究了基于这两种算法的合成算法后，对其进行了修改和优化，形成了高效合成算法。高效合成算法中提出了通过确定点线关系来解决点的定位问题，优化了其LOP的算法，提高了算法的稳定性，使其执行效率得到很明显地提高，本算法的设计思想还可推广到三维空间。     

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

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

生成Delaunay三角网的改进算法

算法以原“改进的自连接Delaunay三角网生成算法”为基础。其主要方法仍是三角网生长法,但同时采用了逐点插入法中的凸壳。在原封闭点的基础上提出了封闭的边界点的概念,并增加了对边界点和边界边的识别和处理,从而进一步提高了构网效率。另外,采用的用边的法向量对边的某侧的点进行判断的方法也简单实用。     

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

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

基于Bowyer-Watson三角网生成算法的研究

不规则三角网（Triangulated Irregular Network,TIN）在表示地形的形态方面具有较好的表现,其生成算法一直备受关注。讨论了三角网的数据结构的设计,采用逐点插入算法中的Bowyer-Watson算法思想为研究重点,设计并实现了该算法,对算法实验过程中可能出现的交叉现象进行分析,给出算法的改进。该改进算法已用于地形的可视化建模中,获得了较好的效果,对于三角剖分的相关研究具有一定的价值。     

An efficient sweep-line Delaunay triangulation algorithm

This paper introduces a new algorithm for constructing a 2D Delaunay triangulation. It is based on a sweep-line paradigm, which is combined with a local optimization criterion—a characteristic of incremental insertion algorithms. The sweep-line status is represented by a so-called advancing front, which is implemented as a hash-table. Heuristics have been introduced to prevent the construction of tiny triangles, which would probably be legalized. This algorithm has been compared with other popular Delaunay algorithms and it is the fastest algorithm among them. In addition, this algorithm does not use a lot of memory for supporting data structure, it is easy to understand and simple to implement.     

Delaunay三角剖分在离群点检测中的应用

在传统的基于[K]近邻的算法中,需要为算法设置邻居参数[k]的值,只有具备相关的先验知识才能确定合适的参数值。为了减少参数对于离群点检测的影响,提出了一种无需参数的基于Delaunay三角剖分的离群点检测算法。Delaunay三角剖分是数值分析以及图形学中的重要基础理论,它的构建无需任何参数,在三角剖分图中的每个数据对象与它空间上相邻的点都存在边直接相连,因此可以形成一种有效的邻居关系。算法首先通过Delaunay三角剖分形成每个点的空间邻居集合,然后根据每个点与它们空间邻居之间的分布特征,计算它们的离群程度,根据离群程度的大小判断该点是否为离群点。通过实验与相关的算法比较,算法具有更好的效果。     

An intersection algorithm based on Delaunay triangulation

A robust method for finding points of intersection of line segments in a 2-D plane is presented. The plane is subdivided by Delaunay triangulation to localize areas where points of intersection exist and to guarantee the topological consistency of the resulting arrangement. The subdivision is refined by inserting midpoints recursively until the areas containing points of intersection are sufficiently localized. The method is robust in the sense that it does not miss points of intersection that are easily detectable when costly line-pair checking is performed. The algorithm is adaptive in the sense that most of the computational cost is incurred for the areas where finding points of intersection is difficult     

基于Delaunay三角剖分的半径补偿新算法

合理的半径补偿算法能有效提高逆向工程的最终精度.在分析了现有半径补偿算法及其相应优缺点的基础上,针对三角网格法,通过Delaunay三角剖分思想的引入,提出了一种基于Delaunay三角剖分的半径补偿新算法,并对其中三角剖分的优化准则、边界点的处理等关键技术进行了详细的阐述,最后以增压器叶轮为例,实现了叶轮叶面测量数据的半径补偿.     

一种改进的基于Delaunay三角网的聚类算法

Mundur等提出了一种基于Delaunay三角网的聚类算法,并将其应用于视频帧的多维特征数据的聚类以生成视频摘要,取得了较好的效果。但是,该算法计算量太大,导致效率不高。为提高该算法的效率,以适合于对大数据集的处理,提出了一种改进的基于Delaunay三角网的聚类算法。通过在典型数据集上的实验,提出了一种新的确定全局聚类阈值的方法,使得计算量大为减少。实验结果表明,该算法无需用户提供聚类参数,也能得到良好的聚类结果,因此能够实现聚类过程自动化;并且计算速度更快,效率更高,适合于大数据集的处理。     

基于Delaunay三角剖分的印鉴识别算法

针对印鉴图像姿势纠正及印鉴匹配处理,引入计算几何中平面点集的三角剖分方法--Delaunay三角剖分方法和基于此的多边形三角剖分方法,并提出一种基于DT网格的印鉴识别方法.通过对两种细节点(基于线条的细节点和基于多边形的细节点)的拓扑结构进行DT三角划分,把空间上位置相近的细节点按照一定的规则相连,得到DT三角形网格,并基于该网格寻找若干参考点对,根据获得的参考点对将两幅印鉴图像进行姿势调整,使用获得的参考点对实现基于点模式的印鉴匹配.经分析该方法可以获得较多的参考点,确保了印鉴旋转、印鉴平移参数计算结果的准确性,有效地提高了最终的识别效果.     

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

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

基于Delaunay三角剖分密度度量的聚类算法

针对K-means聚类算法无法正确识别非凸形状簇的缺陷,提出一种基于Delaunay三角剖分密度度量的聚类方法,利用Delaunay三角剖分图的最近性、邻接性等优良特性来反映数据自身特点并进行密度度量,同时以混沌优化方法实现聚类目标函数的全局优化,达到全局最小解。实验结果证明,基于Delaunay三角剖分密度度量方式的聚类算法能发现任意非凸形状簇。     

Delaunay triangulation using a uniform grid

An algorithm for triangulating 2-D data points that is based on a uniform grid structure and a triangulation strategy that builds triangles in a circular fashion is discussed. The triangulation strategy lets the algorithm eliminate points from the internal data structure and decreases the time used to find points to form triangles, given an edge. The algorithm has a tested linear time complexity that significantly improves on that of other methods. As a by-product, the algorithm produces the convex hull of the data set at no extra cost. Two ways to compute the convex hull using the algorithm are presented. The first is based on the edge list and the second is based on the grid structure     

Adjacency for grid generation and grid adaptation in Delaunay triangulation

One of the characteristics of Delaunay method for mesh generation is its local remeshing ability. The main part of the process is to identify remeshing block out of the whole domain and to execute remeshing on the block. Adjacency, adjacent element array, is introduced with an accompanying algorithm to make the process so simple and versatile that it will be used in generating the initial mesh, in applying mesh adaptation, in mesh revision for moving boundary problems, and in transforming 3-node base mesh to 6-node mesh. These features are demonstrated in the example problems of heat conduction with point sink, crack propagation, and simple upsetting of a circular cylinder. Proposition is made to take utility array ‘adjacency’ as basic element data.