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

doi:10.13474/j.cnki.11-2246.2018.0075

Abstract

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

CLC Number:

P208

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

References

[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.