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

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

任意多边形的Delaunay三角剖分

任意多边形的三角剖分是计算机图形学领域中的一个基本算法，其用途非常广泛，本文利用著名的Ｄｅｌａｕｎａｙ三角剖分的优化性质，提出了一个简洁、通用的任意多边形Ｄｅｌａｕｎａｙ三角剖分算法，并给出了该算法在有限元网络自动生成过程的应用。     

基于EMST的平面点集Delaunay三角剖分

提出一种基于欧几里德最小支撑树(EMST)的平面点集Delaunay三角剖分算法.该算法使用线性时间的随机算法求出平面点集的EMST,逐次加入一边构成三角网络,按照最小角最大化的三角化准则,通过局部变换得到平面点集的Delaunay三角剖分.采用的随机化算法有效节省了寻找EMST的计算时间,提高了整个算法的效率.     

基于图的任意域内点集的Delaunay三角剖分算法

本文提出了一种基于图的二维任意域内点集的Ｄｅｌａｕｎａｙ三角剖分算法．该算法首先求出任意域内点集的约束最小生成树，然后逐次加入一边构造三角形网格，最后通过局部优化变换，得到二维任意域内点集的Ｄｅｌａｕｎａｙ三角剖分．本文还给出了该算法在有限元网格自动生成过程中的应用.     

一种平面点集凸包与三角网格综合生成的算法

平面点集作为一种觉数学模型,其上常做的运算是求其凸包和三角网格,目前二者的研究是独立进行的,鉴于在很多情形下这两种处理结果均需要,提出了一种综合算法：在对离散点集进行ｄｅｌａｕｎａｙ剖分的过程中,增加对三角形边界的判别、管理功能,记录其中作为点集凸包边界的线段,使得在实现剖分的同时产生出点集的凸包,从而提高了算法效率,且当该算法实现单一的点集剖分或凸包功能或是用于简单多边形的凸包与剖分时效果也很好     

空间散点集Delaunay四面体剖分切割算法

提出最大空圆凸多边形和最大空球凸多面体的概念，在此基础上，提出一种空间散乱点集Delaunay四面体剖分算法，即对空间散乱点集首先进行最大空球凸多面体剖分，然后在多面体内部作Delaunay四面体剖分，这种方法消除了“退化”现象（平面3个以上点共圆或空间4个以上点共球面）引起的潜在错误，最后分析了一类常见的Delaunay四面体剖分算法的潜在错误。     

平面散点集Delaunay三角剖分的一种高效方法

本探讨了以平面散点集逐点插入的Delaunay三角化方法为基础，在三角化过程中采用一定策略，将其改进成为一种简单高效的方法。该方法能够适应各种边界，包括多岛、多连通域等复杂情况，能够生成贴体的三角网，网格能够保证符合Delaunay法则。     

周培德三角剖分不是最小权三角剖分

平面点集的（欧几里德）最小权三角剖分问题是计算几何和算法领域的一个长期悬而未决的公开问题,周培德于文献[1]中提出了一个新的平面点集三角剖分算,并称该算法能够获得最小权三角剖分,文中通过给出反例,证明了该三角剖分不是最小权三角剖分,因此,最小权三角剖分问题仍有待于进一步研究。     

平面线段集三角剖分的算法

本文提出了计算平面线段集三角剖分的两种算法，第一个算法是利用平面扫描的思想，当扫描线达到事件点时，处理事件点，即将事件点与已被扫描的某些点连接，这样便将已扫描的区域三角剖分，当扫描线达到最左边的事件点时，处理该事件点，就完成了平面线段集的三角剖分，第二个算法基于逐层计算凸壳，并将凸壳改变为多边形，这样便便形成嵌套的多边形层，这些多边形覆盖线段集凸壳内的区域，然后三角剖分每个多边形，即完成平面线段集的三角剖分，两个算法的时间复杂性分别为O（nlogn),O(mnlogn)，其中n为线段集中线估的数目，m为凸壳的层数。     

《周培德三角剖分不是最小权三角剖分》一文商榷——反例不成立

周培协三角剖分是否能得到最小权三角剖分，周培德在《周培德三角部分不是最小权三角剖分》一文撰写之前已有新的结论，本文还指出《周培德三角剖分不是最小权三角剖分》一文所举反例不成立。     

多尺度形态滤波及弹性匹配技术在类星体谱线识别中的应用

本文提出了一种类星体谱线证认方法。首先针对特征为极值点的信号，研究了多尺度膨胀（腐蚀）关于极值点数的两种重要特性及其应用。其一是单调率特性，根据它自动选择滤波器尺度，有效地滤除脉冲噪声；另一种是单调性，它是＂从粗到精＂策略来重新恢复极值特征位置的理论基础。根据这些性质，对光谱进行多尺度膨胀（腐蚀）和特征恢复，以滤除脉冲噪声而不影响谱线特征。然后研究弹性匹配技术应用于谱线证认，并指出了匹配方法中参量的物理意义。该方法对其他一些应用领域也行之有效     

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

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

三维Delaunay三角剖分快速点定位算法研究

提高点定位的速度是提高Delaunay三角剖分运行效率的关键。本文对四面体定位算法进行了研究,结合有向查找定位的技术,建立合理的数据结构,通过对每个搜索四面体只需计算三个面的法向量,优化了基于法向定位的算法,从减少算法中运算量的角度提高运行效率。该算法定位路径唯一,效率更高,而且具有较好的效果。     

基于分治算法构建Delaunay三角网的研究

提出了一种构建Delaunay三角网的分治算法,该算法利用方格网管理离散点数据,仅需分别对每格中的点进行排序;此外,通过对凸包顶点数据进行分区管理,在搜寻凸包支撑线时,能预先确定出支撑点的范围,减少了搜索工作量,提高了三角网的合并速度。     

基于Voronoi 最小邻近点集的Delaunay 三角化方法

针对局部条件下网格生成的需求,提出一种基于节点的Delaunay 三角化 生成算法,该算法以Delaunay 三角形及其对偶Voronoi 图的局部性特征为基础,通过在局部 搜索最小Voronoi 邻近点集,来生成约束点附近的局部网格,通过建立背景索引网格,来提 高算法效率。给出算法的原理证明、程序实现、效率分析和测试结果,并给出了算法的应用 领域。     

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

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

约束Delaunay三角化的研究与实现

针对在文献[1]中提出的边界边、边界面片在Delaunay三角化中的存在条件的3个 命题，给出了采用Voronoi图和邻域的概念的证明过程。并在此基础上，给出了约束Delaun a y三角化的实现算法，进一步丰富了Delaunay三角化的理论基础。     

三维约束Delaunay三角化的实现

分析了约束Delaunay三角化中存在的边界一致性问题,给出了约束Delaunay三角化的理论依据,重点探讨了三维约束Delaunay三角化的可行性条件和范围,同时,给出了三维有限域约束Delaunay三角化的实现方法及其在石油地质勘探数据和机械零件方面的网格剖分实例.这种算法在复杂对象的科学计算和工程分析中发挥了重要作用.     

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

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

一致分布点集Delaunay三角化最佳期望时间算法

对文献(Dwyer R A.Higher-dimensional Voronoi diagrams in linear expected time.Discrete&Computational Geometry,1991,6(4):342-367)给出的对d≥2维空间站点集合构造Delaunay超三角形算法做了改进,提...