测绘学报 ›› 2019, Vol. 48 ›› Issue (3): 393-399.doi: 10.11947/j.AGCS.2019.20180088

• 地图学与地理信息 • 上一篇    下一篇

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

刘青平1, 赵学胜1, 王磊2, 孙文彬1   

  1. 1. 中国矿业大学(北京)地球科学与测绘工程学院, 北京 100083;
    2. 河南理工大学测绘与国土信息工程学院, 河南 焦作 454000
  • 收稿日期:2018-03-08 修回日期:2019-01-01 出版日期:2019-03-20 发布日期:2019-04-10
  • 通讯作者: 赵学胜 E-mail:zxs@cumtb.edu.cn
  • 作者简介:刘青平(1994-),男,硕士生,研究方向为数字地图制图与三维可视化。E-mail:792556868@qq.com
  • 基金资助:
    国家重点研发计划(2018YFB0505301);国家自然科学基金(41671394;41801318;41671383)

A raster Voronoi diagram generation algorithm based on horizontal-longitudinal scanning

LIU Qingping1, ZHAO Xuesheng1, WANG Lei2, SUN Wenbin1   

  1. 1. College of Geoscience and Surveying Engineering, China University of Mining and Technology(Beijing), Beijing 100083, China;
    2. School of Surveying and Land Information Engineering Henan Polytechnic University, Jiaozuo 454000, China
  • Received:2018-03-08 Revised:2019-01-01 Online:2019-03-20 Published:2019-04-10
  • Supported by:
    The National Key Research and Development Program of China (No. 2018YFB0505301);The National Natural Science Foundation of China (Nos. 41671394;41801318;41671383)

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

关键词: Voronoi图, 光栅扫描, 栅格距离

Abstract: The Voronoi diagram is an important data structure in computational geometry and has a wide range of applications in many fields. The scan algorithm of raster is an optimization of the Euclidean distance algorithm, which is in line with the discrete features of computers. It is one of the optimal algorithms for the generation of raster Voronoi diagram. However, due to the difference between the grid distance and the Euclidean distance, the ownership of some grids in the scanning process inevitably has some errors, so that the application of the raster Voronoi diagram is limited. In this paper, according to the characteristics of error existing in traditional scanning algorithms, an improved algorithm for the generation of raster Voronoi diagram based on horizontal-longitudinal scanning is proposed. First of all, the causes and the regional distribution characteristics of defects of the traditional scanning algorithm are analyzed in depth. Then, using the 3×3 neighborhood as a template, a vertical scan is added after a horizontal scan. That is to say, the Voronoi diagram can be generated accurately by horizontal and vertical scanning. Finally, different raster data are used to carry out experimental comparison. The results show that the improved algorithm not only has the advantage of efficiency of scanning algorithm, but also solves the error of the original algorithm. It keeps the efficiency while limiting the error to a grid.

Key words: Voronoi diagram, raster scan, raster distance

中图分类号: