横-纵扫描的Voronoi图栅格生成算法

• 作者: 刘青平 孙文彬 王磊 赵学胜
• 来源期刊: 测绘学报
• 学科: 地球科学
• 关键词: Voronoi图 光栅扫描 栅格距离
• 年，卷（期）: 2019,（3）
• 所属期刊栏目: 地图学与地理信息
• 页码范围: 393-399
• 页数: 7页
• 分类号: P208
• 字数: 2651字
• 语种: 中文

摘要

Voronoi图是计算几何学中一个重要数据结构,在诸多领域具有广泛的应用.栅格扫描算法符合计算机离散特征,优化了欧氏距离算法,是最优的栅格Voronoi图生成算法之一.但是,由于栅格单元距离与欧氏距离的差异,在扫描过程中部分单元的归属不可避免地产生一定的误差,使栅格Voronoi图的应用受到一定限制.本文针对传统扫描算法存在的误差缺陷,提出了一种基于横-纵扫描的栅格Voronoi图改进生成算法.首先,深入分析了传统扫描算法产生误差缺陷的原因和区域分布特征;然后,以3 ×3邻域为模板,在一个正常周期的水平(横向)扫描后,增加一个周期竖直(纵向)扫描,即通过横-纵两个周期扫描实现Voronoi图的准确生成;最后,应用不同的栅格数据进行了试验对比,结果表明:改进后的算法既具备扫描算法效率上的优势,同时解决了原算法扫描的误差缺陷,在高效生成的同时把误差限制在一个格网以内.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王磊	河南理工大学测绘与国土信息工程学院	52	234	8.0	13.0