平面多边形域的快速约束Delaunay三角化

针对任意平面多边形域,采用增量思想和均匀网格,在局部范围内快速生成约束Delaunay三角形.该方法不会生成区域外的三角形;对存在折线、离散点以及含“洞”的情况不需要特殊处理.实验结果表明,该方法对于随机生成的简单多边形域三角化速度快,平均计算时间呈近似线性.另外,针对文字、工业图案等带状图像的边界多边形,充分利用其近似等宽性优化算法,将其应用于带状图像骨架的快速提取.

二维复杂限定Delaunay三角化算法

针对包括曲线边界和内部带有曲线限定条件的二维Delaunay三角化问题,提出了一种细化算法.首先给出了曲线段的逼近边定义,以保证限定曲线在网格中的存在;然后证明了该算法的收敛性和最终曲线的逼近边集合与原曲线的拓扑一致性,并且生成的网格符合Delaunay优化准则;最后给出了算法的应用实例,验证了其有效性.

三维约束Delaunay三角化的研究

概述了约束三角化的研究进展 .着重分析了三维约束 Delaunay三角化中存在的问题 ,提出并论证了边界边、边界面片在 Delaunay三角化中存在的条件 ,讨论了存在性条件在实际工程中的应用范围 .充实了三维约束Delaunay三角化的研究基础 ,为三维 Delaunay三角化算法的设计提供了理论依据 .

基于Delaunay三角化的指纹匹配方法

将计算几何的三角划分方法引入指纹匹配,研究了一种基于DT(Delaunaytriangulation)网的指纹匹配方法.通过对细节点的拓扑结构进行DT划分,把空间上位置相近的细节点按照一定规则相连,得到三角形网格.然后基于该网格寻找若干参考点对,并根据获得的参考点对将两幅指纹图像进行姿势调整.最后使用获得的参考点对实现基于点模式的指纹匹配.算法在第1届中国生物特征识别竞赛指纹组的测试结果证明了有效性.

约束Delaunay三角化在路线设计中的应用及其生成算法研究

综合分析了 CDT在路线设计中的应用 ,并提出了相应的解决方案。深入研究了适合各种应用的 CDT构建算法 ,即先不考虑约束条件构建初级标准 DT,再将约束边嵌入初始 DT中的两步法。标准 DT的构建采用改进和优化后的逐点插入算法 ,通过建立网格索引 ,实现数据的高效组织和管理 ,再结合方向搜索技术 ,研究出了三角形的快速定位算法。采用 WATSON的“数据相关三角形”算法优化构网 ,为减少优化时间 ,提出了按网格轮流取点的策略。实践证明 ,该算法具有速度快、网形优、精度高、用途广的特点。

基于局部修复的移动数据点Delaunay三角化快速更新方法

在移动数据点Delaunay三角化更新问题中,采用双三角单元过滤算法能够检测出大部分连接关系未发生改变的双三角单元结构,当在算法中出现反转三角单元时,需要重新计算所有数据点的Delaunay三角化.基于以上问题,提出一种具有局部修复的双三角单元过滤算法,通过在局部区域检查三角单元反转并进行修复,避免对所有数据点进行重新Delaunay三角化.实验结果表明,对于三角单元反转出现较多的情况,该算法能够节省约20%～30%的运行时间,提高了原有算法的效率.

基于距离和局部Delaunay三角化控制的颗粒离散元模型填充方法研究

根据颗粒离散元Kelvin接触力计算模型,分析了圆形颗粒体模拟材料力学特性应具备的条件,在此基础上提出了一种新颗粒模型构建方法。该方法首先在复杂模型域内随机生成种子,然后利用相切条件逐步扩展填充整个区域。填充过程中借助局部Delaunay三角化网格控制新颗粒的生成,采用复杂几何体距离控制颗粒与模型边界的相对位置,对靠近模型边界的颗粒进行容忍性优化填充,从而增加模型颗粒与边界的耦合性。同时对模型孔隙进行再填充,保证每个填充颗粒至少与3个颗粒相切,提高了模型内颗粒间的耦合性和模型的密度。最后采用任意多边形控制材料边界,将模型材料的设置简化为判断点是否在多边形内,简化了复杂模型材料属性的设置过程。结果表明:与膨胀颗粒生成法相比,该方法生成模型重叠量小、颗粒间及颗粒-边界相互耦合、填充率高。因此,颗粒黏结力破坏后不会造成飞溢现象,可适用于任意连通域模型的生成,能更好地实现复杂岩土细观介质变形破坏机制的模拟与研究。

结合前沿推进的Delaunay三角化网格生成及应用

采用一种新的混合网格生成方法,生成复杂区域的非结构化网格.结合前沿推进法和Delaunay三角化两种非结构网格生成方法的特点,在边界处采用前沿推进法进行三角形初始网格的生成,在边界区域内部采用Delaunay三角化方法自动生成内部节点.分析表明,该算法简化网格生成过程,能够快速有效地生成非结构化网格.在计算时间以及网格的均匀性方面与其他方法相比具有一定的优势.最后,用混合网格生成方法生成方柱绕流的计算域网格,并运用基于特征线方程的分离算法进行流场计算.

面向四面体网格生成的曲面Delaunay三角化算法

提出了一种曲面域Delaunay三角网格的直接构造算法。该算法在曲面网格剖分的边界递归算法和限定Delaunay四面体化算法的基础上,利用曲面采样点集的空间Delaunay四面体网格来辅助曲面三角网格的生成,曲面上的三角网格根据最小空球最小准则由辅助四面体网格中选取,每个三角形都满足三维Delaunay空球准则,网格质量有保证,并且极大的方便了进一步的曲面边界限定下的Delaunay四面体化的进行。

带权优化约束Delaunay三角化算法

Delaunay细化算法是目前大多数约束Delaunay三角化算法的主要思想,针对其要求输入的约束条件中不能包含夹角较小的尖角的问题,给出了Delau-nay细化算法收敛的充分条件,并通过在尖角点和尖角边处引入带权点和带权Delau-nay空圆/球准则的方法提出了一种带权优化约束Delaunay三角化算法,解决了经典的细化算法在尖角处算法不收敛时需引入辅助控制区域以及过多辅助点的问题,对算法的收敛性进行了分析,给出了相应的算法应用实例,可以应用于复杂几何对象的科学计算和工程分析.

一种基于Delaunay三角化的手写体文字细化方法

为了对手写体文字进行快速准确的识别 ,基于 Delaunay三角化方法 ,提出了一种新的文字图象细化算法 .该算法首先通过对文字图象边界的近似多边形进行 Delaunay三角化 ,同时把其分成一系列保持拓扑关系的三角形 ;然后根据三角形的类型生成不同的局部骨架 ;最后连接生成整幅文字图象的骨架 .由于该算法充分利用了图象的全局和局部信息 ,因此具有速度快 ,效果好等优点 .

基于约束Delaunay三角化的二维非结构网格生成方法

给出基于局部重构和边交换技术的两种约束Delaunay三角剖分方法并证明其收敛性.采用边界指示法恢复流场形状;在预设尺度的指导下融合流场边界曲率、中轴线、梯度限制等信息修正流场尺度;运用Spring方法布置边界点,通过符号面积函数和概率筛选法布置计算区域节点;运用Spring-Laplace方法优化节点位置,伴同边交换和边吞噬技术优化网格结构.该方法可自由进行局部自适应加密或稀疏,并应用于映射曲面网格生成和移动网格技术.

二维任意域约束Delaunay三角化的实现

本文设计了一种逐点加入一局部换边法，提出并证明了二维约束边在约束Ｄｅｌａｕｎａｙ三角化中存在的条件，并据４匕用中点加点法实现了二维任意域的Ｄｅ．ｌａｕｎａｙ三角剖分，生成的网格均符合Ｄｅｌａｕｎａｙ优化准则，网格的优化在网格生成过程中完成，算法复杂度与点数呈近似线性关系，给出了算法在平面域剖分和包含复杂断层的石油地质勘探散乱数据点集剖分的应用实例。

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

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

基于Delaunay三角化和谱方法的非精确点模式匹配算法

当两个要匹配的点模式不同构时,以谱方法为基础的点模式匹配算法性能较差。为了提高谱方法对非同构点模式的匹配性能,将Delaunay三角化过程与谱方法结合起来,提出了一种新的非精确点模式匹配算法。该算法为了缩小非对应点的影响范围,在Delaunay三角化的基础上定义点模式的局部结构,并通过在局部结构层次上应用谱方法找出最相似的局部结构对,然后以此为指导对两个点模式内剩下的点进行匹配。仿真实验结果表明,该算法优于现有的以谱方法为基础的点模式匹配算法。

一种基于三维Delaunay三角化的曲面重建算法

提出一种基于三维Delaunay三角化的区域增长式曲面重建方法。该方法以空间点云的Delaunay三角化为基础,结合局部区域增长的曲面构造,较以往方法具有人为参与更少、适用范围更广的优点。算法采用增量式插入点的方式构建空间Delaunay划分,采用广度优先算法,以外接圆最小为准则从Delaunay三角化得到的四面体中抽取出合适的三角片构成曲面。该算法的设计无须计算原始点集的法矢,且孔洞系数对重建的结果影响很小,重建出的三角网格面更符合原始曲面的几何特征。无论待建曲面是否是封闭曲面,本算法均可获得较好的重建效果。

黎曼流形的Delaunay三角化和Voronoi图

主要研究黎曼空间中Delaunay三角化和Voronoi图.首先,分析和讨论了黎曼流形的Delaunay三角化和Voronoi图的存在性和生成算法.然后,在分析已有研究成果基础上,给出了黎曼流形Delaunay三角化和Voronoi图的一些性质和证明,并提出了采用黎曼流形描述问题的必要性和使用坐标卡研究黎曼流形的优势和意义.最后,以二维流形为例,介绍了将模型初始数据解释为黎曼流形的算法,包括建立坐标卡,定义流形函数等.在黎曼流形定义的基础上,详细描述了基于坐标卡生成模型的Delaunay三角化和Voronoi图的算法,并给出具体实例.

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

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

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

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

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

对文献(Dwyer R A.Higher-dimensional Voronoi diagrams in linear expected time.Discrete&ComputationalGeometry,1991,6(4):342-367)给出的对d≥2维空间站点集合构造Delaunay超三角形算法做了改进,提高了其计算效率,并把站点的分布从限于单位球体扩展成d≥2维空间中任意凸的超多面体.证明了如果站点是独立地从一致分布在凸的超多面体的点集中取出,在线性期望时间内可对站点集实现Delaunay三角化.该证明方法比较直观.虽然这类算法对输入点集有一致分布的要求,但在很多实际应用情况下这种要求常是被满足的,此时使用这类算法便可体现文中算法快速和易于实现的优点.