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

摘要：

三角剖分算法在计算几何中的地位非常重要，其中三角网格的剖分效率及质量对后续研究有着重要的影响。对Delaunay三角剖分算法的基本原理进行了分析，基于散乱点集研究了基于Quad?Edge结构下的分治算法，并将目前流行的Map?Reduce并行编程模型引入到对散乱点集进行基于Delaunay三角剖分中。实验结果表明基于Map?Reduce编程模型实现的三角剖分并行化在大数据量的情况下大大提高了剖分的效率，速度明显高于基于Quad?Edge结构实现的分治算法以及基于三角形索引的Bowyer?Watson三角剖分算法，并且具有很好的弹性计算能力，这对三角剖分的后续研究有重要的借鉴作用。

关键词：Delaunay三角剖分算法、Quad-Edge、并行算法、三角网格

分类号：TN911-34

资助基金：教育部新世纪优秀人才支持计划NCET-10-0702；高等学校博士学科点专项科研基金资助课题20110184110016；中央高校基本科研业务费专项资金专题研究项目SWJTU12ZT08

在线出版日期：2015-03-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：28-30,35