基于半边数据结构的逐点插入Delaunay三角剖分算法

目的 根据传统的三角剖分算法,提出一种基于半边数据结构的逐点插入Delaunay三角剖分算法,提高三角网的构网效率.方法 在逐点插入Delaunay三角剖分算法中引入半边数据结构,在半边数据结构基础上定义Dart三元组,并为Dart三元组定义一组拓扑和几何操作,实现基于半边数据结构的逐点插入Delaunay三角剖分算法.结果 结合随机生成数据,通过实验结果 比较,证明基于半边数据结构的逐点插入Delaunay三角剖分算法具有较好的执行效率,并且随着点个数的增多,这种优势越加明显.结论 半边数据结构及其拓扑和几何操作能够较好地适应Delaunay三角剖分,提高了构网效率.     

Delaunay三角剖分插值用于超分辨成像

微变焦超分辨成像在插值重建方面比较困难,目前基于最小二乘估计的频域模型和空域模型也都存在一些局限性。为了兼顾超分辨成像的实时性和精确性,该文在图像重建过程中,借鉴Delaunay三角剖分的数学概念,采用随机增量算法,定义了基于Delaunay三角剖分的插值算法。该算法可以提高分辨率,降低运算量。仿真实验结果表明,该算法在图像重建的时间和均方误差方面,均优于共轭梯度最小二乘法,其中基于Delaunay三角剖分的三次方插值算法的优越性更为突出。     

基于八叉树与RBF神经网络的曲面三角网格生成

采用八叉树空间分解法生成曲面离散点集,再由点的最近邻域搜索得到三维散乱点集的Delaunay三角剖分算法,并通过对输入的散乱点集进行数据平滑预处理,确定特征点和提取特征线,从神经网络的权值矩阵直接计算曲线控制顶点或曲面的控制网格,最后结合RBF神经网络,提出了一种快速、有效的曲面三角网格直接生成法,其网格生成质量较好....     

一种基于Graham三角剖分生成Delaunay三角网的算法

目的提出一种基于Graham三角剖分生成Delaunay三角网的算法,加快Delaunay三角网的生成速度.方法首先按Graham扫描法对平面散乱点集进行排序,然后将排好序的点通过可见点的判断连接成Graham三角网,最后利用拓扑结构快速进行优化,使其成为Delaunay三角网.结果通过500至10000个点的测试,表明这种基于Graham三角剖分生成Delaunay三角网的生成速度快于传统基于凸包生成Delaunay三角网的生成速度.结论采用可见点表的数据结构以及利用点、边、三角形的有序性的特点构建Delaunay三角网,是提高建网速度的关键.     

一种确定高阶Delaunay三角网中可用k—OD边的算法

目的构建高阶Delaunay三角剖分方法的数字地形模型,有效地减少局部极值问题,使得地形模型能更好地反映原始地形的真实面貌．方法提出了一种确定高阶Delaunay三角网中可用k-OD边的方法,该方法首先在任意边uv的两侧分别确定两点,使每个点与uv边形成的三角形的外接圆不包含同侧的点,若这两三角形都为k—OD三角形,则uv边是可用k—OD边．结果用Visual C＋＋实现算法,通过实验验证了算法的有效性,对于具有n个点的点集P,在时间O（nk^2＋nklogn）内可以计算出所有的可用k—OD边．结论选择合适的可用k—OD边生成相应的高阶Delaunay三角网来模拟实际地形,可以有效地减少局部极小的数量,使地形模型更接近于实际地形．     

连接不相交线段集成简单多边形新算法

针对连接平面上n条线段构成简单多边形问题,给出了线段集能连接成一个简单多边形的一个充分条件。证明了对线段集S的端点进行Delaunay三角剖分可以找到端点的最近点或次最近点。以此为根据,给出了线段加入到简单多边形使得到的多边形总长度最小的方法,进而给出了连接给定线段集成一个简单多边形的算法。对新算法进行了时间复杂度分析,并给出了算法的正确性证明。通过实例对算法进行了对比,表明新算法可以得到更好的结果。     

基于OpenInventor的空间数据三角网重建

根据测量得到的空间数据在计算机软件平台上直观再现数据所代表的物理意义.针对计算几何中的Delaunay三角网格剖分算法,对空间数据的大地投影点构建Delaunay三角网,利用三维图形软件开发包OpenInventor实现对空间位置属性值(转化为高度或颜色)进行三维动态显示,通过数学建模在计算机软件VC忡平台上实现图像重建.     

二维Voronoi图删除任意生成点算法研究

针对Voronoi图与Delaunay三角网具有的对偶特性,提出一种二维Voronoi图任意点删除网络更新算法.利用具有拓扑关系的双向链表三角网搜索影响多边形区域,以凸耳消元法为工具重新剖分影响域多边形,通过连接剖分后的三角网中相邻Delaunay三角形外接圆圆心,实现二维Voronoi图的重构.与其它方法相比,该方法具有操作简单、容易理解、计算效率高的优点.     

基于散乱点云的快速体积计算法

三维可视化体积计算基本上都是先由散乱点云构建出表面网格模型,然后基于网格模型计算体积,存在计算量大、速度慢的缺点.针对此问题提出一种快速体积计算法,首先使用改进的增量式Delaunay三角剖分对散乱点云进行四面体剖分;然后利用K近邻计算散乱点的拟合曲面和最小生成树,得到各点的法向量;由各点法向量剔除体外四面体;最后计算各四面体体积之和从而得到总体积.实验表明,该算法不仅保证了计算准确度,而且较传统算法大大提高了效率.     

曲面散乱点集的组合三角剖分法

曲面散乱点集的三角剖分广泛应用于三维重建领域.为了更加快速、准确的完成曲面重建,提出了一种组合三角剖分法.此方法将整个剖分过程分为三个步骤:首先借鉴分治算法的思想将整个点集进行区域划分,以降低其拓扑结构的复杂性;之后在各个小区域内依据异侧准则、法向量夹角最大准则、域值距离准则和最小内角最大准则进行直接三角剖分;最后根据三维Delaunay空球准则进行各区域边界的连接,从而完成剖分.实验结果表明,组合法可以准确、快速的实现曲面散乱点集的三角剖分.     

基于最大外接圆的约束Delaunay三角剖分算法

目的 研究构建约束Delaunay三角网的方法 ,提高构建约束Delaunay三角网的速度.方法 基于生长法并利用分治法的思想,以约束边为基边分别向两侧重新构网,先构建Delaunay三角网,然后插入约束边并删除与约束边相交的边,按照构网条件对约束边两侧的空腔构网,直至约束边两侧构建成三角网,最后使其成为约束Delaunay三角网.结果 实验测试表明,在地形点数为5 000时,传统算法构建CDT时间为6 195 ms,笔者算法构建CDT时间为6 007ms,速度明显优于传统算法.结论 算法简单、运算速度快、内存开销小且易于实现.     

移动点的反向最近邻查询

反向最近邻（RNN）查询是空间数据库查询的一个重要的问题。随着无线通讯的发展,时空数据库中反向最近邻查询问题越来越受到关注。本文基于Voronoi图的定义和性质,采用一种不同于Delaunay三角剖分的另外一种三角剖分进行研究,其优势在于对于某个特定点,包含它的三角形的数量较少,查询效率较高。     

改进Delaunay三角剖分算法

针对传统Delaunay算法对非凸三维曲面剖分结果不理想,提出了基于凸划分的改进Delaunay三角剖分算法．研究了复杂曲面剖分的特性,定义了非凸集合凸划分定理,对任意曲面相对投影平面进行划分．利用一组正交平面对任意复杂曲面的划分,通过变换域对曲面进行了Delaunay三角剖分．实验结果表明,改进算法能够在正交平面对头面数据集合进行正确凸划分,在投影平面改进Delaunay三角剖分结果正确,鲁棒性明显增强,并与理论分析一致,验证了改进算法的正确性和有效性．     

DT网格在指纹识别中的应用

DT（Delaunay Triangulation）网格由于其优秀特性,在指纹识别领域得到了广泛应用。研究一种基于DT网格的指纹匹配方法,对指纹细节点的拓扑结构进行Delaunay三角剖分,把空间位置相近的细节点按照一定规则相连,得到三角形网格,基于该网格寻找若干参考点对,实现基于点模式的指纹匹配。实验结果证明了该方法的有效性。     

动态Voronoi图的算法实现

文中讨论了一种动态生成Voronoi图的构造算法。该算法以Delaunay三角网和相应的Voronoi图的对偶关系为基础,利用3个额外生长点,动态实现Delaunay三角网,然后根据优化后的三角网生成最终的Voronoi图。     

装备伪装效果可视化检测技术研究与实现

迷彩伪装是一种对抗军事侦察和武器攻击系统的常用手段,其伪装效果对提高部队战斗力和战场生存能力具有十分重要的作用。采用基于图像的三维重建技术,提出了一种改进的区域增长算法来实现空间散乱点的自主三角构网。该算法引入八叉树思想,对点云进行栅格化存储,以提高点云的搜索效率;在每条边界边向外扩展时,综合考虑与其相邻的两边界边对新扩展三角形的影响,保证三角网格能够稳定地增长;采用三角网格优化算法,使得网格中的三角形接近正三角形。