期刊文献+

基于Quad-Edge结构的散乱点集三角剖分并行算法研究及实现

Parallel algorithm of Delaunay triangulation dividing for scattered point set based on Quad-Edge structure
下载PDF
导出
摘要 三角剖分算法在计算几何中的地位非常重要,其中三角网格的剖分效率及质量对后续研究有着重要的影响。对Delaunay三角剖分算法的基本原理进行了分析,基于散乱点集研究了基于Quad-Edge结构下的分治算法,并将目前流行的Map-Reduce并行编程模型引入到对散乱点集进行基于Delaunay三角剖分中。实验结果表明基于Map-Reduce编程模型实现的三角剖分并行化在大数据量的情况下大大提高了剖分的效率,速度明显高于基于Quad-Edge结构实现的分治算法以及基于三角形索引的Bowyer-Watson三角剖分算法,并且具有很好的弹性计算能力,这对三角剖分的后续研究有重要的借鉴作用。 The triangulation dividing algorithm plays an important role in computational geometry,in which the efficiency and quality of triangular mesh are inseparably linked with the follow?up study. In this paper,the basic principle of Delaunay tri?angulation dividing algorithm is analyzed and the divide?and?conquer algorithm for scattered point set is investigated based on the Quad?Edge structure. The popular Map?Reduce parallel programming model is introduced to the Delaunay triangulation divid?ing algorithm when dealing with scattered point set. The experiment result shows the parallel triangulation dividing parallelization can improve the efficiency of this algorithm in the case of mass data by means of Map?Reduce Programming Model. Further?more,this method has good elastic capacity and the efficiency is obviously higher than another two methods,namely the divide?and?conquer algorithm based on the Quad?Edge structure and the Bowyer?Watson triangulation dividing algorithm with triangular index.
出处 《现代电子技术》 北大核心 2015年第6期28-30,35,共4页 Modern Electronics Technique
基金 教育部新世纪优秀人才支持计划(NCET-10-0702) 高等学校博士学科点专项科研基金资助课题(20110184110016) 中央高校基本科研业务费专项资金专题研究项目(SWJTU12ZT08)
关键词 DELAUNAY三角剖分算法 Quad-Edge 并行算法 三角网格 Delaunay triangulation algorithm Quad-Edge parallel algorithm triangular mesh
  • 相关文献

参考文献11

二级参考文献76

共引文献442

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部