梯度Voronoi图及其构建算法

李佳田, 罗富丽, 余莉, 张蓝, 康顺, 林艳

李佳田, 罗富丽, 余莉, 张蓝, 康顺, 林艳. 梯度Voronoi图及其构建算法[J]. 武汉大学学报 ( 信息科学版), 2016, 41(2): 163-170. DOI: 10.13203/j.whugis20140025
引用本文: 李佳田, 罗富丽, 余莉, 张蓝, 康顺, 林艳. 梯度Voronoi图及其构建算法[J]. 武汉大学学报 ( 信息科学版), 2016, 41(2): 163-170. DOI: 10.13203/j.whugis20140025
shu
LI Jiatian, LUO Fuli, YU Li, ZHANG Lan, KANG Shun, LIN Yan. The Gradient Voronoi Diagram and Construction Algorithm[J]. Geomatics and Information Science of Wuhan University, 2016, 41(2): 163-170. DOI: 10.13203/j.whugis20140025
Citation: LI Jiatian, LUO Fuli, YU Li, ZHANG Lan, KANG Shun, LIN Yan. The Gradient Voronoi Diagram and Construction Algorithm[J]. Geomatics and Information Science of Wuhan University, 2016, 41(2): 163-170. DOI: 10.13203/j.whugis20140025
shu

梯度Voronoi图及其构建算法

  • 1.

    昆明理工大学国土资源工程学院, 云南昆明, 650093;

  • 2.

    中国矿业大学(北京)地球科学与测绘工程学院, 北京, 100038;

  • 3.

    中国人民公安大学警务信息工程学院, 北京, 100038

基金项目: 国家自然科学基金(41561082,41161061,41301416)。
详细信息
    作者简介:

    李佳田,博士,副教授,主要研究方向为动态空间关系计算。ljtwcx@163.com

  • 中图分类号: P208

The Gradient Voronoi Diagram and Construction Algorithm

  • 1.

    Faculty of Land Resources Engineering, Kunming University of Science and Technology, Kunming 650093, China;

  • 2.

    College of Geoscience and Surveying Engineering, China University of Mining & Technology(Beijing), Beijing 100083, China;

  • 3.

    Policing Information Technology College, People's Public Security University of China, Beijing 100038, China

Funds: The National Natural Science Foundation of China, Nos. 41561082, 41161061, 41301416.

摘要

    摘要
  • 摘要: 以生长速度为视角,普通Voronoi图及权重Voronoi图是理想欧氏平面上的生长元匀速生长结果。然而,以Voronoi图为基础的实际分析与建模情况不尽如此,通常表现为非理想平面的非匀速生长过程。本文以权重距离函数描述各向异性的非理想平面,以其时间消耗导数一致性形式化生长速度,定义一种新的Voronoi图——梯度Voronoi图。通过以高程变化诱发的梯度生长为例,借助栅格空间中形态学膨胀操作,给出梯度Voronoi图的典型构建算法。算例与分析表明,在等距离边界、势力范围与邻近关系表达方面,梯度Voronoi图更具优势。
    Abstract: Taking the growing processing results as angles, an ordinary Voronoi diagram and weighted Voronoi diagram are produced at uniform speed on an ideal Euclidean plane. However, based on analysis, modeling is not always sound in that a Voronoi diagram progresses at varying velocities on a non-ideal plane. The anisotropic non-ideal plane is depicted by weight distance and the growth velocity is formalized in a form conforming to the time derivative of weight distance. Therefore, a new Voronoi diagram, namely Gradient Voronoi Diagram (GVD) was defined in this paper. Taking the gradient caused by changes in elevation as an example, a typical construction model for GVD was propounded with the help of the dilation operator for mathematical morphology in raster space. An analysis shows that GVD has better guided significance and practical application value in the expression of influence regions and the Voronoi adjacency relationship.
    • HTML全文
    • 参考文献(23)
  • [1] Gold C M. Review:Spatial Tessellations-Concepts and Applications of Voronoi Diagrams[J]. International Journal of Geographical Information Science,1994,8(2):237-238
    [2] Chen Jun. Voronoi-based Dynamic Spatial Data Model[M]. Beijing:Publishing House of Surveying and Mapping,2002(陈军. Voronoi动态空间数据模型[M]. 北京:测绘出版社,2002)
    [3] Okabe A,Boots B,Sugihara K,et al. Spatial Tessellations:Concepts and Applications of Voronoi Diagrams (2nd Edition)[M]. New York:John Wiley and Sons,2000
    [4] Chen Jun,Li Chengming,Li Zhilin, et al. A Voronoi-Based 9-Intersection Model for Spatial Relations[J]. International Journal of Geographical Information Science,2000,15(3):201-220
    [5] Chen Jun,Zhao Renliang,Li Zhilin. Voronoi-Based K-order Neighbors Relations for Spatial Analysis[J]. ISPRS Journal of Photogrammetric and Remote Sensing,2004,59(1/2):60-72
    [6] Zhao Renliang. Voronoi Methods for Computing Spatial Relations in GIS[M]. Beijing:Publishing House of Surveying and Mapping,2006(赵仁亮. 基于Voronoi图的GIS空间关系计算[M]. 北京:测绘出版社,2006)
    [7] Liu Jinyi,Liu Shuang. A Survey on Applications of Voronoi Diagrams[J]. Journal of Engineering Graphics,2004,25(2):125-132(刘金义,刘爽. Voronoi图应用综述[J]. 工程图学学报, 2004,25(2):125-132)
    [8] Chen Jun,Zhao Renliang. Spatial Relations in GIS:A Survey on Its Key Issues and Research Progress[J]. Acta Geodaetica et Cartographica Sinica,1999,28(2):97-102(陈军,赵仁亮. GIS空间关系的基本问题与研究进展[J]. 测绘学报,1999,28(2):97-102)
    [9] Li Jiatian,Kang Shun,Li Xiaojuan,et al. Putting Model for Broad Geographic Annotation[J]. Geomatics and Information Science of Wuhan University,2015,40(1):20-25(李佳田,康顺,李晓娟,等. 宽泛地理注记的投放模型[J]. 武汉大学学报·信息科学版,2015,40(1):20-25)
    [10] Li Jiatian, Kang Shun, Luo Fuli. Point Group Generalization Method Based on Hierarchical Voronoi Diagram[J]. Acta Geodaetica et Cartographica Sinica,2014,43(12):1300-1306(李佳田,康顺,罗富丽. 利用层次Voronoi图进行点群综合[J]. 测绘学报,2014,43(12):1300-1306)
    [11] Mostafavi M A,Gold C, Dakowicz M. Delete and Insert Operations in Voronoi/Delaunay Methods and Applications[J]. Computers & Geosciences,2003,29(4):523-530
    [12] Li Chengming,Chen Jun,Li Zhilin. Raster-Based Methods or the Generation of Voronoi Diagrams for Spatial Entities[J]. International Journal of Geographical Information Science,1999,13(3):209-225
    [13] Wang Xinsheng,Liu Jiyuan,Zhuang Dafang,et al. New Raster-Based Method for Constructing Voronoi Diagrams[J]. Journal of China University of Mining & Technology,2003,32(3):293-296(王新生,刘纪远,庄大方,等. 一种新的构建Voronoi图的栅格方法[J]. 中国矿业大学学报,2003,32(3):293-296)
    [14] Xie Shunping,Wang Jiecheng,Feng Xuezhi,et al. Algorithm for Constructing Voronoi Diagram of Planar Points Based on Approximating and Extracting Vertices[J]. Acta Geodaetica et Cartographica Sinica,2007,36(4):436-442(谢顺平,王结臣,冯学智,等. 基于结点逼近提取的平面点集Voronoi图构建算法[J]. 测绘学报,2007,36(4):436-442)
    [15] Xie Shunping,Feng Xuezhi,Lu Wei. Algorithm for Constructing Voronoi Area Diagram Based on Road Netwrok Analysis[J]. Acta Geodaetica et Cartographica Sinica,2010,39(1):88-94(谢顺平,冯学智,鲁伟. 基于道路网络分析的Voronoi面域图构建算法[J]. 测绘学报,2010,39(1):88-94)
    [16] Geng Hong,Tang Xu,Zhu Guorui. Method for Plotting the Affected Area of Urban Roads Based on Spatial Competing[J]. Geomatics and Information Science of Wuhan University,2004,29(6):521-524(耿红,唐旭,祝国瑞. 基于空间竞争的城市道路影响域划分方法研究[J]. 武汉大学学报·信息科学版,2004,29(6):521-524)
    [17] Dong Pinliang. Generating and Updating Multiplicatively Weighted Voronoi diagrams for Point, Line and Polygon Features in GIS[J]. Computers & Geosciences,2008,34(4):411-421
    [18] Miller G L,Talmor D,et al. Data Generation for Geometric Algorithms on Non-uniform Distributions[J]. International Journal of Computer Geometry Application,1999,9(6):577-599
    [19] Okabe A,Satohb T,Furutac T,et al. Generalized Network Voronoi Diagrams:Concepts,Computational Methods,and Applications[J]. International Journal of Geographical Information Science,2008,22(9):1-30
    [20] Aurenhammer F,Edelsbrunner H. An Optimal Algorithm for Constructing the Weighted Voronoi Diagram in the Plane[J]. Pattern Recognition,1984,17(2):251-257
    [21] Gahegan M,Lee I. Data Structures and Algorithms to Support Interactive Spatial Analysis Using Dynamic Voronoi Diagrams[J]. Computers, Environment and Urban Systems,2000,24(6):509-537
    [22] Yu Li.Typical Clustering Method Compared Between Distance Proximity and Natural Neighbor[D]. Kunming:Kunming University of Science and Technology,2011(余莉. 距离邻近与自然邻近典型聚类方法比较[D]. 昆明:昆明理工大学,2011)
    [23] Rafael C Gonzalez,Richard E Woods. Digital Image Processing (2nd Edition)[M]. Beijing:Publishing House of Electronics Industry,2003
    • 相关文章
    • 施引文献(71)

  • 期刊类型引用(46)

    1. 刘春雷，张媛静，陆晨明，李亚松，李剑锋. 基于时序InSAR的九龙江河口地区地面沉降时空演变规律及成因分析. 应用海洋学学报. 2024(01): 116-125 . 百度学术
    2. 陈瑞瑞，孙颢月，朱紫若，蒋雪中，陈沈良，陈静. 黄河三角洲地面沉降研究进展与未来展望. 海岸工程. 2024(01): 1-23 . 百度学术
    3. 赵凤阳，周吕，魏玉业. 融合改进鲸鱼算法解缠的梧州市地面沉降InSAR监测. 遥感信息. 2024(01): 52-58 . 百度学术
    4. 侯永浩，张兴，李晓民，李宗仁. SBAS-InSAR技术在地质灾害调查中的应用. 北京测绘. 2024(10): 1477-1481 . 百度学术
    5. 柳新强，姜刚，刘军峰，贺国伟. PS-InSAR和SBAS-InSAR的地表沉降监测对比研究——以雄安新区为例. 工程勘察. 2023(01): 62-67 . 百度学术
    6. 曾敏，皮鹏程，赵信文，陈松，彭红霞，侯清芹，孙慧敏，薛紫萱. 基于PS-InSAR的珠江口典型填海造地区地面沉降时空特征研究. 华南地质. 2023(01): 116-126 . 百度学术
    7. 李文慧，王志伟，赵月，王翔. 基于SNAP-StaMPS方法的高速公路沿线地面沉降监测. 测绘工程. 2023(03): 36-43 . 百度学术
    8. 周定义，左小清，赵志芳，喜文飞，葛楚. 基于SBAS-InSAR和改进BP神经网络的城市地面沉降预测. 地质通报. 2023(10): 1774-1783 . 百度学术
    9. 刘泽洲，卢才武，章赛，李萌，和郑翔. 基于多阈值目标提取的时序InSAR矿区地表沉降监测研究. 中国矿业. 2022(08): 79-85 . 百度学术
    10. 王新田，刘增珉，陈建忠，梁菲，孟萌，李天鹤. 山东省地表形变InSAR监测与分析. 测绘通报. 2022(S2): 130-134 . 百度学术
    11. 邓晓景，曲国庆，张建霞，席换，王晖. 融合升降轨PS-InSAR东营市地面沉降监测. 山东理工大学学报(自然科学版). 2021(01): 10-16 . 百度学术
    12. 杨利，薛东剑，王海方，付林，张婷. 五龙沟矿区时序InSAR地表形变监测. 中国矿业. 2021(03): 107-112 . 百度学术
    13. 程琳琳，杨玉曼，李月颖，孙梦尧，王振威，焦路尧. 矿业型村镇转型期发展问题分析与策略研究：以北京市门头沟区为例. 中国矿业. 2021(03): 101-106 . 百度学术
    14. 王辉，曾琪明，焦健，陈继伟. 结合序贯平差方法监测地表形变的InSAR时序分析技术. 北京大学学报(自然科学版). 2021(02): 241-249 . 百度学术
    15. 付云霞，管勇，王晓丹，王建收，尹政，周晓雪，王青，徐美君. 大型河口三角洲地面沉降机制研究——以黄河三角洲为例. 海岸工程. 2021(02): 83-95 . 百度学术
    16. 关金环，高明亮，宫辉力. 首都国际机场区域差异性沉降原因探讨. 测绘科学. 2021(09): 67-75 . 百度学术
    17. 柴华彬，胡吉彪，耿思佳. 融合实测数据的地表沉降SBAS-InSAR监测方法. 煤炭学报. 2021(S1): 17-24 . 百度学术
    18. 程霞，张永红，邓敏，吴宏安，康永辉. Sentinel-1A卫星的黄河三角洲近期地表形变分析. 测绘科学. 2020(02): 43-51 . 百度学术
    19. 卢旺达，韩春明，岳昔娟，赵迎辉，周格仪. 基于Sentinel-1A数据的天津地区PS-InSAR地面沉降监测与分析. 遥感技术与应用. 2020(02): 416-423 . 百度学术
    20. 向淇文，潘建平，张广泽，徐正宣，张定凯，涂文丽. 基于SBAS技术的川藏铁路折多山地区地表形变监测与分析. 测绘工程. 2020(04): 48-54+59 . 百度学术
    21. 张金盈，崔靓，刘增珉，王新田，林琳，徐凤玲. 利用Sentinel-1 SAR数据及SBAS技术的大区域地表形变监测. 测绘通报. 2020(07): 125-129 . 百度学术
    22. 狄桂栓. 基于InSAR技术的黄河三角洲区域地表形变浅析. 地理空间信息. 2020(09): 106-109+8 . 百度学术
    23. 高辉，罗孝文，吴自银，阳凡林. 基于时序InSAR的珠江口大面积地面沉降监测. 海洋学研究. 2020(02): 81-87 . 百度学术
    24. 韩红花. 黄河三角洲区域地表形变监测研究. 山东国土资源. 2020(11): 69-72 . 百度学术
    25. 夏元平，陈志轩，张毅. 南昌市地面沉降InSAR监测及影响因子分析. 测绘科学. 2020(11): 115-122+129 . 百度学术
    26. 贺跃光，肖亮. 某水溶开采矿区短基线集InSAR高相干点探测. 中国锰业. 2019(01): 89-93 . 百度学术
    27. 张静，丁黄平，刘纯，谢文然，时雨. 基于InSAR技术的盘锦地区地面沉降研究. 世界地质. 2019(02): 574-580 . 百度学术
    28. 韩红超，符华年，张文峰，温浩. InSAR、水准多维沉降监测体系建设及应用研究. 测绘通报. 2019(S1): 236-241 . 百度学术
    29. 师芸，李伟轩，唐亚明，席磊，孟欣. 时序InSAR技术在地球环境监测及其资源管理中的应用:以交城-清徐地区为例. 武汉大学学报(信息科学版). 2019(11): 1613-1621 . 百度学术
    30. 杨帆，王道顺，张磊，张子文. 基于时序InSAR的隧道工程形变监测与分析. 测绘与空间地理信息. 2019(10): 1-4 . 百度学术
    31. 黄洁慧，谢谟文，王立伟. 基于SBAS-InSAR技术的白格滑坡形变监测研究. 人民长江. 2019(12): 101-105 . 百度学术
    32. 黄洁慧，谢谟文，王立伟. 基于差分干涉合成孔径雷达技术的米林滑坡形变监测. 科学技术与工程. 2019(25): 7-12 . 百度学术
    33. 李锁乐，吴宏安，张永红，康永辉，左振华. 包头市地面沉降高分辨率时序InSAR监测. 测绘科学. 2018(09): 76-80 . 百度学术
    34. 杨帆，张磊，张子文，赵增鹏. 利用短基线集InSAR技术监测抚顺市地面沉降. 测绘通报. 2018(03): 84-88 . 百度学术
    35. 张静，冯东向，綦巍，周雪，赵玉星. 基于SBAS-InSAR技术的盘锦地区地面沉降监测. 工程地质学报. 2018(04): 999-1007 . 百度学术
    36. 贺晓阳，赵盟，程存付. 小基线集技术在矿区地表形变监测中的应用. 河南科技. 2018(13): 97-98 . 百度学术
    37. LIU Xiao，LIU Jie，FENG Xiuli. Inversion and Prediction of Consolidation Settlement Characteristics of the Fluvial Sediments Based on Void Ratio Variation in the Northern Modern Yellow River Subaqueous Delta, China. Journal of Ocean University of China. 2018(03): 545-554 . 必应学术
    38. 李达，邓喀中，高晓雄，牛海鹏. 基于SBAS-InSAR的矿区地表沉降监测与分析. 武汉大学学报(信息科学版). 2018(10): 1531-1537 . 百度学术
    39. 张炜，张伟胜，张东升，胡文敏，孙毓言，唐佳佳. 采动覆岩活动规律的“空-地”监测技术. 中国矿业大学学报. 2018(06): 1212-1223 . 百度学术
    40. 王小侣. 水电站大坝400V备自投改造研究. 河南科技. 2018(19): 90-91 . 百度学术
    41. 张磊，杨帆，李超飞，赵增鹏，张子文. 宁波地面沉降的短基线集监测与分析. 测绘科学. 2017(12): 77-82 . 百度学术
    42. 陈继伟，曾琪明，焦健，赵斌臣. Sentinel-1A卫星TOPS模式数据的SBAS时序分析方法——以黄河三角洲地区为例. 国土资源遥感. 2017(04): 82-87 . 百度学术
    43. 王萍. 沉降观测技术在高层建筑施工中的应用. 建材与装饰. 2017(35): 19-20 . 百度学术
    44. 史秀保，徐宁，温浩，李春进. 一种小基线地表形变监测精度评价方法. 测绘通报. 2016(08): 70-73+91 . 百度学术
    45. 于丹，杨子玉，庄岩，于均园. 时序分析法在沈阳地铁二号线变形预测的应用. 沈阳建筑大学学报(自然科学版). 2016(03): 453-458 . 百度学术
    46. 王霖郁，李辉. 一种枝切法和质量图相结合的InSAR相位解缠算法. 应用科技. 2016(05): 49-53 . 百度学术

    其他类型引用(25)

    • 资源附件(0)
计量
  • 文章访问数:  2227
  • HTML全文浏览量:  85
  • PDF下载量:  1888
  • 被引次数: 71
出版历程
  • 收稿日期:  2014-07-08
  • 发布日期:  2016-02-04

目录

摘要
HTML全文
    参考文献(23)
    相关文章
    施引文献(71)
    资源附件(0)

    /

    返回文章
    返回

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

    地址：武汉大学文理学部本科生院楼北5楼邮政编码：430072

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

    我要投稿

    投稿攻略

    联系我们

    二维码

    本系统由北京仁和汇智信息技术有限公司开发  百度统计