A progressive simplification method of navigation road map based on mesh model

doi:10.11947/j.AGCS.2019.20180552

Abstract

Abstract: In this paper the graphic generalization of roads is transformed into linear graphic simplification based on mesh model when the navigation data precision is decreased. A progressive collaborative graphic generalization method for roads in the navigation data is proposed based on the mesh model, which can ensure that the single road and road networks after generalization are similar to the original high-precision data in spatial directional relationship. In the process of data handling, the navigational requirements are applied to constrain the progressive graphic simplification of the road. Besides, characteristics of road shape and the spatial direction relationship at the intersection of roads are maintained while visualizations of the roads in navigation is taken into consideration. The algorithm proposed in this paper has been verified with navigation data in actual production, which proves the method is both effective and practical.

Key words: navigation road network, progressive map generalization, linear graphic simplification, mesh model, spatial direction relationship

CLC Number:

P208

GUO Qingsheng, LIU Yang, LI Meng, CHENG Xiaoxi, HE Jie, WANG Huihui, WEI Zhiwei. A progressive simplification method of navigation road map based on mesh model[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11): 1357-1368.

References 26

[1]	DOUGLAS D H, PEUCKER T K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. Cartographica, 1973, 10(2):112-122.
[2]	HERSHBERGER J, SNOEYINK J. Speeding up the Douglas-Peucker line-simplification algorithm[C]//Proceedings of the 5th International Symposium on Spatial Data Handling. Charleston, South Carolina:[s.n.], 1992:134-143.
[3]	SAALFELD A. Topologically consistent line simplification with the Douglas-Peucker algorithm[J]. Cartography and Geographic Information Science, 1999, 26(1):7-18.
[4]	CROMLEY R G, CAMPBELL G M. Integrating quantitative and qualitative aspects of digital line simplification[J]. The Cartographic Journal, 1992, 29(1):25-30.
[5]	JIANG Bin, NAKOS B. Line simplification using self-organizing maps[C]//Proceedings of ISPRS Workshop on Spatial Analysis and Decision Making. Hong Kong, China:ISPRS, 2003.
[6]	武芳, 邓红艳. 基于遗传算法的线要素自动化简模型[J]. 测绘学报, 2003, 32(4):349-355. DOI:10.3321/j.issn:1001-1595.2003.04.013. WU Fang, DENG Hongyan. Using genetic algorithms for solving problems in automated line simplification[J]. Acta Geodaetica et Cartographica Sinica, 2003, 32(4):349-355. DOI:10.3321/j.issn:1001-1595.2003.04.013.
[7]	郑春燕, 郭庆胜, 胡华科. 基于蚁群优化算法的线状目标简化模型[J]. 测绘学报, 2011, 40(5):635-638. ZHENG Chunyan, GUO Qingsheng, HU Huake. The simplification model of linear objects based on ant colony optimization algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(5):635-638.
[8]	WANG Zeshen, MVLLER J C. Line generalization based on analysis of shape characteristics[J]. Cartography and Geographic Information Systems, 1998, 25(1):3-15.
[9]	GÖKGÖZ T, SEN A, MEMDUHOGLU A, et al. A new algorithm for cartographic simplification of streams and lakes using deviation angles and error bands[J]. ISPRS International Journal of Geo-Information, 2015, 4(4):2185-2204.
[10]	钱海忠, 武芳, 陈波, 等. 采用斜拉式弯曲划分的曲线化简方法[J]. 测绘学报, 2007, 36(4):443-449, 456. DOI:10.3321/j.issn:1001-1595.2007.04.014. QIAN Haizhong, WU Fang, CHEN Bo, et al. Simplifying line with oblique dividing curve method[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(4):443-449, 456. DOI:10.3321/j.issn:1001-1595.2007.04.014.
[11]	何海威, 钱海忠, 王骁, 等. 采用弯曲进行道路化简冲突避免的方法[J]. 测绘学报, 2016, 45(3):354-361. DOI:10.11947/j.AGCS.2016.20140576. HE Haiwei, QIAN Haizhong, WANG Xiao, et al. Avoiding special conflicts in road simplification by using road bends[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(3):354-361. DOI:10.11947/j.AGCS.2016.20140576.
[12]	李成名, 郭沛沛, 殷勇, 等. 一种顾及空间关系约束的线化简算法[J]. 测绘学报, 2017, 46(4):498-506. DOI:10.11947/j.AGCS.2017.20160546. LI Chengming, GUO Peipei, YIN Yong, et al. A line simplification algorithm considering spatial relations between two lines[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(4):498-506. DOI:10.11947/j.AGCS.2017.20160546.
[13]	艾廷华, 郭仁忠, 刘耀林. 曲线弯曲深度层次结构的二叉树表达[J]. 测绘学报, 2001, 30(4):343-348. DOI:10.3321/j.issn:1001-1595.2001.04.013. AI Tinghua, GUO Renzhong, LIU Yaolin. A binary tree representation of curve hierarchical structure in depth[J]. Acta Geodaetica et Cartographica Sinica, 2001, 30(4):343-348. DOI:10.3321/j.issn:1001-1595.2001.04.013.
[14]	翟仁健, 武芳, 朱丽, 等. 曲线形态的结构化表达[J]. 测绘学报, 2009, 38(2):175-182. DOI:10.3321/j.issn:1001-1595.2009.02.014. ZHAI Renjian, WU Fang, ZHU Li, et al. Structured representation of curve shape[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(2):175-182. DOI:10.3321/j.issn:1001-1595.2009.02.014.
[15]	郭庆胜, 黄远林, 章莉萍. 曲线的弯曲识别方法研究[J]. 武汉大学学报(信息科学版), 2008, 33(6):596-599. GUO Qingsheng, HUANG Yuanlin, ZHANG Liping. The method of curve bend recognition[J]. Geomatics and Information Science of Wuhan University, 2008, 33(6):596-599.
[16]	张栋海, 黄丽娜, 费立凡, 等. 一种基于曲率法的曲线特征点选取方法[J]. 测绘科学, 2013, 38(3):151-153. ZHANG Donghai, HUANG Lina, FEI Lifan, et al. An algorithm of extracting feature points in curve based on the curvature[J]. Science of Surveying and Mapping, 2013, 38(3):151-153.
[17]	RAPOSO P. Scale-specific automated line simplification by vertex clustering on a hexagonal tessellation[J]. Cartography & Geographic Information Science, 2013, 40(5):427-443.
[18]	郭庆胜. 线状要素图形综合的渐进方法研究[J]. 武汉测绘科技大学学报, 1998, 23(1):52-56. GUO Qingsheng. Study on progressive approach to graphic generalization of linear feature[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1998, 23(1):52-56.
[19]	杜佳威, 武芳, 李靖涵, 等. 一种河口湾海岸线渐进化简方法[J]. 测绘学报, 2018, 47(4):547-556. DOI:10.11947/j.AGCS.2018.20170440. DU Jiawei, WU Fang, LI Jinghan, et al. A progressive simplification method for the estuary coastline[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(4):547-556. DOI:10.11947/j.AGCS.2018.20170440.
[20]	遆鹏, 贾洪果, 徐柱, 等. 面向道路网络地图示意化的线形简化方法[J]. 测绘学报, 2014, 43(12):1280-1284, 1292. DOI:10.13485/j.cnki.11-2089.2014.0190. TI Peng, JIA Hongguo, XU Zhu, et al. A line-shape-simplification method for schematization of road network map[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(12):1280-1284, 1292. DOI:10.13485/j.cnki.11-2089.2014.0190.
[21]	蔡剑红, 李德仁. 多尺度下的不确定性空间方向锥形模型研究[J]. 武汉大学学报(信息科学版), 2007, 32(8):735-739. CAI Jianhong, LI Deren. Research on cone-shaped models of cardinal direction relations considering positional uncertainty of multiple spatial-scale data[J]. Geomatics and Information Science of Wuhan University, 2007, 32(8):735-739.
[22]	闫浩文, 郭仁忠. 空间方向关系形式化描述模型研究[J]. 测绘学报, 2003, 32(1):42-46. DOI:10.3321/j.issn:1001-1595.2003.01.009. YAN Haowen, GUO Renzhong. Research on formal description model of directional relationships[J]. Acta Geodaetica et Cartographica Sinica, 2003, 32(1):42-46. DOI:10.3321/j.issn:1001-1595.2003.01.009.
[23]	DENG Min, LI Zhilin. A statistical model for directional relations between spatial objects[J]. GeoInformatica, 2008, 12(2):193-217.
[24]	YAN Haowen, CHU Yandong, LI Zhilin, et al. A quantitative description model for direction relations based on direction groups[J]. GeoInformatica, 2006, 10(2):177-196.
[25]	潘正风, 罗年学, 黄全义. 近似斜轴抛物线加权平均插值法曲线光滑[J]. 测绘学报, 1991, 20(1):60-65. PAN Zhengfeng, LUO Nianxue, HUANG Quanyi. Approximate interpolation by weighted average on skew axial parabola[J]. Acta Geodaetica et Cartographica Sinica, 1991, 20(1):60-65.
[26]	李伟, 郭沛沛, 武鹏达, 等. 地图综合中曲线局部尖锐凸角的光滑方法[J]. 测绘科学, 2018, 43(10):112-116. LI Wei, GUO Peipei, WU Pengda, et al. Smooth method of local convex sharp angle in cartographic generalization[J]. Science of Surveying and Mapping, 2018, 43(10):112-116.