Volume 48 Issue 5
May  2023
Turn off MathJax
Article Contents
Abstract
References
Related Articles
DUAN Xinqiao, GE Yong, ZHANG Tong, LI Lin, TAN Yongbin. Direct Algorithm for the Exact Voronoi Diagram on Discrete Topographic Space[J]. Geomatics and Information Science of Wuhan University, 2023, 48(5): 799-806. DOI: 10.13203/j.whugis20210566
Citation: DUAN Xinqiao, GE Yong, ZHANG Tong, LI Lin, TAN Yongbin. Direct Algorithm for the Exact Voronoi Diagram on Discrete Topographic Space[J]. Geomatics and Information Science of Wuhan University, 2023, 48(5): 799-806. DOI: 10.13203/j.whugis20210566
shu

Direct Algorithm for the Exact Voronoi Diagram on Discrete Topographic Space

  • 1.

    School of Surveying and Geoinformation Engineering, East China University of Technology, Nanchang 330013, China

  • 2.

    State Key Laboratory of Resources and Environmental Information System, Beijing 100101, China

  • 3.

    Key Laboratory of Mine Environmental Monitoring and Improving Around Poyang Lake, Ministry of Natural Resources, Nanchang, 330013, China

  • 4.

    University of Chinese Academy of Sciences, Beijing 100049, China

  • 5.

    State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China

  • 6.

    School of Resources and Environmental Sciences, Wuhan University, Wuhan 430079, China

  • 7.

    Geospatial Information Technology Collaborative Innovation Center, Wuhan University, Wuhan 430072, China

More Information
  • Received Date: April 30, 2022
  • Available Online: May 23, 2023
  • Published Date: May 04, 2023
    Graphical Abstract
    • Abstract
  •   Objectives  Voronoi diagram is a fundamental structure in geo-computing, but it still encounters the problem of exactness and the challenge of an exact algorithm comparable to planar Voronoi diagrams in the topographic space.
      Methods  The geodesic distance field of computational geometry is introduced into the triangulated irregular network in the discrete topographic surface. The hyperbolic curves representing the bisector are gradually grown from the singularity of the distance field on the edge of the grid. The precise division of the discrete surface is obtained by the arrangement of the hyperbolic curves, and the exact geodesic Voronoi diagram (GVD) is obtained by clustering the divided patches. Then, the exact Voronoi diagrams are tested quantitatively and qualitatively.
      Results and Conclusions  It is found that the exact GVD can bring a basic improvement for the spatial analysis of topographic surface. The direct algorithm based on singular growth and hyperbolic arrangement is intuitive and easy to implement, which avoids the excessive subdivision and preprocessing of grid patches by the existing algorithms, and provides a useful exploration for the development of Voronoi diagram analysis in digital topographic analysis.
    • FullText(HTML)
    • References (37)
  • [1]
    陈军, 赵仁亮, 乔朝飞. 基于Voronoi图的GIS空间分析研究[J]. 武汉大学学报(信息科学版), 2003, 28(S1): 32-37. https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH2003S1008.htm

    Chen Jun, Zhao Renliang, Qiao Chaofei. Voronoi Diagram-Based GIS Spatial Analysis[J]. Geomatics and Information Science of Wuhan University, 2003, 28(S1): 32-37 https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH2003S1008.htm
    [2]
    郭仁忠. 空间分析[M]. 北京: 高等教育出版社, 2001.

    Guo Renzhong. Spatial Analysis[M]. Beijing: Higher Education Press, 2001
    [3]
    赵学胜, 陈军, 王金庄. 基于O-QTM的球面Voronoi图的生成算法[J]. 测绘学报, 2002, 31(2): 157-163. doi: 10.3321/j.issn:1001-1595.2002.02.013

    Zhao Xuesheng, Chen Jun, Wang Jinzhuang. QTM-Based Algorithm for the Generating of Voronoi Diagram for Spherical Objects[J]. Acta Geodaetica et Cartographic Sinica, 2002, 31(2): 157-163 doi: 10.3321/j.issn:1001-1595.2002.02.013
    [4]
    Hu H, Liu X, Hu P. Voronoi Diagram Generation on the Ellipsoidal Earth[J]. Computers & Geosciences, 2014, 73: 81-87.
    [5]
    Okabe A. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams[M]. Chichester: Wiley, 2000.
    [6]
    Shi W Z, Pang M Y C. Development of Voronoi-Based Cellular Automata: An Integrated Dynamic Model for Geographical Information Systems [J]. International Journal of Geographical Information Science, 2000, 14(5): 455-474. doi: 10.1080/13658810050057597
    [7]
    胡鹏, 王海军, 邵春丽, 等. 论多边形中轴问题和算法[J]. 武汉大学学报(信息科学版), 2005, 30(10): 853-857. https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH200510003.htm

    Hu Peng, Wang Haijun, Shao Chunli, et al. Polygon Medial Axis Problem and the Algorithm[J]. Geomatics and Information Science of Wuhan University, 2005, 30(10): 853-857 https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH200510003.htm
    [8]
    Adikusuma Y Y, Fang Z, He Y. Fast Construction of Discrete Geodesic Graphs[J]. ACM Transactions on Graphics, 2020, 39(2): 14.
    [9]
    赵俊莉, 辛士庆, 刘永进, 等. 网格模型上的离散测地线[J]. 中国科学: 信息科学, 2015, 45(3): 313-335. https://www.cnki.com.cn/Article/CJFDTOTAL-PZKX201503002.htm

    Zhao Junli, Xin Shiqing, Liu Yongjin, et al. A Survey on the Computing of Geodesic Distances on Meshes[J]. Scientia Sinica Informationis, 2015, 45(3): 313-335 https://www.cnki.com.cn/Article/CJFDTOTAL-PZKX201503002.htm
    [10]
    沈晶, 刘纪平, 林祥国, 等. 集成距离变换和区域邻接图生成Delaunay三角网的方法研究[J]. 武汉大学学报(信息科学版), 2012, 37(8): 1000-1003. https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201208029.htm

    Shen Jing, Liu Jiping, Lin Xiangguo, et al. A Method for Delaunay Triangulation by Integration of Distance Transformation and Region Adjacency Graphics[J]. Geomatics and Information Science of Wuhan University, 2012, 37(8): 1000-1003 https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201208029.htm
    [11]
    李成名, 陈军. Voronoi图生成的栅格算法[J]. 武汉测绘科技大学学报, 1998, 23(3): 208-210. doi: 10.3321/j.issn:1671-8860.1998.03.005

    Li Chengming, Chen Jun. Raster Based Method for Voronoi Diagram[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1998, 23(3): 208-210 doi: 10.3321/j.issn:1671-8860.1998.03.005
    [12]
    Liu Y, Chen Z, Tang K. Construction of Iso-Contours, Bisectors, and Voronoi Diagrams on Triangulated Surfaces[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1502-1517. doi: 10.1109/TPAMI.2010.221
    [13]
    Liu Y, Wang W, Lévy B, et al. On Centroidal Voronoi Tessellation: Energy Smoothness and Fast Computation[J]. ACM Transactions on Graphics, 2009, 28(4): 101.
    [14]
    Kimmel R, Sethian J A. Computing Geodesic Paths on Manifolds [J]. Proceedings of the National Academy of Sciences of the United States of America, 1998, 95(15): 8431-8435. doi: 10.1073/pnas.95.15.8431
    [15]
    Mitchell J S B, Mount D M, Papadimitriou C H. The Discrete Geodesic Problem[J]. SIAM Journal on Computing, 1987, 16(4): 647-668. doi: 10.1137/0216045
    [16]
    Crane K, Weischedel C, Wardetzky M. Geodesics in Heat: A New Approach to Computing Distance Based on Heat Flow[J]. ACM Transactions on Graphics, 2013, 32(5): 152.
    [17]
    Surazhsky V, Surazhsky T, Kirsanov D, et al. Fast Exact and Approximate Geodesics on Meshes[J]. ACM Transactions on Graphics, 2005, 24(3): 553-560. doi: 10.1145/1073204.1073228
    [18]
    Herholz P, Haase F, Alexa M. Diffusion Diagrams: Voronoi Cells and Centroids from Diffusion[J]. Computer Graphics Forum, 2017, 36(2): 163-175. doi: 10.1111/cgf.13116
    [19]
    Moet E, van Kreveld M, van der Stappen A F. On Realistic Terrains[J]. Computational Geometry, 2008, 41(1/2): 48-67.
    [20]
    Aronov B, Berg M, Thite S. The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains[C]//The 16th Annual European Symposium, Karlsruhe, Germany, 2008.
    [21]
    Liu Y, Tang K. The Complexity of Geodesic Voronoi Diagrams on Triangulated 2-Manifold Surfaces[J]. Information Processing Letters, 2013, 113(4): 132-136. doi: 10.1016/j.ipl.2012.12.010
    [22]
    Liu Y, Goodchild M F, Guo Q, et al. Towards a General Field Model and Its Order in GIS [J]. International Journal of Geographical Information Science, 2008, 22(6): 623-643. doi: 10.1080/13658810701587727
    [23]
    Sharir M, Schorr A. On Shortest Paths in Polyhedral Spaces[J]. SIAM Journal on Computing, 1986, 15(1): 193-215. doi: 10.1137/0215014
    [24]
    Ying X, Wang X, He Y. Saddle Vertex Graph (SVG): A Novel Solution to the Discrete Geodesic Problem[J]. ACM Transactions on Graphics, 2013, 32(6): 170.
    [25]
    Xu C, Liu Y, Sun Q, et al. Polyline-Sourced Geodesic Voronoi Diagrams on Triangle Meshes[J]. Computer Graphics Forum, 2014, 33(7): 161-170. doi: 10.1111/cgf.12484
    [26]
    Qin Y, Yu H, Zhang J. Fast and Memory-Efficient Voronoi Diagram Construction on Triangle Meshes[J]. Computer Graphics Forum, 2017, 36(5): 93-104.
    [27]
    Xin S, Wang G. Improving Chen and Han's Algorithm on the Discrete Geodesic Problem[J]. ACM Transactions on Graphics, 2009, 28(4): 1-8.
    [28]
    王劲峰, 姜成晟, 李连发, 等. 空间抽样与统计推断[M]. 北京: 科学出版社, 2009.

    Wang Jinfeng, Jiang Chengsheng, Li Lianfa, et al. Spatial Sampling and Statistical Inference[M]. Beijing: Science Press, 2009
    [29]
    Persson H J, Jonzén J, Nilsson M. Combining TanDEM-X and Sentinel-2 for Large-Area Species-Wise Prediction of Forest Biomass and Volume[J]. International Journal of Applied Earth Observation and Geoinformation, 2021, 96: 102275.
    [30]
    Salekin S, Burgess J, Morgenroth J, et al. A Comparative Study of Three Non-Geostatistical Methods for Optimising Digital Elevation Model Interpolation[J]. ISPRS International Journal of Geo-Information, 2018, 7(8): 300.
    [31]
    Park S W, Linsen L, Kreylos O, et al. Discrete Sibson Interpolation [J]. IEEE Transactions on Visualization and Computer Graphics, 2006, 12(2): 243-253.
    [32]
    Dobesch H, Dumolard P, Dyras I. Spatial Interpolation for Climate Data[M]. London, UK: ISTE, 2007.
    [33]
    Smith M W. Roughness in the Earth Sciences[J]. Earth-Science Reviews, 2014, 136: 202-225.
    [34]
    Duan X, Li L, Zhu H, et al. A High-Fidelity Multiresolution Digital Elevation Model for Earth Systems[J]. Geoscientific Model Development, 2017. 10(1): 239-253.
    [35]
    Shakhnarovich G, Darrell T, Indyk P. Nearest-Neighbor Methods in Learning and Vision [J]. IEEE Transactions on Neural Networks, 2008, 19(2): 377.
    [36]
    Dyn N, Levin D, Rippa S. Data Dependent Triangulations for Piecewise Linear Interpolation[J]. IMA Journal of Numerical Analysis, 1990, 10(1): 137-154.
    [37]
    Liu Y, Xu C, Fan D, et al. Efficient Construction and Simplification of Delaunay Meshes[J]. ACM Transactions on Graphics, 2015, 34(6): 174.
    • Related Articles

  • Related Articles

    [1]ZHAI Ruoming, HAN Xianquan, GAN Xiaoqing, ZOU Jingui, ZOU Shuangchao, WAN Peng, LI Jianzhou. Extraction of Line Segments from Indoor Point Clouds under Building Geometric Regularization Constraints[J]. Geomatics and Information Science of Wuhan University. DOI: 10.13203/j.whugis20240384
    [2]LIU Yawen, ZHANG Ying, CHEN Quan. Vehicle Point Cloud Data Enhancement Method Combined with Panoramic Image[J]. Geomatics and Information Science of Wuhan University, 2020, 45(7): 1015-1020. DOI: 10.13203/j.whugis20180332
    [3]YU Anbin, MEI Wensheng. An Efficient Management Method for Massive Point Cloud Data of Metro Tunnel Based on R-tree and Grid[J]. Geomatics and Information Science of Wuhan University, 2019, 44(10): 1553-1559. DOI: 10.13203/j.whugis20170419
    [4]ZHU Qing, LI Shiming, HU Han, ZHONG Ruofei, WU Bo, XIE Linfu. Multiple Point Clouds Data Fusion Method for 3D City Modeling[J]. Geomatics and Information Science of Wuhan University, 2018, 43(12): 1962-1971. DOI: 10.13203/j.whugis20180109
    [5]LU Xiaoping, ZHU Ningning, LU Fengnian. An Elliptic Cylindrical Model for Tunnel Filtering[J]. Geomatics and Information Science of Wuhan University, 2016, 41(11): 1476-1482. DOI: 10.13203/j.whugis20140389
    [6]FANG Fang, CHENG Xiaojun. A Fast Data Reduction Method for Massive Scattered Point Clouds Based on Slicing[J]. Geomatics and Information Science of Wuhan University, 2013, 38(11): 1353-1357.
    [7]YING Shen, MAO Zhengyuan, LI Lin, XU Guang. Point Cloud Segmentation of 3D Rabbit Base 3D Voronoi[J]. Geomatics and Information Science of Wuhan University, 2013, 38(3): 358-361.
    [8]TUO Lei, KANG Zhizhong, XIE Yuancheng, WANG Baoqian. Continuously Vertical Section Abstraction for Deformation Monitoring of Subway Tunnel Based on Terrestrial Point Clouds[J]. Geomatics and Information Science of Wuhan University, 2013, 38(2): 171-175,185.
    [9]SUI Lichun, ZHANG Yibin, ZHANG Shuo, CHEN Wei. Filtering of Airborne LiDAR Point Cloud Data Based on Progressive TIN[J]. Geomatics and Information Science of Wuhan University, 2011, 36(10): 1159-1163.
    [10]ZHAN Qingming ZHOU Xingang, XIAO Yinghui, YU Liang, . 对古建筑激光扫描点云进行分割、识别,并利用Hough变换和最小二乘法从点云中提取直线和圆,取得了较满意的结果。对两种算法的提取效果进行了比较。[J]. Geomatics and Information Science of Wuhan University, 2011, 36(6): 674-677.

  • Cited by

    Periodical cited type(22)

    1. 万冠军，苏涛. 移动式三维激光扫描在轨道交通结构变形监测中的应用. 北京测绘. 2024(07): 1015-1019 .
    2. 李佳田，阿晓荟，王聪聪，高鹏，朱志浩，晏玲. 利用高帧频相机检测运动控制轴精细形变. 武汉大学学报(信息科学版). 2022(03): 388-395 .
    3. 赵立都，张双成，向中富，马下平，周银，胡川，冯红刚，陈茂霖，蒋俊秋. 地面三维激光扫描点云应用于滑坡监测中基准统一研究. 灾害学. 2022(02): 84-88 .
    4. 甘立彬. 基于三维激光扫描技术的隧道工程测量与建模. 工程勘察. 2021(06): 58-61 .
    5. 严慧敏. 三维激光扫描在隧道断面测量中应用研究——以宁杭高速公路梯子山隧道为例. 测绘地理信息. 2021(06): 108-111 .
    6. 张辛，向巍，丁涛，宋韬. 基于三维激光扫描技术的穿黄隧洞形变检测研究. 人民长江. 2020(09): 129-134 .
    7. 浦仕贵，甘淑，杨敏. 面向不同分辨率点云的NURBS曲面构建偏差分析比较. 地质灾害与环境保护. 2020(03): 72-76 .
    8. 王峰，王清泉，王红新，温立委. 三维激光扫描技术在地铁工程测量的应用综述. 工程勘察. 2019(01): 56-60 .
    9. 吴俊杰. 高负荷光栅传感网络异常节点数据挖掘方法研究. 激光杂志. 2019(02): 68-72 .
    10. 陈智聪. 桥梁模型的三维激光扫描变形分析及精度评定. 四川建材. 2019(05): 205-206 .
    11. 祝明然. 三维激光测量技术在大型复杂钢结构工程建造中的应用. 测绘通报. 2019(08): 92-95 .
    12. 郝进锋，姜月利，祝庭，唐楠. 基于激光扫描数据的建筑工程质量评估. 激光杂志. 2018(05): 53-56 .
    13. 郑跃骏，岳仁宾. 基于激光扫描的交通隧洞几何形变监测方法. 北京测绘. 2018(11): 1318-1321 .
    14. 马伟丽，王健，孙文潇，陈喆. 基于NURBS曲面模型的滑坡点云形变分析. 中国科技论文. 2018(21): 2408-2412 .
    15. 王峰. 集成RTK的三维激光扫描技术测量地形的方法. 测绘通报. 2017(03): 71-75 .
    16. 梁周雁，赵富燕，孙文潇，邵为真. 基于三维激光扫描技术的地表变形监测方法研究. 测绘与空间地理信息. 2017(06): 213-216+219 .
    17. 葛聪. 激光扫描的物流条形码识别系统. 激光杂志. 2017(07): 188-191 .
    18. 唐奇军. 三维激光扫描中隧道变形监测方法分析. 中国高新技术企业. 2017(10): 218-220 .
    19. 常明，康志忠. 利用激光点云的规则面微小变形统计分析. 测绘科学. 2016(03): 138-144+57 .
    20. 林鸿，欧海平，王峰. 地面激光扫描技术在建筑变形测量中的应用探讨. 测绘通报. 2016(06): 73-76 .
    21. 曾繁轩，李亮. 基于Lagrange算子与曲面拟合的点云滤波研究. 激光杂志. 2016(08): 75-78 .
    22. 孔金玲，杨笑天，吴哲超，邵永军，袁雷，赵绍兵，先涛. 基于三维激光扫描技术的高速公路滑坡体建模及应用. 公路交通科技(应用技术版). 2015(12): 12-14 .

    Other cited types(14)

Catalog

    Get Citation
    PDF
    XML
    Article views PDF downloads Cited by(36)
    Related

    Copyright © 2013 《武汉大学学报·信息科学版》编辑部

    Address：武汉大学文理学部本科生院楼北5楼Post Code：430072

    Tel：027-68778465,68788631E-mail:whuxxb@vip.163.com

    Submit Article

    Submission Guidelines

    e

    Contact Us

    Qrcode

    Supported by: Beijing Renhe Information Technology Co., Ltd.  Baidu Analytics

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return