面向任意分布点云数据的二维Delaunay快速构网算法

摘要：

为了更好地提高对二维点云数据的Delaunay构网效率, 并充分考虑点云数据规模庞大、分布多样的特点, 提出一种Hilbert曲线与多重网格划分相结合的算法. 首先通过多重网格划分解决规则网格对非均匀点集划分程度无法统一的问题; 其次通过添加控制点和采用 Hilbert 曲线顺序遍历网格的方式, 避免逐行遍历网格时产生大量需要重复创建和删除的狭长三角形的情况; 最后通过调整相邻网格间Hilbert曲线遍历顺序, 避免遍历过程的"跳跃"现象, 降低相邻网格插入点的点定位搜索步长. 实验结果表明, 与CGAL、规则网格和多重网格划分算法相比, 该算法的构网效率对于分布均匀和非均匀的点云数据都有明显提升.

关键词：Delaunay三角网、Hilbert曲线、网格划分、多重网格、点云数据

所属期刊栏目：27

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

资助基金：国家科技重大专项2011ZX05056-001-01;海洋公益性行业科研专项201205001

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

页数：共8页

页码：1653-1660