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

doi:10.11947/j.AGCS.2019.20180088

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

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

刘青平¹, 赵学胜¹, 王磊², 孙文彬¹

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 Qingping¹, ZHAO Xuesheng¹, WANG Lei², SUN Wenbin¹

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)

摘要/Abstract

摘要： 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

中图分类号:

P208

刘青平, 赵学胜, 王磊, 孙文彬. 横-纵扫描的Voronoi图栅格生成算法[J]. 测绘学报, 2019, 48(3): 393-399.

LIU Qingping, ZHAO Xuesheng, WANG Lei, SUN Wenbin. A raster Voronoi diagram generation algorithm based on horizontal-longitudinal scanning[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(3): 393-399.

参考文献

[1] 周培德. 计算几何:算法分析与设计[M]. 北京:清华大学出版社, 2000. ZHOU Peide. Computational geometry:algorithm analysis and design[M]. Beijing:Tsinghua University Press, 2000.
[2] 普雷帕拉塔F P, 沙莫斯M I. 计算几何导论[M]. 庄心谷, 译. 北京:科学出版社, 1990. PREPALATA F P, SHAMOS M I. Computational geometry[M]. ZHUANG Xingu, trans. Beijing:Science Press, 1990.
[3] 刘小凤, 吴艳兰, 胡海. 面状要素的多层次骨架线提取[J]. 测绘学报, 2013, 42(4):588-594. LIU Xiaofeng, WU Yanlan, HU Hai. A method of extracting multiscale skeletons for polygonal shapes[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(4):588-594.
[4] 张雯. 医学可视人真彩图像分割技术研究[D]. 西安:西北工业大学, 2005. ZHANG Wen. Research on medical visualization of human color image segmentation technology[D]. Xi'an:Northwestern Polytechnical University, 2005.
[5] 陆晓庆. 多飞行器协同航路规划与编队控制方法研究[D]. 南昌:南昌航空大学, 2014. LU Xiaoqing. Research on route planning and formation control method for multi aircraft cooperative[D]. Nanchang:Nanchang Hangkong University, 2014.
[6] KASTRISIOS C, TSOULOS L. A cohesive methodology for the delimitation of maritime zones and boundaries[J]. Ocean & Coastal Management, 2016(130):188-195.
[7] SHAMOS M I, HOEY D. Closest-point problems[C]//Proceedings of the 16th Annual Symposium on Foundations of Computer Science. Washington, DC:IEEE Computer Society, 1977:151-162.
[8] GREEN P J, SIBSON R. Computing dirichlet tessellations in the plane[J]. The Computer Journal, 1978, 21(2):168-173.
[9] FORTUNE S. A sweepline algorithm for voronoi diagrams[J]. Algorithmica, 1987, 2(1-4):153-174.
[10] BROWN K Q. Geometric transforms for fast geometric algorithms[D]. Pittsburgh:Carnegie Mellon University, 1979.
[11] HELD M. VRONI:An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments[J]. Computational Geometry, 2001, 18(2):95-123.
[12] OKABE A, BOOTS B, SUGIHARA K, et al. Spatial tessellations:concepts and applications of Voronoi diagrams[M]. 2nd ed. London:John Wiley & Sons, Inc. 2000.
[13] 李成明, 陈军. Voronoi图生成的栅格算法[J]. 武汉大学学报信息科学版, 1998, 23(3):208-210. LI Chengming, CHEN Jun. Raster-based method for Voronoi diagram[J]. Geomatics and Information Science of Wuhan University, 1998, 23(3):208-210.
[14] CHEN J. A raster-based method for computing Voronoi diagrams of spatial objects using dynamic distance transformation[J]. International Journal of Geographical Information Science, 1999, 13(3):209-225.
[15] RONG Guodong, TAN T S. Variants of jump flooding algorithm for computing discrete Voronoi diagrams[C]//Proceedings of the 4th International Symposium on Voronoi Diagrams in Science and Engineering. Glamorgan, UK:IEEE, 2007:176-181.
[16] GUO Licai, WANG Feng, HUANG Zhangjin, et al. A fast and robust seed flooding algorithm on GPU for Voronoi diagram generation[C]//Proceedings of 2011 International Conference on Electrical and Control Engineering. Yichang, China:IEEE, 2011:492-495.
[17] 李佳田, 陈军, 赵仁亮, 等. 基于线性四叉树结构的Voronoi图反向膨胀生成方法[J]. 测绘学报, 2008, 37(2):236-242. DOI:10.3321/j.issn:1001-1595.2008.02.019. LI Jiatian, CHEN Jun, ZHAO Renliang, et al. A backward inflation generating method for voronoi diagram based on linear quadtree structure[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(2):236-242. DOI:10.3321/j.issn:1001-1595.2008.02.019.
[18] LIANG E H, LIN S G. A hierarchical approach to distance calculation using the spread function[J]. International Journal of Geographical Information Science, 1998, 12(6):515-535.
[19] 寿华好, 袁子薇, 缪永伟, 等. 一种平面点集Voronoi图的细分算法[J]. 图学学报, 2013, 34(2):1-6. SHOU Huahao, YUAN Ziwei, MIAO Yongwei, et al. A subdivision algorithm for a planar point set Voronoi grap[J]. Journal of Graphics, 2013, 34(2):1-6.
[20] 王新生, 刘纪远, 庄大方, 等. 一种新的构建Voronoi图的栅格方法[J]. 中国矿业大学学报, 2003, 32(3):293-296. WANG Xinsheng, LIU Jiyuan, ZHUANG Defang, et al. New raster-based method for constructing Voronoi diagrams[J]. Journal of China University of Mining & Technology, 2003, 32(3):293-296.
[21] MAJDANDZIC I, TREFFTZ C, WOLFFE G. Computation of Voronoi diagrams using a graphics processing unit[C]//Proceedings of 2008 IEEE International Conference on Electro/Information Technology, 2008. Ames, IA:IEEE, 2008:437-441.
[22] SHIH F Y, WU Yiya. Fast euclidean distance transformation in two scans using a 3×3 neighborhood[J]. Computer Vision and Image Understanding, 2004, 93(2):195-205.
[23] 李淑艳, 曹菡, 刘妮玲. Voronoi图的并行生成算法研究[J]. 郑州轻工业学院学报(自然科学版), 2010, 25(1):105-109. LI Shuyan, CAO Han, LIU Niling. Generation parallel algorithm research of Voronoi diagram[J]. Journal of Zhengzhou University of Light Industry (Natural Science), 2010, 25(1):105-109.
[24] 屠文森, 汪佳佳. Voronoi图栅格生成算法GPU并行实现[J]. 现代电子技术, 2015, 38(4):66-68, 72. TU Wensen, WANG Jiajia. Raster-based method for Voronoi diagram using GPU parallel technology[J]. Modern Electronics Technique, 2015, 38(4):66-68, 72.
[25] FABBRI R, COSTA L D F, TORELLI J C, et al. 2D Euclidean distance transform algorithms:a comparative survey[J]. ACM Computing Surveys, 2008, 40(1):1-44.
[26] 王磊. 基于QTM的球面Voronoi图生成算法与应用[D]. 北京:中国矿业大学(北京), 2016. WANG Lei. QTM-based spherical Voronoi diagram generating algorthms and its application[D]. Beijing:China University of Mining and Technology (Beijing), 2016.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

本文评价

[1]	余莉, 甘淑, 袁希平, 李佳田. 克服双重约束的面目标位置聚类方法[J]. 测绘学报, 2016, 45(10): 1250-1259.
[2]	余莉, 甘淑, 袁希平, 杨明龙. 综合线面特征分布的点目标多尺度聚类方法[J]. 测绘学报, 2015, 44(10): 1152-1159.
[3]	李佳田, 康顺, 罗富丽. 利用层次Voronoi图进行点群综合[J]. 测绘学报, 2014, 43(12): 1300-1306.
[4]	涂伟李清泉方志祥. 基于网络Voronoi图的大规模多仓库物流配送路径优化[J]. 测绘学报, 2014, 43(10): 1075-1082.
[5]	李霖毛凯谭永滨. 基于分层地标的多粒度路径导引描述方法[J]. 测绘学报, 2014, 43(1): 105-112.
[6]	艾廷华禹文豪. 基于水流扩展思想的网络空间Voronoi图生成[J]. , 2013, 42(5): 760-766.
[7]	刘小凤吴艳兰胡海. 面状要素的多层次骨架线提取[J]. , 2013, 42(4): 0-0.
[8]	周启艾廷华张翔. 面向多重空间冲突解决的移位场模型[J]. , 2013, 42(4): 0-0.
[9]	刘万增,陈军,闫超德,赵仁亮,赵勇,孙文彬. 平面离散点集拓扑邻近稳定区域计算模型[J]. 测绘学报, 2012, 41(1): 127-0.
[10]	谢顺平,冯学智,鲁伟. 基于道路网络分析的Voronoi面域图构建算法[J]. 测绘学报, 2010, 39(1): 0-82.
[11]	耿协鹏杜晓初胡鹏. 基于栅格距离变换的扩展对象空间聚类方法[J]. 测绘学报, 2009, 38(2): 0-174.