留言板

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

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

基于多层次QTM的球面Voronoi图生成算法

王磊 赵学胜 赵龙飞 殷楠

王磊, 赵学胜, 赵龙飞, 殷楠. 基于多层次QTM的球面Voronoi图生成算法[J]. 武汉大学学报 ● 信息科学版, 2015, 40(8): 1111-1115. doi: 10.13203/j.whugis20140381
引用本文: 王磊, 赵学胜, 赵龙飞, 殷楠. 基于多层次QTM的球面Voronoi图生成算法[J]. 武汉大学学报 ● 信息科学版, 2015, 40(8): 1111-1115. doi: 10.13203/j.whugis20140381
WANG Lei, ZHAO Xuesheng, ZHAO Longfei, YIN Nan. Multi-level QTM Based Algorithm for Generating Spherical Voronoi Diagram[J]. Geomatics and Information Science of Wuhan University, 2015, 40(8): 1111-1115. doi: 10.13203/j.whugis20140381
Citation: WANG Lei, ZHAO Xuesheng, ZHAO Longfei, YIN Nan. Multi-level QTM Based Algorithm for Generating Spherical Voronoi Diagram[J]. Geomatics and Information Science of Wuhan University, 2015, 40(8): 1111-1115. doi: 10.13203/j.whugis20140381

基于多层次QTM的球面Voronoi图生成算法

doi: 10.13203/j.whugis20140381
基金项目: 国家自然科学基金资助项目(41171306;41171304)
详细信息
    作者简介:

    王磊,博士生,研究方向为全球离散格网与球面Voronoi图。

  • 中图分类号: P208

Multi-level QTM Based Algorithm for Generating Spherical Voronoi Diagram

Funds: The National Natural Science Foundation of China,Nos.41171306,41171304.
More Information
    Author Bio:

    WANG Lei,PhD candidate,specializes in Global Discrete Grid and spherical Voronoi diagram.

  • 摘要: 随着格网层次的增大,基于全球离散格网的球面Voronoi图生成算法的格网数据量与Voronoi图生成时间都呈指数增长,在高层次时容易出现算法效率较低,甚至内存溢出无法执行等情况。利用球面四元三角格网的层次性,提出了一个基于多层次QTM的球面Voronoi图生成算法。首先用全球低层次QTM格网生成Voronoi图,然后对Voronoi边界格网进行再次剖分,得到下一层次的Voronoi图,重复进行,直至达到目标层次。实验结果表明,相对于单一层次的确定归属算法和扩张算法,该算法能够生成更高层次的Voronoi图,且效率较前两者分别提高了22倍和25倍(第9层)。
  • [1] Yan Haowen,Wang Bangsong.A MWVD-basedAlgorithm for Point Cluster Generation[J].Geo-matics and Information Science of Wuhan Univer-sity,2013,38(9):1 088-1 091(闫浩文,王邦松.地图点群综合的加权 Voronoi算法[J].武汉大学学报·信息科学版,2013,38(9):1 088-1 091)[2] Wang Zhonghui,Yan Haowen.Computation of Di-rection Relations Between Object Groups Based onDirection Voronoi Diagram Model[J].Geomaticsand Information Science of Wuhan University,2013,38(5):584-588(王中辉,闫浩文.基于方向Voronoi图模型的群组目空间方向关系计算[J].武汉大学学报·信息科学版,2013,38(5):584-588) 第40卷第8期王 磊等:基于多层次QTM的球面Voronoi图生成算法1115[3] Hu Wei,Tao Weidong,Yuan Zhenyu,et al.AMethod of Vectorization of Scanning Map Based onVoronoi Diagrams[J].Geomatics and InformationScience of Wuhan University,2013,38(4):470-474(胡玮,陶伟东,苑振宇,等.一种Voronoi图的扫描地图矢量化方法[J].武汉大学学报·信息科学版,2013,38(4):470-474)[4] Chen J,Zhao X,Li Z.An Algorithm for the Gener-ation of Voronoi Diagrams on the Sphere Based onQTM[J].Photogrammetric Engineering &RemoteSensing,2003,69(1):79-89[5] Augenbaum J M,Peskin C S.On the Constructionof the Voronoi Mesh on a Sphere[J].Journal ofComputational Physics,1985,59(2):177-192[6] Robert J,Renka R.Delaunay Triangulation andVoronoi Diagram on the Surface of a Sphere[J].ACM Transactions on Mathematical Software,1997,23(3):416-434[7] Ma Y,Chen Q.Fast Delaunay Triangulation andVoronoi Diagram Generation on the Sphere[C].TheSecond World Congress on Software Engineering,Wuhan,China,2010[8] Dinis J,Mamede M.Sweeping the Sphere[C].2010International Symposium on Voronoi Diagramsin Science and Engineering,Quebec,Canada,2010[9] Hyeon-Suk N,Chung-Nim L,Otfried C.VoronoiDiagrams on the Sphere[J].Computation Geome-try:Theory and Applications,2002,23(2):183-194[10] Christopher G,Mir A M.Towards the Global GIS[J].ISPRS Journal of Photogrammetry &Re-mote Sensing,2000,55(3):150-163[11] Yang W,Christopher G.Managing Spatial Objectswith the VMO-Tree[C].The 7th InternationalSymposium on Spatial Data Handling,Netherlands,1996[12] Tong Xiaochong,Ben Jin,Zhang Yongsheng.TheGeneration Algorithm for Spherical Voronoi Dia-gram of Different Aggregation[J].Acta Geodaeticaet Cartographica Sinica,2006,35(1):83-89(童晓冲,贲进,张永生.不同集合的球面矢量 Voronoi图生成算法[J].测绘学报,2006,35(1):83-89)[13] Zhao Xuesheng.Spherical Voronoi Data ModelBased on QTM [M].Beijing:Surveying and Map-ping Press,2004(赵学胜.基于 QTM 的球面Voronoi数据模型[M].北京:测绘出版社,2004)[14]Ben Jin,Tong Xiaochong,Zhang Heng,et al.ASpherical Voronoi Algorithm Based on HexagonalGrid[J].Journal of Zhengzhou Institute of Sur-veying and Mapping,2006,23(5):328-330(贲进,童晓冲,张衡,等.基于球面六边形格网的球面Voronoi图生成算法[J].测绘科学技术学报,2006,23(5):328-330)[15] Tong Xiaochong,Ben Jin,Zhang Yongsheng.Ex-pression of Spherical Entities and Generation ofVoronoi Diagram Based on Truncated IcosahedronDGG[J].Geomatics and Information Science ofWuhan University,2006,31(11):966-970(童晓冲,贲进,张永生.基于二十面体剖分格网的球面实体表达与Voronoi图生成[J].武汉大学学报· 信息科学版,2006,31(11):966-970)[16] Dutton G.Modeling Locational Uncertainty via Hi-erarchical Tessellation[M].London:Taylor &Francis,1989[17] Sun Wenbin,Zhao Xuesheng.A Hierarchical Seam-less Model of Spatial Data Based on QTM [J].Journal of China University of Mining &Tech-nology,2008,37(5):675-679(孙文彬,赵学胜.基于QTM的空间数据无缝层次建模[J].中国矿业大学学报,2008,37(5):675-679)[18] Goodchild M F,Yang S,Dutton G.Spatial DataRepresentation and Basic Operations for a Triangu-lar Hierarchical Data Structure[P].US:NationalCenter for Geographic Information and Analysis,1991[19] Sun Wenbin,Zhao Xuesheng.Algorithm of Neigh-bor Finding on Sphere Triangular Meshes with Qua-ternary Code[J].Geomatics and Information Sci-ence of Wuhan University,2007,32(4):350-352(孙文彬,赵学胜.球面Quaternary编码的球面三角格网邻近搜索算法[J].武汉大学学报·信息科学版,2007,32(4):350-352)[20] Wang Lei,Zhao Xuesheng,Cao Wenmin,et al.AGPU-Based Algorithm for the Generation of SphericalVoronoi Diagram in QTM Mode[C].ISPRS WebMGS2013 &DMGIS 2013,Xuzhou,China,2013
  • [1] 王谦, 赵学胜, 王政, 刘青平.  一种改进的QTM地址码与经纬度坐标转换算法 . 武汉大学学报 ● 信息科学版, 2020, 45(2): 303-308, 316. doi: 10.13203/j.whugis20170390
    [2] 王政, 赵学胜, 罗富丽, 李亚路, 孙中昶.  球面三角格网单元面积的分形计算 . 武汉大学学报 ● 信息科学版, 2020, 45(10): 1541-1546. doi: 10.13203/j.whugis20180478
    [3] 张秀红, 陈迪, 刘纪平, 郭庆胜.  结构化居民地群的多层次识别方法 . 武汉大学学报 ● 信息科学版, 2018, 43(8): 1144-1151. doi: 10.13203/j.whugis20160239
    [4] 赵龙飞, 赵学胜, 朱思坤, 付瑞全.  一种球面退化四叉树格网的多层次邻近搜索算法 . 武汉大学学报 ● 信息科学版, 2018, 43(4): 529-535. doi: 10.13203/j.whugis20150611
    [5] 王磊, 赵学胜, 官亚勤, 赵龙飞.  QTM格网空间中的球面Voronoi图并行生成算法 . 武汉大学学报 ● 信息科学版, 2017, 42(5): 691-696. doi: 10.13203/j.whugis20140910
    [6] 孙文彬, 周长江.  一种近似等积球面菱形格网的构建方法 . 武汉大学学报 ● 信息科学版, 2016, 41(8): 1040-1045. doi: 10.13203/j.whugis20140397
    [7] 王金鑫, 禄丰年, 郭同德, 陈 杰.  球体大圆弧QTM八叉树剖分 . 武汉大学学报 ● 信息科学版, 2013, 38(3): 344-348.
    [8] 侯妙乐, 邢华桥, 赵学胜, 陈军.  球面四元三角网的复杂拓扑关系计算 . 武汉大学学报 ● 信息科学版, 2012, 37(4): 468-471.
    [9] 罗广祥, 刘苗, 樊鸿宇, 杨芳.  全球等面积四叉树离散格网建模与编码体系研究 . 武汉大学学报 ● 信息科学版, 2012, 37(10): 1252-1255.
    [10] 周东波, 朱庆, 杜志强, 张叶廷.  粒度与结构统一的多层次三维城市模型数据组织方法 . 武汉大学学报 ● 信息科学版, 2011, 36(12): 1406-1409.
    [11] 朱庆, 胡明远, 黄丽慧.  基于多层次事件的三维房产动态表示 . 武汉大学学报 ● 信息科学版, 2009, 34(3): 326-330.
    [12] 赵学胜, 崔马军, 李昂, 张美娟.  球面退化四叉树格网单元的邻近搜索算法 . 武汉大学学报 ● 信息科学版, 2009, 34(4): 479-482.
    [13] 侯妙乐, 赵学胜, 陈军.  球面四元三角网的三拓扑数计算 . 武汉大学学报 ● 信息科学版, 2008, 33(1): 60-63.
    [14] 万晓霞, 吴汉颖, 甘朝华.  基于多层次误差扩散加网的数字水印算法研究 . 武汉大学学报 ● 信息科学版, 2007, 32(11): 1056-1059.
    [15] 黄正东, 于卓, 汪斌.  一种面向对象的多层次公交数据模型 . 武汉大学学报 ● 信息科学版, 2007, 32(4): 358-361.
    [16] 孙文彬, 赵学胜.  基于Quaternary编码的球面三角格网邻近搜索算法 . 武汉大学学报 ● 信息科学版, 2007, 32(4): 350-352.
    [17] 阎平, 江万寿.  DSM数据中多层次、多直角房屋的三维重建 . 武汉大学学报 ● 信息科学版, 2006, 31(6): 492-495.
    [18] 侯妙乐, 赵学胜, 陈军.  球面栅格空间中的Jordan曲线性质及其拓扑矛盾分析 . 武汉大学学报 ● 信息科学版, 2006, 31(2): 148-151.
    [19] 白建军, 赵学胜, 陈军.  基于线性四叉树的全球离散格网索引 . 武汉大学学报 ● 信息科学版, 2005, 30(9): 805-808.
    [20] 周建彬, 贲进, 王蕊, 郑明阳.  四孔六边形全球离散格网一致瓦片层次结构编码运算 . 武汉大学学报 ● 信息科学版, 0, 0(0): 0-0. doi: 10.13203/j.whugis20200530
  • 加载中
计量
  • 文章访问数:  1052
  • HTML全文浏览量:  25
  • PDF下载量:  457
  • 被引次数: 0
出版历程
  • 收稿日期:  2014-05-13
  • 修回日期:  2015-08-05
  • 刊出日期:  2015-08-05

基于多层次QTM的球面Voronoi图生成算法

doi: 10.13203/j.whugis20140381
    基金项目:  国家自然科学基金资助项目(41171306;41171304)
    作者简介:

    王磊,博士生,研究方向为全球离散格网与球面Voronoi图。

  • 中图分类号: P208

摘要: 随着格网层次的增大,基于全球离散格网的球面Voronoi图生成算法的格网数据量与Voronoi图生成时间都呈指数增长,在高层次时容易出现算法效率较低,甚至内存溢出无法执行等情况。利用球面四元三角格网的层次性,提出了一个基于多层次QTM的球面Voronoi图生成算法。首先用全球低层次QTM格网生成Voronoi图,然后对Voronoi边界格网进行再次剖分,得到下一层次的Voronoi图,重复进行,直至达到目标层次。实验结果表明,相对于单一层次的确定归属算法和扩张算法,该算法能够生成更高层次的Voronoi图,且效率较前两者分别提高了22倍和25倍(第9层)。

English Abstract

王磊, 赵学胜, 赵龙飞, 殷楠. 基于多层次QTM的球面Voronoi图生成算法[J]. 武汉大学学报 ● 信息科学版, 2015, 40(8): 1111-1115. doi: 10.13203/j.whugis20140381
引用本文: 王磊, 赵学胜, 赵龙飞, 殷楠. 基于多层次QTM的球面Voronoi图生成算法[J]. 武汉大学学报 ● 信息科学版, 2015, 40(8): 1111-1115. doi: 10.13203/j.whugis20140381
WANG Lei, ZHAO Xuesheng, ZHAO Longfei, YIN Nan. Multi-level QTM Based Algorithm for Generating Spherical Voronoi Diagram[J]. Geomatics and Information Science of Wuhan University, 2015, 40(8): 1111-1115. doi: 10.13203/j.whugis20140381
Citation: WANG Lei, ZHAO Xuesheng, ZHAO Longfei, YIN Nan. Multi-level QTM Based Algorithm for Generating Spherical Voronoi Diagram[J]. Geomatics and Information Science of Wuhan University, 2015, 40(8): 1111-1115. doi: 10.13203/j.whugis20140381
参考文献 (1)

目录

    /

    返回文章
    返回