留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

梯度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
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

梯度Voronoi图及其构建算法

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

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

  • 中图分类号: P208

The Gradient Voronoi Diagram and Construction Algorithm

Funds: The National Natural Science Foundation of China, Nos. 41561082, 41161061, 41301416.
  • 摘要: 以生长速度为视角,普通Voronoi图及权重Voronoi图是理想欧氏平面上的生长元匀速生长结果。然而,以Voronoi图为基础的实际分析与建模情况不尽如此,通常表现为非理想平面的非匀速生长过程。本文以权重距离函数描述各向异性的非理想平面,以其时间消耗导数一致性形式化生长速度,定义一种新的Voronoi图——梯度Voronoi图。通过以高程变化诱发的梯度生长为例,借助栅格空间中形态学膨胀操作,给出梯度Voronoi图的典型构建算法。算例与分析表明,在等距离边界、势力范围与邻近关系表达方面,梯度Voronoi图更具优势。
  • [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
  • [1] 吴建华, 戴鹏, 胡烈云.  一种面向多尺度面状居民地匹配的Voronoi图自适应构建算法 . 武汉大学学报 ● 信息科学版, 2022, 47(2): 304-312. doi: 10.13203/j.whugis20200324
    [2] 李佳田, 吴华静, 高鹏, 贺日兴, 张文靖, 阿晓荟, 邓钢.  一种复合Voronoi几何特征的地标提取新方法 . 武汉大学学报 ● 信息科学版, 2020, 45(9): 1448-1454. doi: 10.13203/j.whugis20180125
    [3] 王邦松, 张继贤, 卢丽君, 黄国满, 赵争.  利用Voronoi图辅助星载干涉雷达配准 . 武汉大学学报 ● 信息科学版, 2016, 41(10): 1339-1343. doi: 10.13203/j.whugis20140549
    [4] 王新生, 谢凯, 姜友华, 郭光毅.  复杂多边形中轴构建方法! . 武汉大学学报 ● 信息科学版, 2014, 39(2): 181-185. doi: 10.13203/j.whugis20120715
    [5] 胡玮, 陶伟东, 苑振宇, 王结臣.  一种Voronoi图的扫描地图矢量化方法 . 武汉大学学报 ● 信息科学版, 2013, 38(4): 470-474.
    [6] 沈晶, 刘纪平, 林祥国, 赵荣.  集成距离变换和区域邻接图生成Delaunay三角网的方法研究 . 武汉大学学报 ● 信息科学版, 2012, 37(8): 1000-1003.
    [7] 付仲良, 刘思远.  MR-tree空间索引的Voronoi图改进及其并行空间查询方法 . 武汉大学学报 ● 信息科学版, 2012, 37(12): 1490-1494.
    [8] 王海军, 邓羽, 张文婷, 贺三维.  利用元胞自动机和遗传算法的Voronoi图生成 . 武汉大学学报 ● 信息科学版, 2010, 35(7): 778-781.
    [9] 邵振峰, 闫贝贝, 周杨.  基于模糊思想的改进Voronoi图模型 . 武汉大学学报 ● 信息科学版, 2009, 34(11): 1381-1385.
    [10] 潘俊, 王密, 李德仁.  基于顾及重叠的面Voronoi图的接缝线网络生成方法 . 武汉大学学报 ● 信息科学版, 2009, 34(5): 518-521.
    [11] 闫超德, 白建军, 赵仁亮.  基于Voronoi图的点状目标邻近空间分布测度方法 . 武汉大学学报 ● 信息科学版, 2009, 34(1): 48-51.
    [12] 李光强, 邓敏, 朱建军.  基于Voronoi图的空间关联规则挖掘方法研究 . 武汉大学学报 ● 信息科学版, 2008, 33(12): 1242-1245.
    [13] 闫超德, 赵仁亮, 陈军, 赵学胜.  Voronoi图的首最邻近递归收敛特性及其应用 . 武汉大学学报 ● 信息科学版, 2008, 33(11): 1194-1197.
    [14] 童晓冲, 贲进, 张永生.  基于二十面体剖分格网的球面实体表达与Voronoi图生成 . 武汉大学学报 ● 信息科学版, 2006, 31(11): 966-970.
    [15] 陈军, 赵仁亮, 乔朝飞.  基于Voronoi图的GIS空间分析研究 . 武汉大学学报 ● 信息科学版, 2003, 28(S1): 32-37.
    [16] 闫浩文, 郭仁忠.  基于Voronoi图的空间方向关系形式化描述模型 . 武汉大学学报 ● 信息科学版, 2003, 28(4): 468-471,479.
    [17] 闫浩文, 郭仁忠.  用Voronoi图描述空间方向关系的理论依据 . 武汉大学学报 ● 信息科学版, 2002, 27(3): 306-310.
    [18] 李成名, 陈军, 朱英浩.  基于Voronoi图的空间邻近定义与查询 . 武汉大学学报 ● 信息科学版, 1998, 23(2): 128-131.
    [19] 李成名, 陈军.  Voronoi图生成的栅格算法 . 武汉大学学报 ● 信息科学版, 1998, 23(3): 208-210.
    [20] 陈军, 崔秉良.  用Voronoi方法为MapInfo扩展拓扑功能 . 武汉大学学报 ● 信息科学版, 1997, 22(3): 195-200,211.
  • 加载中
计量
  • 文章访问数:  1827
  • HTML全文浏览量:  55
  • PDF下载量:  1861
  • 被引次数: 0
出版历程
  • 收稿日期:  2014-07-09
  • 刊出日期:  2016-02-05

梯度Voronoi图及其构建算法

doi: 10.13203/j.whugis20140025
    基金项目:  国家自然科学基金(41561082,41161061,41301416)。
    作者简介:

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

  • 中图分类号: P208

摘要: 以生长速度为视角,普通Voronoi图及权重Voronoi图是理想欧氏平面上的生长元匀速生长结果。然而,以Voronoi图为基础的实际分析与建模情况不尽如此,通常表现为非理想平面的非匀速生长过程。本文以权重距离函数描述各向异性的非理想平面,以其时间消耗导数一致性形式化生长速度,定义一种新的Voronoi图——梯度Voronoi图。通过以高程变化诱发的梯度生长为例,借助栅格空间中形态学膨胀操作,给出梯度Voronoi图的典型构建算法。算例与分析表明,在等距离边界、势力范围与邻近关系表达方面,梯度Voronoi图更具优势。

English Abstract

李佳田, 罗富丽, 余莉, 张蓝, 康顺, 林艳. 梯度Voronoi图及其构建算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(2): 163-170. doi: 10.13203/j.whugis20140025
引用本文: 李佳田, 罗富丽, 余莉, 张蓝, 康顺, 林艳. 梯度Voronoi图及其构建算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(2): 163-170. doi: 10.13203/j.whugis20140025
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
参考文献 (23)

目录

    /

    返回文章
    返回