计算Delaunay三角剖分的新算法

提出一种计算K维欧氏空间EK 中任意数据点集的凸包的Delaunay三角剖分的新算法 .通过引入辅助的无穷三角形和在全空间 EK 的Delaunay三角剖分 ,确保最终结果是数据点集的凸包的完整Delaunay三角剖分 ,而且使算法具有在线性质 ,适用于动态的数据点集 .     

Delaunay三角剖分的几种算法综述

多边形的三角剖分是计算几何中的基本问题,本文对三角剖分算法做简要的综述,并对约束三角剖分动态算法进行了研究,为设计更好的三角剖分算法提供了一定的依据。     

基于Delaunay三角剖分的指纹识别

针对指纹识别过程中指纹匹配算法的准确性以及识别效果等问题, 结合计算几何中Delaunay三角剖分方法的特点, 将其引入指纹匹配处理, 提出一种基于三角网格的指纹匹配方法.该方法通过对细节点的拓扑结构进行三角划分, 得到三角形网格.最后利用三角形的几何不变性按照匹配与配型两个步骤进行指纹识别.经实验验证该方法是一种行之有效的指纹匹配方法, 有效地提高了最终的识别效果.     

带断层约束的Delaunay三角剖分混合算法

三角剖分是构建高精度数字高程模型(DEM)的基础,在各个领域都有广泛的应用。特别是在约束数据域下的Delaunay三角剖分更具有重大的研究价值,前人已经做了大量的工作,并提出了一系列经典的剖分算法。在对传统算法进行研究与分析后,总结了传统算法的优缺点,结合了逐点插入法、三角网生长法以及分治法的思想,提出了一种高效的、带断层约束的Delaunay三角剖分混合算法。该算法在建立无约束的DT(Delaunay Triangulation,DT)网格的基础上通过嵌入加密后的断层数据来实现带断层约束的CDT(Constrained Delaunay Triangulation,CDT)网格。通过实例比较,说明了混合算法在构网质量和时间效率上都优于传统算法。     

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

描述了一种平面散乱点集的Delaunay三角剖分算法.首先对散乱点集预处理,保证每次插入的点落在已处理点集形成的临时边界环外;然后逐点插入预处理后的点,使临时边界环不断向外围扩展,直至点集处理完毕,形成散乱点集的三角网格;最后运用Delaunay优化准则优化.该算法由于充分利用了Visual C 语言中MFC类的数据资源,使得编程容易实现.最后举例验证了该算法的优越性.     

Voromoi图和Delaunay三角剖分的计算及应用

论述了Ｖｏｒｏｎｏｉ图及其几何对偶Ｄｅｌａｕｎａｙ三角剖分的计算方法，重点探讨了Ｄｅｌａｕｎａｙ三角剖分的优化性质及其有限元网格自动生成过程中的应用，在此基础上提出了一种自动生成三角形有限元网格的新算法。     

地质模型网格剖分中Delaunay三角剖分算法的实现及优化

地震勘探方法的核心就是对地震波数据的采集、处理和解释,尽可能真实地反映地下的地质构造．整个勘探过程中,数据处理的难度最大,难点在于数据量大、运算量大．网格剖分由于其本身算法的繁琐和易错性成为整个数值模拟过程中的瓶径．选择并实现可根据少量的输入数据生成同时满足通用性与健壮性要求的网格数据的剖分算法具有重要实用意义．本文提出了地质模型数据不规则网格剖分算法的思路,并实现了经过优化的Delaunay三角形网格剖分算法。     

长江口北槽水域的Delaunay三角剖分

为了进行长江口水动力过程等的有限元数据模拟，研究了任意平面区域的Delaunay三角剖分和基于背景网格等值线点集的新的自动生成方法：局部三角形内得到等值线、进行自动加点；改进任意平面区域的Delauay三角剖分法，与行波法结合，从区域边界向域内逐步三角化，前者简化了自动加点算法，保证新生成点均位于域内、疏密连续变化和最终网格具有良好形态，后者则统一解决了多连通、4点共圆和非凸域的自动三角剖分问题，逐步减少人为给定边界的影响，从而减少了算法的运行时间，据此开发的软件包可动态监控点，网格的生成过程，并经大量的测试、验证，应用于长江口北槽水域的自动加点和三角剖分，取得了较好的效果。     

基于Delaunay三角剖分的最大Lyapunov指数算法研究

针对时间序列最大Lyapunov指数计算速度慢的缺陷,研究了小数据量算法,提出了基于Delaunay三角剖分的最大Lyapunov指数的计算方法.利用Delaunay三角剖分方法解决了邻点搜索速度慢的问题.详细地介绍了算法步骤,分析了算法的运算量,并应用于几种离散映射.仿真试验表明:该方法较稳定、可靠,同时对相空间重构中的嵌入维数不敏感.     

Delaunay三角剖分的递进构造算法

提出一个计算有限点集Ｓ的Ｄｅｌａｕｎａｙ三角剖分的递进算法，本算法通过对点集Ｓ进行预处理，使得每次插入的点落在已处理点集的凸壳外，从而减少了查找第一个删除顶点的时间，并且能够在最优时间内维持凸壳，克服了Ｂｏｗｙｅｒ算法的缺陷。     

一种支持三维Delaunay三角剖分与Voronoi图生成的数据结构

目前,很多三维Voronoi图生成算法都是先构造Delaunay三角剖分,然后根据剖分后的数据结构来提取出Voronoi信息。在这个过程中,一种简单易处理的数据结构可以提高算法的效率,而在提取Voronoi信息时需要这种数据结构提供足够多的拓扑信息,以便快速简便地提取Voronoi信息。因此一种易于处理而又保有足够多拓扑信息的数据结构显得尤为重要。描述了一种数据结构,使Delaunay三角剖分算法的实现更加直观、简单,而且足够的拓扑信息简化了Voronoi信息的提取过程。     

基于ArcGIS环境下多类型数据的三角网和Voronoi图的生成

基于渐次插入算法,在ArcGIS环境下,提取居民地中心点和道路中心线上的点作为离散点,实现了对这些离散点的Delaunay三角网的构建和数据的有效组织,利用ArcGIS提供的接口生成了Voronoi图,实现了多类型数据Delaunay三角网和Voronoi图的生成。     

基于Delaunay三角网与Voronoi图联合提取等高线骨架的地形重建算法研究

提出一种基于Delaunay三角网与Voronoi图联合提取等高线特征骨架的地形重建算法,该算法利用各Delaunay三角形与其对偶Voronoi多边形之间的关系,能一步高效的提取骨架,再通过分析骨架点与主要地貌特征的对应关系,对骨架点进行插值,最后由提取的骨架及原有等高线共同建立新的TIN,完成整个数字高程模型(DEM)的生成。实验结果表明,该算法对修正TIN 中不真实的平坦区域有良好的效果,使得生成的TIN 能更准确地描述地形特征。     

反求工程中基于Delaunay三角形的模型重构研究

散乱点的三角网格剖分是反求工程中首要环节。在分析三角剖分基本方法的基础上提出了动态圆和封闭点的概念,使得搜索新三角形的范围大为降低,从而加快了速度,并在搜索过程中实现Delaunay三角形优化。通过动态更新搜索边控制三角形生成速度。将新三角形和已有三角形的相交判定转化为和搜索边的相交判定,完成非凸边界下的多连通区域的划分。     

欧氏Steiner最小树的Delaunay三角网混合智能求解方法

欧氏Steiner最小树问题是组合优化中一个经典的NP难题,在许多实际问题中有着广泛的应用.由于使用普通智能算法求解较大规模问题时,极易陷入拓扑结构的局部最优,因此,基于Delaunay三角网技术并结合智能算法的有关思想,设计了一种改进的混合型智能求解方法,可大幅度提高算法在寻找更好拓扑结构上的有效性.算法在Matlab环境下编程实现,经大量STEINLIB中的标准数据实例测试和验证,获得了满意的效果,为求解较大规模的欧氏Steiner最小树问题提供了新的有效方法.     

基于凸壳和二次优化的三角网生成算法

文章基于逐点插入算法,引入虚拟网格技术将点和三角形重心规则化,优化了点、边和三角形的拓扑存储结构,实现了点、边和三角形的快速查找。并提出了一种快速的凸壳生成算法和二次优化方案。实验表明此算法获得的三角网生成效率明显提高。     

一个基于桶技术的平面点集Voronoi图增量算法

设计并实现了一个有效的平面Voronoi图增量算法 .该算法以翼边数据结构为基础 ,应用桶技术选择生成子并提高近邻搜索效率 ,可处理平面点集三点共线、四点共圆等退化情形 ,并具有较高的计算精度 .尽管理论上算法的最坏时间复杂性为O(n2 ) ,实验结果表明算法的平均时间复杂性近似为O(n) .     

带岛屿多边形Delaunay三角剖分算法

提出一种适用于任意多边形(含岛屿或不含岛屿)的统一Delaunay三角剖分算法.该算法首先将带岛屿多边形的所有顶点统一构建基于多边形边约束的Delaunay不规则三角网(CD-TIN);基于三角形顶点绕向,提出了多边形域外三角形的判定法则,剔除CD-TIN中的域外三角形,实现了带岛屿多边形的三角剖分.实验表明,该算法在含有大量岛屿的带岛屿多边形三角剖分中具有很高的时间效率和很强的鲁棒性,并成功将其应用到基于剖面的三维矿体建模与可视化系统中,解决了含有夹石或孔洞的矿体剖面多边形三角剖分问题,具有一定的实际应用价值.     

有限元网格Delaunay剖分的拓扑不相容问题研究

Ｄｅｌａｕｎａｙ三角剖分将产生网格拓扑不相容问题。本文详细研究了利用网格元素的自下而上／自上而上的拓扑分类方式,代替传统的,花费时间的,不准确的“内／外”几何检查,初步解决了Ｄｅｌａｕｎａｙ三角剖分中存在的各种不相容问题,节约了计算时间,提高了计算效率。