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

doi:10.11947/j.AGCS.2015.20130724

测绘学报 ›› 2015, Vol. 44 ›› Issue (3): 346-352.doi: 10.11947/j.AGCS.2015.20130724

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

张蓝, 李佳田, 徐珩, 贺飞越, 徐燕竹, 王红梅

昆明理工大学国土资源工程学院, 云南昆明 650093

收稿日期:2014-01-03 修回日期:2014-04-15 出版日期:2015-03-20 发布日期:2015-04-01
通讯作者: 李佳田 E-mail:ljtwcx@163.com E-mail:ljtwcx@163.com
作者简介:张蓝(1990—),女,硕士生,主要研究方向为地图综合和空间认知. E-mail:z.lan@foxmail.com
基金资助:
国家自然科学基金(41161061;40901197)

Polygon Growing Algorithm for Network Schematic Maps

ZHANG Lan, LI Jiatian, XU Heng, HE Feiyue, XU Yanzhu, WANG Hongmei

Faculty of Land Resource Engineering, Kunming University of Science and Technology, Kunming 650093, China

Received:2014-01-03 Revised:2014-04-15 Online:2015-03-20 Published:2015-04-01
Supported by:
The National Natural Science Foundation of China(Nos.41161061;40901197)

摘要/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

中图分类号:

P208

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

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.

参考文献

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

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

Polygon Growing Algorithm for Network Schematic Maps

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	杨凯淳, 吕志平, 李林阳, 邝英才, 许炜, 郑茜. 附加历元间约束的滑动窗单频实时精密单点定位算法[J]. 测绘学报, 2022, 51(5): 648-657.
[2]	唐晓芳, 詹总谦, 丁久婕, 刘佳辉, 熊子柔. 顾及超像素光谱特征的无人机影像自动模糊聚类分割法[J]. 测绘学报, 2022, 51(5): 677-690.
[3]	王珂, 刘国林, 付政庆, 王路遥. 基于Moore-Penrose广义逆及立体矩阵的可分离非线性最小二乘解算方法[J]. 测绘学报, 2022, 51(3): 340-350.
[4]	李景文, 韦晶闪, 姜建武, 陆妍玲, 刘垒, 唐一飞, 李旭. 多视角监控视频中动态目标的时空信息提取方法[J]. 测绘学报, 2022, 51(3): 388-400.
[5]	纪松, 张永生, 董杨, 范大昭. 星载轻量化影像控制点数据制作方法[J]. 测绘学报, 2022, 51(3): 413-425.
[6]	曹闻, 彭斐琳, 童晓冲, 戴浩然, 张勇. 顾及空间分布与注记相关性的点要素注记配置算法[J]. 测绘学报, 2022, 51(2): 301-311.
[7]	纪雪, 唐秋华, 陈义兰, 李杰, 丁德秋. 联合支持向量机和增强学习算法的多波束声学底质分类[J]. 测绘学报, 2021, 50(7): 972-981.
[8]	刘远刚, 李少华, 蔡永香, 何贞铭, 马潇雅, 李鹏程, 郭庆胜, 何宗宜. 移位安全区约束下的建筑物群移位免疫遗传算法[J]. 测绘学报, 2021, 50(6): 812-822.
[9]	叶发茂, 孟祥龙, 董萌, 聂运菊, 葛芸, 陈晓勇. 遥感图像蚁群算法和加权图像到类距离检索法[J]. 测绘学报, 2021, 50(5): 612-620.
[10]	颜金彪, 吴波, 何清华. 顾及各向异性的多参数协同优化IDW插值方法[J]. 测绘学报, 2021, 50(5): 675-684.
[11]	毕自军, 赵建虎, 郑根, 刘美琴. 顾及传播曲面的多波束波束脚印高精度快速归位算法[J]. 测绘学报, 2021, 50(5): 695-705.
[12]	周哲, 胡钊政, 李娜, 肖汉彪, 伍锦祥. 面向智能车的地下停车场环视特征地图构建与定位[J]. 测绘学报, 2021, 50(11): 1574-1584.
[13]	吕栋, 欧吉坤, 于胜文. 基于MEA-BP神经网络的卫星钟差预报[J]. 测绘学报, 2020, 49(8): 993-1003.
[14]	郭迎钢, 李宗春, 何华, 王志颖. 三维坐标转换公共点最优权值的单纯形搜索算法[J]. 测绘学报, 2020, 49(8): 1004-1013.
[15]	张驰, 李姗姗, 史颜俊, 邢志斌, 范雕. 蚁群-势场算法在水下重力辅助导航航迹规划中的应用[J]. 测绘学报, 2020, 49(7): 865-873.