地图学与地理信息

道路网络示意图的多边形生长算法

  • 张蓝 ,
  • 李佳田 ,
  • 徐珩 ,
  • 贺飞越 ,
  • 徐燕竹 ,
  • 王红梅
展开
  • 昆明理工大学国土资源工程学院, 云南 昆明 650093
张蓝(1990—),女,硕士生,主要研究方向为地图综合和空间认知. E-mail:z.lan@foxmail.com

收稿日期: 2014-01-03

  修回日期: 2014-04-15

  网络出版日期: 2015-04-01

基金资助

国家自然科学基金(41161061;40901197)

Polygon Growing Algorithm for Network Schematic Maps

  • ZHANG Lan ,
  • LI Jiatian ,
  • XU Heng ,
  • HE Feiyue ,
  • XU Yanzhu ,
  • WANG Hongmei
Expand
  • Faculty of Land Resource Engineering, Kunming University of Science and Technology, Kunming 650093, China

Received date: 2014-01-03

  Revised date: 2014-04-15

  Online published: 2015-04-01

Supported by

The National Natural Science Foundation of China(Nos.41161061;40901197)

摘要

道路网络示意图是实体网络的抽象表示,因其更加符合人的认知习惯,在地图服务与地图制图领域已得到初步应用.以路径为单位的网络示意图自动生成算法只顾及节点与线段的局部布置,且较难以维护网络拓扑一致性.本文以闭合多边形(网眼)为基本单位,利用网眼的独立性与邻接性,提出了多边形生长算法,核心思想是将道路网络分类为闭合多边形与非闭合线段,以闭合多边形提取、映射、优化为主线,辅助组合非闭合线段.算例分析验证,本算法在网络均衡分布及拓扑一致性方面具有优势.

本文引用格式

张蓝 , 李佳田 , 徐珩 , 贺飞越 , 徐燕竹 , 王红梅 . 道路网络示意图的多边形生长算法[J]. 测绘学报, 2015 , 44(3) : 346 -352 . DOI: 10.11947/j.AGCS.2015.20130724

Abstract

Network schematic map is the abstract representation of entity network. It has been applied in the field of map service and cartography because it is more consistent with people's cognitive habits. The previous route-based auto schematic algorithms have only considered the local arrangement of nodes and are difficult to maintain topological consistency. In reaction to the deficiency, a new polygon-based algorithm is proposed in this paper, which uses the closed polygons (mesh) as the basic unit of the network for their independence and adjacency. The network is regarded as closed polygons and non-closed line segments. The main progress is extracting, mapping and combining closed polygons. Experimental analysis shows that this algorithm is more effective in balancing network spatial distribution and maintaining topological consistency.

参考文献

[1] MONMONIER M S. How to Lie with Maps[M]. Chicago: The University of Chicago Press, 1996.
[2] BARKOWSKY T, LATECKI L J, RICHTER K F. Schematizing Maps: Simplification of Geographic Shape by Discrete Curve Evolution[C]//Proceedings of Spatial Cognition II. Berlin: Springer, 2000: 41-53.
[3] AVELAR S, MÜLLER M. Generating Topologically Correct Schematic Maps[C]//Proceedings of the 9th International Symposium on Spatial Data Handling. [S.l.]: Springer, 2000: 28-35.
[4] AVELAR S. Schematic Maps on Demand: Design, Modeling and Visualization[D]. Zurich: Swiss Federal Institute of Technology, 2002.
[5] AVELAR S. Convergence Analysis and Quality Criteria for a Iterative Schematization of Networks[J]. Geoinformatica, 2007, 11(4): 497-513.
[6] AVELAR S, HURNI L. On the Design of Schematic Transport Maps[J]. Cartographica: The International Journal for Geographic Information and Geovisualization, 2006, 41(3):217-228.
[7] AVELAR S, HUBER R. Modeling a Public Transport Network for Generation of Schematic Maps and Location Queries[C]//Proceedings of the 20th International Cartographic Conference. Beijing: Surveying and Mapping Press, 2001: 1472-1480.
[8] STOTT J M, RODGERS P, MARTINEZ-OVANDO J C, et al. Automatic Metro Map Layout Using Multicriteria Optimization[J]. IEEE Transaction on Visualization and Computer Graphics, 2011, 17(1): 101-114.
[9] STOTT J M. Automatic Layout of Metro Maps Using Multicriteria Optimisation[D]. Canterbury: University of Kent, 2008.
[10] DONG Weihua, LI Zhilin, GUO Qingsheng. Automated Model Generalization of Schematic Networl Maps Based on Dynamic Segmentation[J]. Geomatics and Information Science of Wuhan University, 2010, 35(8): 892-895.(董卫华, 李志林, 郭庆胜. 基于动态分段的道路网示意性地图模型综合[J]. 武汉大学学报:信息科学版, 2010, 35(8): 892-895.)
[11] CABELLO S, DE BERG M, VAN KREVELD M. Schematization of Networks[J]. Computational Geometry, 2005, 30(3): 223-238.
[12] CABELLO S, VAN KREVELD M. Schematic Networks: an Algorithm and Its Implementation[C]//Proceedings of the 10th International Symposium on Spatial Data Handling. Ottawa: Springer, 2002: 475-486.
[13] HU Yungang, CHEN Jun, LI Zhilin, et al. Selective Omission of Road Features Based on Mesh Density for Digital Map Generalization[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3): 351-357.(胡云岗, 陈军, 李志林, 等. 基于网眼密度的道路选取方法[J]. 测绘学报, 2007, 36(3): 351-357.)
[14] DENG Hongyan, WU Fang, WANG Huilian, et al. A Generalization of Road Networks Based on Topological Similarity[J]. Journal of Geomatics Science and Technology, 2008,25(3):183-187.(邓红艳, 武芳, 王辉连, 等. 基于拓扑相似性的道路网综合模型[J]. 测绘科学技术学报, 2008, 25(3): 183-187.)
[15] CHEN Chun, ZHANG Shuwen, XU Guifen. The Basis for Generation of Topologic Information of Polygons in GIS[J]. Acta Geodaetica et Cartographica Sinica, 1996, 25(4): 266-271.(陈春, 张树文, 徐桂芬. GIS中多边形图拓扑信息生成的数学基础[J]. 测绘学报, 1996, 25(4): 266-271.)
[16] DU Qingyun. Automatic Organization of Polygon Data in Cartographic Database[J]. Acta Geodaetica et Cartographica Sinica, 1989, 18(3): 204-212.(杜清运. 地图数据库中多边形数据的自动组织[J]. 测绘学报, 1989, 18(3): 204-212.)
[17] WANG Zhaorui. Graph Theory[M].3rd Edition. Beijing: Beijing Institute of Technology Press, 2001.(王朝瑞. 图论[M]. 3版. 北京: 北京理工大学出版社, 2005.)
[18] AWARE J M, ANAND S, TAYLOR G E, et al. Automated Production of Schematic Maps for Mobile Applications[J]. Transactions in GIS, 2006, 10(1): 25-42.
[19] DONG Weihua, GUO Qingsheng, LIU Jiping, et al. Progressive Generalization Research of Schematic Road Network Maps[J]. Geomatics and Information Science of Wuhan University, 2007, 32(9): 829-832.(董卫华, 郭庆胜, 刘纪平, 等. 道路网示意性地图的渐进式综合研究[J]. 武汉大学学报:信息科学板, 2007, 32(9): 829-832.)
[20] LIANG Xiaowen, LIU Zongqi, CHEN Yijin. An algorithm of Polygon Auto-Construction Based on Angle Changing Tendence[J]. Journal of Image and Graphics, 2005, 10(6): 785-789.(梁晓文, 刘宗岐, 陈宜金. 基于夹角变化趋势的多边形自动搜索和生成算法[J].中国图象图形学报, 2005, 10(6): 785-789.)
文章导航

/