Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2019, Vol. 53 Issue (3): 571-578    DOI: 10.3785/j.issn.1008-973X.2019.03.019
计算机技术     
基于网络加权Voronoi图的点群选取
禄小敏1,2,3(),闫浩文2,3,*(),康路2,3,武芳4
1. 兰州交通大学 环境与市政工程学院 甘肃 兰州 730070
2. 兰州交通大学 测绘与地理信息学院 甘肃 兰州 730070
3. 甘肃省地理国情监测工程实验室 甘肃 兰州 730070
4. 信息工程大学 地理空间信息学院 河南 郑州 450000
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
 全文: PDF(1557 KB)   HTML
摘要：

传统基于Voronoi图的算法忽略了点与点之间是通过实际网络距离相连这一事实，针对此缺陷，提出一种基于网络加权Voronoi图的点群选取算法. 1）利用网络扩展法构建点群的网络加权Voronoi图；2）计算每个点对应的网络Voronoi多边形面积及扩展弧段总长度，并以此为依据，为点群中所包含的统计、专题、拓扑和度量信息分别选定量化描述因子；3）提出“同心圆”算法，解决点群取舍问题. 实验结果表明，提出的方法顾及了点群权重以及与点群相关联的道路等级、方向及局部密度对选取结果的影响，较好地保持了原始点群的各类信息，选取结果符合实际地理空间特征.
关键词： 网络加权Voronoi图;  栅格化;  点群选取;  扩展算法;  “同心圆”算法    
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
收稿日期: 2018-05-19 出版日期: 2019-03-04
CLC:  P 283  
通讯作者: 闫浩文     E-mail: xiaominlu08@gmail.com;haowen2010@gmail.com
作者简介: 禄小敏（1982 —），女，博士生，从事方向关系与地图制图研究. orcid.org/0000-0002-6206-251X. E-mail: xiaominlu08@gmail.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
禄小敏
闫浩文
康路
武芳

引用本文:

禄小敏,闫浩文,康路,武芳. 基于网络加权Voronoi图的点群选取[J]. 浙江大学学报(工学版), 2019, 53(3): 571-578.

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.

链接本文:

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

图 1  基于网络加权Voronoi图的点群选取算法流程图
图 2  传统栅格模型与网络栅格模型
图 3  发生元点的栅格化结果
图 4  点群的扩展操作过程
图 5  网络加权Voronoi图的生成
图 6  点群的网络加权Voronoi多边形及其扩展弧段
图 7  删除点的“同心圆”算法
图 8  基于网络加权Voronoi图的点群选取实验
图 9  基于传统加权Voronoi图（MWVD）的点群选取实验
算法 Ds Dth（归一化后） Dtp Dm/%
基于MWVD的点群选取算法 1.00 0.062 1.563 1.324
本文点群选取算法 0.21 0.154 1.612 1.483
表 1  实验中各类信息的传输程度
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] 谭文垦, 王长虹, 石忆邵. 基于XML的数字地下空间索引QR树研究[J]. J4, 2009, 43(09): 1615-1620.