以优先点为中心的Delaunay三角网生长算法

摘要：

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

关键词：计算几何、Delaunay三角网、生长算法、先进先出、封闭点、优先点

所属期刊栏目：21

分类号：TP391(计算技术、计算机技术)

资助基金：国家高技术研究发展计划863基金项目2012AA102002;国家自然科学基金项目61202194,31470641,61572417,11501489;河南省省院科技合作专项资金项目122106000052 National High Technology Research and Development Program of China122106000052;National Natural Science Foundation of China61202194,31470641,61572417, 11501489

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

页数：共9页

页码：60-68