首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 171 毫秒
1.
毕硕本  陈东祺  颜坚  郭忆 《计算机科学》2014,41(10):317-320
提出了一种基于并行二维凸壳算法的平面点集的Delaunay三角网生成算法。该算法基于颜坚等在文献[20]中提出的并行二维凸壳算法,在构建凸壳时记录被替换的边和被删除的点,形成一个初始三角网;再在初始三角网的各个三角形内部,采用逐点插入法构建局部的Delaunay三角网;最后,对各个局部Delaunay三角网的边界边进行局部优化,得到原点集的Delaunay三角网。文中给出了算法的正确性说明,实验结果也表明该算法稳定高效。  相似文献   

2.
Delaunay三角网高效构建及地形仿真应用   总被引:1,自引:0,他引:1       下载免费PDF全文
针对基于离散点的Delaunay三角网构建过程中待插入点的定位耗时问题,提出Delaunay三角网高效构建算法,并将其用于三维地形仿真应用中。对大量数据点进行分块排序预处理后,运用空间自相关理论使下一个待插入点总是紧邻新近插入点,融合最短路径定位算法和三角形面积法,结合三角形重心与点、有向线段的关系遍历三角形,减少遍历时间。在对三角网进行LOP局部优化时,采用Delaunay四叉树保存待调整的所有边的节点信息,提高遍历效率。实验结果证明,该算法构建的三维地表真实感较强,并且具有较低的时间复杂度。  相似文献   

3.
改进的Delaunay三角网渐次插入生成算法   总被引:2,自引:0,他引:2       下载免费PDF全文
许建中  马利庄 《计算机工程》2008,34(17):254-256
提出一种改进的Delaunay三角网渐次插入生成算法。在边界初始化阶段,无须对插入点进行排序,只须按链表顺序插入,在LOP算法中,因交换对角线而产生的新三角形只须遵循Delaunay三角化原则由里向外更新邻接三角形。实验结果表明,改进的算法能提高效率,加快Delaunay三角网的构建速度。  相似文献   

4.
基于Delaunay三角剖分生成Voronoi图算法   总被引:4,自引:0,他引:4  
针对Delaunay三角网生长算法和间接生成Voronoi图算法构网效率不高的问题,提出了一种Delaunay三角网生长法间接生成Voronoi图的改进算法。该算法以点集凸壳上一边快速生成种子三角形,定义了半封闭边界点的概念,在三角形扩展过程中动态删除封闭点及半封闭边界点,加快Delaunay三角网生成速度。然后又定义了有序目标三角形的概念,该算法能迅速查找点的有序目标三角形,生成无射线的Voronoi图;考虑凸壳上点的特性,借助三个无穷点生成带射线的Voronoi图。通过实验结果分析表明,改进的算法执行效率有了很大提高。  相似文献   

5.
在常规逐点插入算法的基础上,提出了一种改进的逐点插入构建Delaunay三角网的算法。引入散乱点集有序化、三角形单元分类的方法快速生成Delaunay三角网。  相似文献   

6.
基于Delaunay三角网的CBDT聚类算法研究   总被引:1,自引:0,他引:1  
聚类分析是空间数据挖掘的重要方法之一.Delaunay三角网具有良好的空间邻近特性,应用于空间聚类分析具有独特的优势,提出了一种基于Delaunay三角网的聚类算法--CBDT算法,该算法采用了将Delaunay三角剖分得到的三角形划分为小三角形、狭长三角形和大三角形的聚类模型,通过一定规则分别以小三角形、狭长三角形为基准进行扩展从而实现聚类.CBDT算法相对于AUTOCLUST算法能识别密度渐变的簇,而且计算量要比AUTOCLUST小得多.经实验验证,证明了该算法的有效性.  相似文献   

7.
以优先点为中心的Delaunay三角网生长算法   总被引:1,自引:0,他引:1       下载免费PDF全文
目的 Delaunay三角网具备的优良性质使其得到广泛的应用,构建Delaunay三角网是计算几何的基础问题之一,为了高效、准确地构建大规模点集的Delaunay三角网,提出一种基于优先点的改进三角网生长算法.方法 算法以逆时针次序的一条凸包边为初始基边,使用基边对角最大化并按照逆时针次序选定第3点构建一个Delaunay三角形,通过待扩展边列表中的数据判断新生成的两条边是否需要扩展,采用先进先出的方式从待扩展边列表中取边作为基边,以优先点为中心构建局部Delaunay三角网使优先点尽快成为封闭点,再从点集中删除此封闭点.结果 对于同一测试点集,改进算法运行时间与经典算法运行时间的比率不超过1/3,且此比率随点集规模增长逐步下降.相比经典算法,改进算法在时间效率上有较大提升.结论 本文改进算法对点集规模具有较好的自适应性与较高的构网效率,可用于大规模场景下Delaunay三角网的构建.  相似文献   

8.
Delaunay三角网在GIS/VR中用途广泛,分割-归并法和逐点插入法是目前普遍用于生成Delaunay三角网的两种算法.在研究基于这两种算法的合成算法后,对其进行了两点改进.一是简化凸壳的生成;二是三角形快速定位,通过确定向量之间的关系来解决点的定位问题,避免了复杂运算.实验结果证明,改进后的算法不仅继承原算法兼顾空间和时间的性能,且执行效率有明显提高.  相似文献   

9.
讨论了离散点建立Delaunay三角网算法的研究现状,并采用网格划分提高构网速度。由于三角形定位的速度是影响构网速度的关键因素,改进了基于点线关系方向定位算法,充分利用点与三角形的拓扑关系,减少点线关系的方向定位算法中计算重心的次数,从而提高了三角形定位的效率和构网速度。通过测试证明了算法的高效型和稳定性。  相似文献   

10.
基于最小距离简单多边形的Delaunay三角剖分算法   总被引:2,自引:1,他引:1  
简单多边形的Delaunay三角剖分,在计算机图形学及三维建模领域有着广泛的应用.提出了一种时间复杂度为O((n-4)2)的基于三角形顶点距离最小的简单多边形Delaunay三角剖分算法.通过三角形顶点的最小距离,形成简单多边形的初始三角网,而后对初始三角网进行Delaunay剖分,并对算法的时间复杂度进行了分析.通过实例表明,此算法在时间复杂度和三角形形态质量上都得到了很大改进.  相似文献   

11.
针对现有三维重建算法速度较慢的问题,提出了一种基于快速Delaunay三角化的散乱数据点的三维重建算法。首先,提出一种新的平面Delaunay三角化插入点目标三角形定位算法,利用插入点的方向搜索线与三角形是否相交以及交点个数加速目标三角形定位,不用额外判断点是否在三角形内;其次,自动检测曲面漏洞,利用凸壳的边界拼接方法进行漏洞弥补。实验结果表明,本算法不仅能较好地重建出三维模型,而且有较高的效率。  相似文献   

12.
在极限约束法基础上提出了一种非编码点匹配的改进算法,首先采用极限约束法得到候选匹配对应点,然后按编码点位置将图像Delaunay三角化,缩小匹配范用。在对应Delaunay三角形内确定匹配点,若在三角形范围内仍不能唯一的确定匹配点,则通过交比不变性来实现对应点的匹配。本方法不限制标志点的粘贴位置,满足摄影测量中实际应用要求。  相似文献   

13.
改进的自连接Delaunay三角网生成算法   总被引:19,自引:0,他引:19  
凌海滨  吴兵 《计算机应用》1999,18(12):10-12
本文提出了一个改进的自连接Delaunay三角网生成算法。在原算法的基础上引进了封闭点的概念,在三角网的生成过程中动态地剔除封闭点,从而大大加快了生成新三角形时对点的查找过程。其次,通过对边扩展过程的研究,发现对除了第一个三角形以外的其他三角形实际上只有两条可扩展的边,新算法对这一点也进行了改进。最后,给出了实验的结果数据。  相似文献   

14.
采用改进的逐点插入算法生成Voronoi图。该算法在逐点插入的过程中生成凸壳,进而生成Delaunay三角剖分。在生成Voronoi图的实现过程中,通过遍历三角形的边顶点快速识别相关的三角形组,进而生成Voronoi图。试验结果表明,该算法能实现,成功生成Voronoi图。  相似文献   

15.
夏俊  李映华 《计算机应用》2017,37(12):3558-3562
在计算曲面Ricci Flow时,会因为三角网格中存在过小的角而出现不收敛的情况。针对这种不收敛的问题,提出一种提高最小角角度的球面凸类图形Delaunay三角剖分再分算法。首先,给出球面凸类图形Delaunay三角剖分再分算法。它的核心操作有两个:1)如果某条Delaunay劣弧被"侵占",通过添加Delaunay劣弧中点分割Delaunay劣弧;2)如果存在"瘦"球面三角形,通过添加球面三角形外接球面小圆圆心分解球面三角形。然后,利用局部特征尺度探索出所提算法的收敛条件并给出输出顶点的一个上界公式。根据实验输出的网格验证,所提算法网格生成的球面三角形没有狭小的角,适合用来计算Ricci Flow。  相似文献   

16.
给出一种新的基于边优先的二维多边形域任意散乱数据的约束Delaunay三角剖分算法.算法结合网格分块技术,提出基于最小搜索圆的点搜索思想,并证明了该思想的正确性,有效地提高了搜索第三点的速度.算法中散乱数据可以是任意复杂的折线、封闭多边形环及离散点.另外,在三角剖分过程中,实时地去掉封闭点和封闭边,极大地加快了构网速度,实现了平面多边形域散乱数据的快速约束Delaunay三角化.  相似文献   

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

18.
This paper presents a new incremental insertion algorithm for constructing a Delaunay triangulation. Firstly, the nearest point is found in order to speed up the location of a triangle containing a currently inserted point. A hash table and 1–3 deterministic skip lists, combined with a walking strategy, are used for this task. The obtained algorithm is compared with the most popular Delaunay triangulation algorithms. The algorithm has the following attractive features: it is fast and practically independent of the distribution of input points, it is not memory demanding, and it is numerically stable and easy to implement.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号