Polygon Growing Algorithm for Network Schematic Maps

doi:10.11947/j.AGCS.2015.20130724

Abstract

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.

Key words: network schematic maps, mesh density, closed polygon, mapping, algorithm

CLC Number:

P208

ZHANG Lan, LI Jiatian, XU Heng, HE Feiyue, XU Yanzhu, WANG Hongmei. Polygon Growing Algorithm for Network Schematic Maps[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(3): 346-352.

References

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