Point cluster selection based on weighted network Voronoi diagram

doi:10.3785/j.issn.1008-973X.2019.03.019

Journal of ZheJiang University (Engineering Science)

2019, Vol. 53

Issue (3): 571-578 DOI: 10.3785/j.issn.1008-973X.2019.03.019

Computer Technology

Point cluster selection based on weighted network Voronoi diagram

Xiao-min LU1,2,3(

),Hao-wen YAN2,3,*(

),Lu KANG2,3,Fang WU4

1. School of Environment and Municipal Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China
2. Faculty of Geomatics, Lanzhou Jiaotong University, Lanzhou 730070, China
3. Gansu Provincial Engineering Laboratory for National Geographic State Monitoring, Lanzhou 730070, China
4. Institute of Geospatial Information, Information Engineering University, Zhengzhou 450000, China

Download:

HTML

PDF(1557KB) HTML
Export: BibTeX | EndNote (RIS)

Abstract

The existing algorithms based on Voronoi ignores the fact that points are connected through road network, in view of which, a new algorithm was proposed based on network weighted Voronoi diagram. Firstly, the weighted network Voronoi diagram of the point cluster was constructed based on expansion operation. Secondly, the area of the weighted network Voronoi polygon and the total length of the expansion route of each point were calculated, based on which the appropriate factors for describing the statistical, thematic, topological and metric information were selected. Thirdly, the method called ‘concentric circle’ was proposed and the point deletion was completed. The experimental results show that the algorithm takes into account the effect of the weight of the point, the level and the direction of the roads, and the density of the road network on the generalized results. The information of the original point cluster is transmitted well and the generalized results fit the actual geographic feature.

Key words： network weighted Voronoi diagram rasterization point cluster generalization dilation operation ‘concentric circle’ algorithm

Received: 19 May 2018 Published: 04 March 2019

CLC:

P 283

Corresponding Authors: Hao-wen YAN E-mail: xiaominlu08@gmail.com;haowen2010@gmail.com

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	Xiao-min LU
	Hao-wen YAN
	Lu KANG
	Fang WU

Cite this article:

Xiao-min LU,Hao-wen YAN,Lu KANG,Fang WU. Point cluster selection based on weighted network Voronoi diagram. Journal of ZheJiang University (Engineering Science), 2019, 53(3): 571-578.

URL:

http://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2019.03.019 OR http://www.zjujournals.com/eng/Y2019/V53/I3/571

基于网络加权Voronoi图的点群选取

传统基于Voronoi图的算法忽略了点与点之间是通过实际网络距离相连这一事实，针对此缺陷，提出一种基于网络加权Voronoi图的点群选取算法. 1）利用网络扩展法构建点群的网络加权Voronoi图；2）计算每个点对应的网络Voronoi多边形面积及扩展弧段总长度，并以此为依据，为点群中所包含的统计、专题、拓扑和度量信息分别选定量化描述因子；3）提出“同心圆”算法，解决点群取舍问题. 实验结果表明，提出的方法顾及了点群权重以及与点群相关联的道路等级、方向及局部密度对选取结果的影响，较好地保持了原始点群的各类信息，选取结果符合实际地理空间特征.

关键词： 网络加权Voronoi图, 栅格化, 点群选取, 扩展算法, “同心圆”算法

Fig.1 Flowchart of point cluster selection algorithm based on weighted network Voronoi diagram

Fig.2 Traditional raster model and network raster model

Fig.3 Rasterized results of source elements

Fig.4 Dilation operation of point cluster

Fig.5 Generation of weighted network Voronoi diagram

Fig.6 Weighted network Voronoi polygons and extended segments of point cluster

Fig.7 Method of ‘concentric quadrants’ in point deletion process

Fig.8 Experiment of point cluster selection based on weighted network Voronoi diagram

Fig.9 Experiment of point cluster selection based on multipcatively weighted Voronoi diagram (MWVD)

Tab.1 Indices used in the experiments for evaluating the new algorithm


[1]	李佳田, 康顺, 罗富丽利用层次Voronoi图进行点群综合[J]. 测绘学报, 2014, 43 (12): 1300- 1306 LI Jia-tian, KANG Shun, LUO Fu-li Point group generalization method on hierarchical Voronoi diagram[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43 (12): 1300- 1306

[2]	闫浩文, 王家耀基于Voronoi图的点群目标普适综合算法[J]. 中国图象图形学报, 2005, 10 (5): 633- 636 YAN Hao-wen, WANG Jia-yao A generic algorithm for point cluster generalization based on Voronoi diagrams[J]. Journal of Image and Graphics, 2005, 10 (5): 633- 636 doi: 10.3969/j.issn.1006-8961.2005.05.017

[3]	闫浩文, 王邦松地图点群综合的加权Voronoi算法[J]. 武汉大学学报: 信息科学版, 2013, 38 (9): 1088- 1090 YAN Hao-wen, WANG Bang-song A MWVD-based algorithm for point cluster generalization[J]. Geomatics and Information Science of Wuhan University, 2013, 38 (9): 1088- 1090

[4]	YAN H W, WEIBEL R An algorithm for point cluster generalization based on the Voronoi diagram[J]. Computers and GeoScience, 2008, 34 (8): 939- 954 doi: 10.1016/j.cageo.2007.07.008

[5]	蔡永香, 郭庆胜基于Kohonen网络的点群综合研究[J]. 武汉大学学报: 信息科学版, 2007, 32 (7): 626- 629 CAI Yong-xiang, GUO Qing-sheng Points group generalization based on Konhonen Net[J]. Geomatics and Information Science of Wuhan University, 2007, 32 (7): 626- 629

[6]	郭庆胜, 郑春燕, 胡华科基于邻近图的点群层次聚类方法的研究[J]. 测绘学报, 2008, 37 (2): 240- 249 GUO Qing-sheng, ZHENG Chun-yan, HU Hua-ke Hierarchical clustering method of group of points based on the neighborhood graph[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37 (2): 240- 249

[7]	李赟, 闫浩文, 刘正军两种地图点群综合算法的比较[J]. 测绘工程, 2015, 43- 47 LI Yun, YAN Hao-wen, LIU Zheng-jun Comparison of two point cluster generalization algorithms[J]. Engineering of Surveying and Mapping, 2015, 43- 47 doi: 10.3969/j.issn.1006-7949.2015.06.010

[8]	OKABE A, SATOH T, FURUTA T, et al Generalized network voronoi diagrams: concepts, computational methods, and applications[J]. International Journal of Geographical Information Science, 2008, 22 (9): 965- 994 doi: 10.1080/13658810701587891

[9]	佘冰, 叶信岳, 房会会, 等基于局部聚类的网络Voronoi图生成方法研究[J]. 地理科学, 2015, 35 (5): 637- 643 SHE Bing, YE Xin-yue, FANG Hui-hui, et al A method for integrating network Voronoi and spatial clustering[J]. Scientia Geographica Sinica, 2015, 35 (5): 637- 643

[10]	涂伟, 李清泉, 方志祥基于网络Voronoi图的大规模多仓库物流配送路径优化[J]. 测绘学报, 2014, 43 (10): 1075- 1082 TU Wei, LI Qing-quan, FANG Zhi-xiang Large scale multi-depot logistics routing optimization based on network Voronoi diagram[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43 (10): 1075- 1082

[11]	刘欣网络加权Voronoi图的动态构建[J]. 价值工程, 2015, 34 (22): 193- 194 LIU Xin The dynamic construction of network weighted Voronoi diagram[J]. Value Engineering, 2015, 34 (22): 193- 194

[12]	AI T H, YU W H, HE Y K Generation of constrained network Voronoi diagram using linear tessellation and expansion method[J]. Computers, Environment and urban systems, 2015, 51: 83- 96 doi: 10.1016/j.compenvurbsys.2015.02.001

[13]	艾廷华, 禹文豪水流扩展思想的网络空间Voronoi图生成[J]. 测绘学报, 2013, 42 (5): 760- 766 AI Ting-hua, YU Wen-hao Algorithm for constructing network Voronoi diagram based on flow extension ideas[J]. Computers, Environment and Urban Systems, 2013, 42 (5): 760- 766

[14]	郑鹏飞, 邹培玲, 赵菊娣, 等点云曲面空间网格化加密求交算法[J]. 浙江大学学报: 工学版, 2018, 52 (3): 605- 612 ZHENG Peng-fei, ZOU Pei-ling, ZHAO Ju-di, et al Intersection algorithm of point cloud surface by spatial mesh and refinement[J]. Jouranl of Zhejiang University: Engineering Science, 2018, 52 (3): 605- 612

[15]	禹文豪. 路径单元剖分法支持下的网络空间分析[D]. 武汉: 武汉大学, 2015. YU Wen-hao. Network spatial analysis supported by network tessellation approach [D]. Wuhan: Wuhan University, 2015.

[16]	TOPFER F, PILLEWIZER W The principles of selection[J]. The Cartographic Journal, 1966, 3 (1): 10- 16 doi: 10.1179/caj.1966.3.1.10

[17]	禄小敏, 闫浩文, 王中辉, 等基于约束Delaunay三角网的线, 面群目标分布边界计算[J]. 测绘工程, 2015, 24 (5): 37- 41 LU Xiao-min, YAN Hao-wen, WANG Zhong-hui, et al Computation of the boundaries of linear/polygonal groups based on constrained Delaunay triangulation[J]. Engineering of Surveying and Mapping, 2015, 24 (5): 37- 41 doi: 10.3969/j.issn.1006-7949.2015.05.009

[18]	杨敏, 艾廷华, 周启顾及道路目标Stroke特征保持的路网自动综合方法[J]. 测绘学报, 2014, 42 (4): 581- 587 YANG Min, AI Ting-hua, ZHOU Qi A method of road network generalization considering stroke properties of road object[J]. Acta Geodaetica et Cartographica Sinica, 2014, 42 (4): 581- 587

[19]	王家耀, 李志林, 武芳. 数字地图综合进展[M]. 北京: 科学出版社, 2011: 87.

[1]	TAN Wen-Ken, WANG Chang-Gong, DAN Yi-Shao. Digital underground spatial indexing QRtree based on XML[J]. Journal of ZheJiang University (Engineering Science), 2009, 43(09): 1615-1620.

Viewed

Full text

Abstract

Cited

Shared

Discussed