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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Delaunay三角网格化算法及实现

在实践的基础上，探讨了Ｄｅｌａｕｎａｙ三角网格化算法的实现技巧，提出了改进措施．是后就平面单连通城的Ｄｅｌａｕｎａｙ三角网格化算法及在空间中的应用做了深入的讨论。

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

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

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

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

一种改进的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三角化.该证明方法比较直观.虽然这类算法对输入点集有一致分布的要求,但在很多实际应用情况下这种要求常是被满足的,此时使用这类算法便可体现文中算法快速和易于实现的优点.

基于优化三角形植被指数(TVI)的灌丛化草原植被地上生物量遥感估测方法研究

灌丛化已经成为草原生态系统中重要的生态问题,而灌丛化草原植被地上生物量(AGB)的精细化估测对于开展区域生态系统碳循环研究有着重要的科学意义。受土壤背景噪声和植被生长结构特征差异的双重影响,现有常见植被指数在灌丛化草原区域构建AGB估算模型时表现极不稳定。针对这一问题,基于Sentinel-2遥感数据,通过优化三角形植被指数(TVI)开展灌丛化草原植被AGB遥感估测方法研究。研究结果表明:1)在以草本植被为主的区域中,基于绿R560、红边R705和近红R865组合形成的TVI与AGB拟合效果最好,R2达到了0.684;而在以灌丛植被为主的区域中,以基于绿R560、红边R783和近红R842组合形成的TVI与AGB拟合效果最好,R^(2)达到了0.368。2)分析现有常用的12种植被指数对土壤的噪声敏感性时,在以草本植被为主的区域中,增强型植被指数(EVI)对土壤噪声表现最为敏感;在以灌丛植被为主的区域中,修正土壤调节植被指数(MSAVI)表现最为敏感。3)在草本植被为主的区域中,相对于TVI,优化后植被指数草地三角形植被指数(GTVI)构建线性估算模型的交叉验证决定系数(R^(2)CV)提高了0.153、交叉验证均方根误差(RMSECV)减小了12.222 g·m^(-2);在灌丛植被为主的区域中,相对于TVI,优化后植被指数GTVI构建线性估算模型的R^(2)CV提高了0.029、RMSECV减小了1.684 g·m^(-2)。4)与常用的12种植被指数构建的估测模型相比,无论在草本植被区域还是灌丛植被区域,GTVI构建的估测模型都具有最高的精度。该研究结果以期为采用植被指数法开展灌丛化草原植被地上生物量遥感估算提供科学依据和参考。

基于Delaunay三角化方法的三维辐射场可视化研究

根据三维空间立体剖分特点,采用逐点插入法对空间离散点的三角剖分进行改进;对理论计算或实测产生的辐射场离散数据进行重构,得到三维空间内连续分布的辐射场数据;最后结合VR仿真技术,构建某核设施的三维仿真场景,并利用可视化映射技术,实现虚拟环境中的三维辐射场的可视化。结果表明,VR技术与Delaunay三角化方法结合使用可显著提高三维辐射场可视化的质量与效率。

基于无锁原子操作的多线程并行Delaunay三角化算法

基于OpenMP实现了一种基于空腔交叠互斥准则与无锁原子操作的Delaunay三角化增量插点细粒度并行算法。在串行算法的基础上,对点集引入Hilbert排序,使相邻点在几何上亦相邻。引入互斥机制——仅当各空腔无公共单元及公共相邻边时,才可同时插入,根据Delaunay局部性准则可保证整个网格都具备Delaunay属性。每个单元用一个原子变量标记该单元是否已被占有,在计算Delaunay空腔时,各线程将试图写入该原子变量,但本竞争机制保证有且仅有一个线程能成功获得该单元的所有权,以保证算法的互斥性。经数值实验表明,对于10~7的点集,该算法在16核下加速比可达7.06倍。

基于克里金和三角剖分联合的数据网格化方法研究

在物化探数据网格化插值计算中,常采用克里金法和三角剖分法。克里金法通过区域限制范围内进行无偏和方差最优估计区域化空间变量取值,可对无数据边界区域进行插值,但异常有位移和弱化现象;三角剖分法利用最小内角最大准则进行Delaunay三角剖分,形成三角形不规则网络TIN(Triangulated Irregular Network),并通过线性插值的方式进行数据网格化,由于保留了原始数据,异常位置准确且无位移,但对于无数据的边界区域无法插值。本文融合克里金法和三角剖分法的优点,采用克里金法进行无偏最优插值,利用Delaunay三角剖分形成三角不规则网络,通过对三角不规则网络等值线追踪绘制等值线。最后利用一组极化率数据进行了对比验证,该方法绘制的等值线图,四周空白区域得到了插值填充,5个原始极值点得到了完整保留。结论表明,该方法既能对无数据区域进行插值,又能保证极值点大小不弱化、位置不偏移,是提高物化探成果精度的有效手段。

基于三维Delaunay三角化的快速可视化方法

随着数字海洋战略的深入发展,把不可见的海洋环境参数物理量转变为可见的形式,直观显示和描绘其中的内涵和规律是对计算机虚拟现实与可视化手段提出的迫切需求。针对海洋环境信息三维可视化的快速性问题,提出了一种基于模糊聚类分析和三维Delaunay三角化的大量数据可视化快速方法。该方法采用模糊C均值聚类分析对原始离散数据集进行预处理,得到需要的分类数据集,并提出了一种改进的三维Delaunay三角化快速算法,该算法通过建立点与点之间的相对位置关系来进一步提高点的定位速度,同时给出了生成新四面体的优化处理方法,从而在大量三维离散点集中快速构建三维曲面,最后采取颜色法进行可视化,并将该方法应用于海洋温度场的三维可视化。通过对某海域温度数据的多组可视化仿真实验的比较与分析,验证了提出方法的快速性和有效性。