面向雷利法则的加权Voronoi图生成方法

doi:10.13474/j.cnki.11-2246.2018.0075

测绘通报 ›› 2018, Vol. 0 ›› Issue (3): 55-59,70.doi: 10.13474/j.cnki.11-2246.2018.0075

面向雷利法则的加权Voronoi图生成方法

康顺¹, 瞿珊珊²

1. 中国矿业大学(北京)地球科学与测绘工程学院, 北京 100083;
2. 中南大学地球科学与信息物理学院, 湖南长沙 410083

收稿日期:2017-06-20 出版日期:2018-03-25 发布日期:2018-04-03
作者简介:康顺(1987-),男,博士生,主要从事Voronoi空间建模与计算研究。E-mail:kangshun1987@163.com
基金资助:
国家自然科学基金（41161061）

A Generating Method for Weighted Voronoi Diagram Based on Reilly's Law

KANG Shun¹, QU Shanshan²

1. College of Geoscience and Surveying Engineering, China University of Mining and Technology(Beijing), Beijing 100083, China;
2. School of Geosciences and Info-physics, Central South University, Changsha 410083, China

Received:2017-06-20 Online:2018-03-25 Published:2018-04-03

摘要/Abstract

摘要：

Voronoi图及其生成是计算几何的重要内容。针对传统栅格加权Voronoi图的权重界定局限性，以及栅格数据下Voronoi图生成的计算效率问题，本文研究了基于雷利法则的生长元规模权重和栅格欧氏距离变换权重作为综合权重条件下，规避单图幅背景栅格与每一生长元之间的距离计算，根据生长元各自距离变换图幅构建栅格加权Voronoi图，即雷利Voronoi图（Reilly Voronoi diagram，RVD）的地图代数生成方法。经试验验证，该方法生成的Voronoi图不仅完善了传统的权重因素，而且避免了因背景栅格与生长元的距离运算、判断而产生的大量计算，证明了该方法的切实可行性。

关键词: Voronoi, 雷利法则, 规模权重, 距离变换权重, 地图代数

Abstract:

Voronoi diagram and its generation are quite important in computational geometry.As to the limitation of weight defined and the generating efficiency for raster-based Voronoi diagram,taking the comprehensive conditions of generating grid scale weight and raster distance transformation weight into consideration,from multi-distance map angle,a raster-based weighted Voronoi diagram,i.e.Reilly Voronoi diagram (RVD) is proposed by map algebra method based on Reilly's law of retail gravitation,by which it avoids the multi-computing between background grids and generating grids in single map.Through experiment verification,it has been proved to be a feasible way for generating raster-based Voronoi diagram meanwhile improve and perfect the traditional weight factor and need not multi-computing between background grids and generating cell to generate spatial Voronoi tessellations.

Key words: Voronoi, Reilly's law, scale weight, distance transform weight, map algebra

中图分类号:

P208

康顺, 瞿珊珊. 面向雷利法则的加权Voronoi图生成方法[J]. 测绘通报, 2018, 0(3): 55-59,70.

KANG Shun, QU Shanshan. A Generating Method for Weighted Voronoi Diagram Based on Reilly's Law[J]. 测绘通报, 2018, 0(3): 55-59,70.

参考文献

[1] DESCARTES R,MILLER V R,MILLER R P.Principles of Philosophy[M].Boston:[s.n.],1908.
[2] VORONOI G.Nouvelles Applications des Paramètres Continusàla Théorie des Formes Quadratiques[J].Journal für die Reine und Angewandte Mathematik,1908(134):198-287.
[3] 刘金义,刘爽.Voronoi图应用综述[J].图学学报,2004,25(2):125-132.
[4] 康顺,相诗尧.基于马氏距离的多高斯Voronoi图生成方法[J].地理与地理信息科学,2016,32(3):49-52.
[5] 李佳田,杨琪莉,罗富丽,等.线/面Voronoi图的分解合并生成算法[J].武汉大学学报(信息科学版),2015,40(11):1545-1550.
[6] 王新生,刘纪远,庄大方,等.基于GIS的任意发生元Voronoi图逼近方法[J].地理科学进展,2004,23(4):97-102.
[7] 刘宝举,刘慧敏,邓敏,等.一种基于栅格的加权Voronoi图构建普适方法[J].地理与地理信息科学,2016,32(4):17-22.
[8] DONG P.Generating and Updating Multiplicatively Weighted Voronoi Diagrams for Point,Line and Polygon Features in GIS[J].Computers & Geosciences,2008,34(4):411-421.
[9] BAREQUET G,DICKERSON M T,SCOT R L.2-Point Site Voronoi Diagrams[J].Discrete Applied Mathematics,2002,122(1):37-54.
[10] LI C,CHEN J,LI Z.A Raster-based Method for Computing Voronoi Diagrams of Spatial Objects Using Dynamic Distance Transformation[J].International Journal of Geographical Information Science,1999,13(3):209-225.
[11] 李佳田,陈军,赵仁亮,等.基于线性四叉树结构的Voronoi图反向膨胀生成方法[J].测绘学报,2008,37(2):236-242.
[12] 寿华好,袁子薇,缪永伟,等.一种平面点集Voronoi图的细分算法[J].图学学报,2013,34(2):1-6.
[13] 王新生,刘纪远,庄大方,等.一种新的构建Voronoi图的栅格方法[J].中国矿业大学学报,2003,32(3):293-296.
[14] 王结臣,蒲英霞,崔璨,等.一种基于点集自适应分组构建Voronoi图的并行算法[J].图学学报,2012,33(6):7-13.
[15] LEE I,PERSHOUSE R,LEE K.Geospatial Cluster Tessellation Through the Complete Order-k Voronoi Diagrams[C]//International Conference on Spatial Information Theory.[S.l.]:Springer-Verlag,2007:321-336.
[16] 兰连意,张有会,杨玉平.一般城市Voronoi图的结晶生成[J].计算机工程与应用,2010(10):216-219.
[17] 涂伟,李清泉,方志祥.基于网络Voronoi图的大规模多仓库物流配送路径优化[J].测绘学报,2014,43(10):1075-1082.
[18] 佘冰,叶信岳,房会会,等.基于局部聚类的网络Voronoi图生成方法研究[J].地理科学,2015,35(5):637-643.
[19] ASANO T.Aspect-ratio Voronoi Diagram with Applications[C]//International Symposium on Voronoi Diagrams in Science and Engineering.[S.l.]:IEEE,2006:32-39.
[20] ASANO T,TAMAKI H.Angular Voronoi Diagram with Applications[C]//International Symposium on Voronoi Diagrams in Science and Engineering.Banff,Canada:[s.n.],2006:18-24.
[21] REILLY W J.The Law of Retail Gravitation[M].New York:Knickerbocker Press,1931.
[22] 胡鹏,杨传勇,胡海,等.GIS的基本理论问题-地图代数的空间观[J].武汉大学学报(信息科学版),2002,27(6):616-621.

面向雷利法则的加权Voronoi图生成方法

A Generating Method for Weighted Voronoi Diagram Based on Reilly's Law

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

本文评价

[1]	赵佳星, 吕伟才, 葛祥, 陈卫卫. 基于加权Voronoi图评价安徽省城市空间吸引力影响范围[J]. 测绘通报, 2020, 0(4): 125-129.
[2]	陈松, 周平, 李显巨, 陈刚. 基于Voronoi图的正射影像镶嵌网络生成与优化方法[J]. 测绘通报, 2019, 0(6): 57-60,84.
[3]	陆晓蕙, 梁勇, 燕琴, 刘正军. 城市开发区土地集约利用评价——以武汉市为例[J]. 测绘通报, 2018, 0(3): 71-75,88.
[4]	赵庶旭, 屈睿涛, 刘昌荣. 一种基于轨迹特征划分的交通轨迹数据分析方法[J]. 测绘通报, 2018, 0(11): 73-77,82.
[5]	王海涛, 张丹, 张娜. Voronoi图在无人机航空影像匹配中的应用[J]. 测绘通报, 2017, 0(11): 118-122,127.
[6]	李佳, 段平, 梁明, 吕海洋. 地理多要素Voronoi图相邻关系下的地图放大裁剪方法[J]. 测绘通报, 2017, 0(10): 84-88.
[7]	王圣尧刘善磊石善球王光辉. 遥感影像GCP选取方法研究[J]. 测绘通报, 2014, 0(6): 55-59.
[8]	张建辉付瑞全. 基于GIS的海洋划界技术方法研究[J]. 测绘通报, 2013, 0(10): 115-118.