基于网络加权Voronoi图的点群选取
|
摘要
传统基于Voronoi图的算法忽略了点与点之间是通过实际网络距离相连这一事实,针对此缺陷,提出一种基于网络加权Voronoi图的点群选取算法. 1)利用网络扩展法构建点群的网络加权Voronoi图;2)计算每个点对应的网络Voronoi多边形面积及扩展弧段总长度,并以此为依据,为点群中所包含的统计、专题、拓扑和度量信息分别选定量化描述因子;3)提出"同心圆"算法,解决点群取舍问题.实验结果表明,提出的方法顾及了点群权重以及与点群相关联的道路等级、方向及局部密度对选取结果的影响,较好地保持了原始点群的各类信息,选取结果符合实际地理空间特征.
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.
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.
引文
[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.
[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 Geo Science,2008,34(8):939-954.
[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.
[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.
[9]佘冰,叶信岳,房会会,等.基于局部聚类的网络Voronoi图生成方法研究[J].地理科学,2015,35(5):637-643.SHE Bing,YE Xin-yue,FANG Hui-hui,et al.Amethod 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.
[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.
[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.
[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.
[20]LI Z L,HUANG P Z.Qualitative measures for spatial information of maps[J].International Journal of Geographical Information Systems,2002,16(7):699-709.
[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.
[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 Geo Science,2008,34(8):939-954.
[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.
[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.
[9]佘冰,叶信岳,房会会,等.基于局部聚类的网络Voronoi图生成方法研究[J].地理科学,2015,35(5):637-643.SHE Bing,YE Xin-yue,FANG Hui-hui,et al.Amethod 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.
[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.
[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.
[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.
[20]LI Z L,HUANG P Z.Qualitative measures for spatial information of maps[J].International Journal of Geographical Information Systems,2002,16(7):699-709.