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