留言板

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

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

线/面Voronoi图的分解合并生成算法

李佳田 杨琪莉 罗富丽 罗辉兰 林艳

李佳田, 杨琪莉, 罗富丽, 罗辉兰, 林艳. 线/面Voronoi图的分解合并生成算法[J]. 武汉大学学报 ● 信息科学版, 2015, 40(11): 1545-1550. doi: 10.13203/j.whugis20140018
引用本文: 李佳田, 杨琪莉, 罗富丽, 罗辉兰, 林艳. 线/面Voronoi图的分解合并生成算法[J]. 武汉大学学报 ● 信息科学版, 2015, 40(11): 1545-1550. doi: 10.13203/j.whugis20140018
LI Jiatian, YANG Qili, LUO Fuli, LUO Huilan, LIN Yan. A Decomposition and Combination Algorithm for Voronoi Diagrams of Polylines and Polygons[J]. Geomatics and Information Science of Wuhan University, 2015, 40(11): 1545-1550. doi: 10.13203/j.whugis20140018
Citation: LI Jiatian, YANG Qili, LUO Fuli, LUO Huilan, LIN Yan. A Decomposition and Combination Algorithm for Voronoi Diagrams of Polylines and Polygons[J]. Geomatics and Information Science of Wuhan University, 2015, 40(11): 1545-1550. doi: 10.13203/j.whugis20140018

线/面Voronoi图的分解合并生成算法

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

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

  • 中图分类号: P208

A Decomposition and Combination Algorithm for Voronoi Diagrams of Polylines and Polygons

Funds: The National Natural Science Foundation of China, Nos. 41161061, 40901197.
  • 摘要: Voronoi图生成算法受到计算效率或生长源类型的限制,难以支撑线/面生长源Voronoi图的构建。本文提出一种生成线/面生长源Voronoi图的分解合并算法,其主要过程是将线/面生长源离散为特征点表达,通过特征点交叉建立最近特征点对,并以最近特征点对Voronoi子区域的交来部分地代替线/面生长源的等距离边界,算法以前后迭代离散计算的Voronoi子区域面积差分作为条件,可有选择地将部分生长源置入迭代过程,使线/面生长源Voronoi子区域逐步调整并达到精度要求。
  • [1] Gold C. Review: Spatial Tessellation-Concepts and Applications of Voronoi Diagrams [J]. International Journal of Geographical Information Science, 1994, 8(2): 237-238
    [2] Okabe A, Boots B,Sugihare K, et al. Spatial tessellations: Concepts nd Applications of Voronoi Diagrams [M]. New York: Wiley, 2000
    [3] Chen Jun. Voronoi-based Dynamic Spatial Data Model [M]. Beijing: Publishing House of Surveying and Mapping, 2002(陈军. Voronoi动态空间数据模型[M]. 北京: 测绘出版社, 2002)
    [4] Yan Haowen, Wang Bangsong. A MWVD-based Algorithm for Point Cluster Generalization [J]. Geomatics and Information Science of Wuhan Univers, 2013, 38(9): 1 088-1 091 (闫浩文, 王邦松. 地图点群综合的加权Voronoi算法[J]. 武汉大学学报·信息科学版, 2013, 38(9): 1 088-1 091)
    [5] 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 Univers, 2012, 37(8): 1 000-1 003 (沈晶, 刘纪平, 林祥国, 等. 集成距离变换和区域邻接图生成Delaunay三角网的方法研究[J]. 武汉大学学报·信息科学版, 2012, 37(8): 1 000-1 003)
    [6] 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)
    [7] 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)
    [8] Zhao Renliang. Voronoi Methods for Computing Spatial Relations in GIS [M]. Beijing: Publishing House of Surveying and Mapping, 2006 (赵仁亮. 基于Voronoi图的GIS空间关系计算[M]. 北京: 测绘出版社, 2006)
    [9] Schueller A. A Nearest Neighbor Sweep Circle Algorithm for Computing Discrete Voronoi Tessellations [J]. Journal of Mathematical Analysis and Applications, 2007, 336(2): 1 018-1 025
    [10] Dong Pinliang. Generating and Updating Multiplicatively Weighted Voronoi Diagrams for Point, Line and Polygon Features in GIS [J]. Computer & Geosciences, 2008, 34(4): 411-421
    [11] Guibas L, Stolfi J. Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams [J]. ACM Transactions on Graphics, 1985, 4(2): 74-123
    [12] Imai T, Sugihara K. A Failure-Free Algorithm for Constructing Voronoi Diagrams of Line Segments [J]. Information Processing Society of Japan, 1994, 35(10): 1 966-1 977
    [13] Held M, Huber S. Topology-Oriented Incremental Computation of Voronoi Diagrams of Circular Arcs and Straight-Line Segments [J]. Computer-Aided Design, 2009, 41(5): 327-338
    [14] Hu Peng, You Lian, Yang Chuanyong, et al. Map Algebra [M]. Wuhan: Wuhan University Press, 2006 (胡鹏, 游涟, 杨传勇, 等. 地图代数[M]. 武汉: 武汉大学出版社, 2006)
  • [1] 李欣, 杨宇辉, 杨博, 尹峰.  利用方向相位特征进行多源遥感影像匹配 . 武汉大学学报 ● 信息科学版, 2020, 45(4): 488-494. doi: 10.13203/j.whugis20180445
    [2] 纪松, 张永生, 范大昭, 龚志辉.  基于特征点引导的多视影像择优匹配方法 . 武汉大学学报 ● 信息科学版, 2018, 43(1): 37-45. doi: 10.13203/j.whugis20150458
    [3] 胡学敏, 郑宏, 郭琳, 熊饶饶.  利用鱼眼相机对人群进行运动估计 . 武汉大学学报 ● 信息科学版, 2017, 42(4): 537-542. doi: 10.13203/j.whugis20150090
    [4] 卢学良, 童晓冲, 张永生, 谢金华, 于英.  城市密集点云的区域生长表面构网改进算法 . 武汉大学学报 ● 信息科学版, 2016, 41(6): 832-837. doi: 10.13203/j.whugis20140443
    [5] 李佳田, 罗富丽, 余莉, 张蓝, 康顺, 林艳.  梯度Voronoi图及其构建算法 . 武汉大学学报 ● 信息科学版, 2016, 41(2): 163-170. doi: 10.13203/j.whugis20140025
    [6] 许雪梅, 周立超, 杨兵初, 李梦平, 李丽娴, 尹林子, 丁一鹏.  CIFO:针对显著对象的彩色图像检索方法 . 武汉大学学报 ● 信息科学版, 2015, 40(1): 53-58.
    [7] 应 申, 毛政元, 李 霖, 许 光.  利用3D Voronoi图的兔子点云聚类分割 . 武汉大学学报 ● 信息科学版, 2013, 38(3): 358-361.
    [8] 邹亚锋, 刘耀林, 孔雪松, 范登科.  加权Voronoi图在农村居民点布局优化中的应用研究 . 武汉大学学报 ● 信息科学版, 2012, 37(5): 560-563.
    [9] 孙殿柱, 刘健, 李延瑞, 孙永伟.  三维散乱点云的Voronoi拓扑近邻点集查询算法 . 武汉大学学报 ● 信息科学版, 2011, 36(1): 86-91.
    [10] 李芳芳, 贾永红, 肖本林, 张谦.  利用线特征和SIFT点特征进行多源遥感影像配准 . 武汉大学学报 ● 信息科学版, 2010, 35(2): 233-236.
    [11] 孙殿柱, 刘健, 李延瑞, 李心成.  三维散乱点集Voronoi图快速生成算法研究 . 武汉大学学报 ● 信息科学版, 2010, 35(8): 909-912.
    [12] 江南, 白小双, 曹亚妮, 王驹.  基础电子地图多尺度显示模型的建立与应用 . 武汉大学学报 ● 信息科学版, 2010, 35(7): 768-772.
    [13] 闫超德, 白建军, 赵仁亮.  基于Voronoi图的点状目标邻近空间分布测度方法 . 武汉大学学报 ● 信息科学版, 2009, 34(1): 48-51.
    [14] 朱庆, 李逢春, 张叶廷.  一种改进的三维点集表面重建的区域生长算法 . 武汉大学学报 ● 信息科学版, 2006, 31(8): 667-670.
    [15] 于子凡, 林宗坚.  基于图像表面积的分形布朗运动分数维算法研究 . 武汉大学学报 ● 信息科学版, 2005, 30(2): 161-165.
    [16] 黄培之, 刘泽慧.  基于地形梯度方向的山脊线和山谷线的提取 . 武汉大学学报 ● 信息科学版, 2005, 30(5): 396-399.
    [17] 张鹏林, 关泽群, 王新洲.  时间序列影像特征点提取与匹配算法研究 . 武汉大学学报 ● 信息科学版, 2004, 29(4): 329-332.
    [18] 黄培之.  提取山脊线和山谷线的一种新方法 . 武汉大学学报 ● 信息科学版, 2001, 26(3): 247-252.
    [19] 李成名, 陈军.  Voronoi图生成的栅格算法 . 武汉大学学报 ● 信息科学版, 1998, 23(3): 208-210.
    [20] 秦宏楠, 马海涛, 于正兴, 刘玉溪.  地基雷达干涉测量动态高频次数据用于滑坡早期预警方法研究 . 武汉大学学报 ● 信息科学版, 0, 0(0): -. doi: 10.13203/j.whugis20220152
  • 加载中
计量
  • 文章访问数:  2014
  • HTML全文浏览量:  69
  • PDF下载量:  1524
  • 被引次数: 0
出版历程
  • 收稿日期:  2014-01-06
  • 刊出日期:  2015-11-05

线/面Voronoi图的分解合并生成算法

doi: 10.13203/j.whugis20140018
    基金项目:  国家自然科学基金资助项目(41161061,40901197)。
    作者简介:

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

  • 中图分类号: P208

摘要: Voronoi图生成算法受到计算效率或生长源类型的限制,难以支撑线/面生长源Voronoi图的构建。本文提出一种生成线/面生长源Voronoi图的分解合并算法,其主要过程是将线/面生长源离散为特征点表达,通过特征点交叉建立最近特征点对,并以最近特征点对Voronoi子区域的交来部分地代替线/面生长源的等距离边界,算法以前后迭代离散计算的Voronoi子区域面积差分作为条件,可有选择地将部分生长源置入迭代过程,使线/面生长源Voronoi子区域逐步调整并达到精度要求。

English Abstract

李佳田, 杨琪莉, 罗富丽, 罗辉兰, 林艳. 线/面Voronoi图的分解合并生成算法[J]. 武汉大学学报 ● 信息科学版, 2015, 40(11): 1545-1550. doi: 10.13203/j.whugis20140018
引用本文: 李佳田, 杨琪莉, 罗富丽, 罗辉兰, 林艳. 线/面Voronoi图的分解合并生成算法[J]. 武汉大学学报 ● 信息科学版, 2015, 40(11): 1545-1550. doi: 10.13203/j.whugis20140018
LI Jiatian, YANG Qili, LUO Fuli, LUO Huilan, LIN Yan. A Decomposition and Combination Algorithm for Voronoi Diagrams of Polylines and Polygons[J]. Geomatics and Information Science of Wuhan University, 2015, 40(11): 1545-1550. doi: 10.13203/j.whugis20140018
Citation: LI Jiatian, YANG Qili, LUO Fuli, LUO Huilan, LIN Yan. A Decomposition and Combination Algorithm for Voronoi Diagrams of Polylines and Polygons[J]. Geomatics and Information Science of Wuhan University, 2015, 40(11): 1545-1550. doi: 10.13203/j.whugis20140018
参考文献 (14)

目录

    /

    返回文章
    返回