A Line Simplification Algorithm Considering Spatial Relations between Two Lines

doi:10.11947/j.AGCS.2017.20160546

Abstract

Abstract: Line element simplification has always been a hot research topic in the field of cartography generalization and expression. However, more existing line simplification algorithms aimed at single line rather than spatial relationship between linear elements. At the same time, there are some problems with classical algorithm, such as blunt performance(D-P algorithm), missing local extreme point and curve intersection(L-O algorithm). So, this paper puts forward a line simplification algorithm taking account of spatial relations between two lines. Line global simplification method(LGSM), vector displacement, area displacement and so on are proposed. Experiments are carried out on three kinds of line elements,such as contour lines, rivers and roads. The experiments' results show that the proposed algorithm can maintain the overall shape of the curve better and reduce the complexity of the curve effectively, the shape is more smooth and has a high position accuracy.

Key words: line simplification, spatial relations constraints, line global simplification method(LGSM), square-root model

CLC Number:

P208

LI Chengming, GUO Peipei, YIN Yong, WU Pengda, GU Teng. A Line Simplification Algorithm Considering Spatial Relations between Two Lines[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(4): 498-506.

References

[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]. Cartographer, 1973, 10(2): 112-122.
[2] 李志林, OPENSHAW S. 基于客观综合自然规律的线状要素自动综合的算法[J]. 武测译文, 1994(1): 49-58. LI Zhilin, OPENSHAW S. Linear Feature's Self-adapted Generalization Algorithm Based on Impersonality Generalized Natural Law[J]. Translation of Wuhan Technical University of Surveying and Mapping, 1994(1): 49-58.
[3] 朱鲲鹏, 武芳, 王辉连, 等. Li-Openshaw算法的改进与评价[J]. 测绘学报, 2007, 36(4): 450-456. ZHU Kunpeng, WU Fang, WANG Huilian, et al. Improvement and Assessment of Li-Openshaw Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(4): 450-456.
[4] 刘慧敏, 樊子德, 徐震, 等. 曲线化简的弧比弦算法改进及其评价[J]. 地理与地理信息科学, 2011, 27(1): 45-48. LIU Huimin, FAN Zide, XU Zhen, et al. An Improved Local Length Ratio Method for Curve Simplification and Its Evaluation[J]. Geography and Geo-Information Science, 2011, 27(1): 45-48.
[5] 顾腾, 陈晓勇, 刘成强. 一种Douglas-Peucker与Li-Openshaw结合改进的曲线化简方法[J]. 东华理工大学学报(自然科学版), 2016, 39(4): 396-400. GU Teng, CHEN Xiaoyong, LIU Chengqiang. A modified Line Simplification Method Combined Douglas-Peucker with Li-Openshaw[J]. Journal of East China University of Technology, 2016, 39(4): 396-400.
[6] NAKOS B, MITROPOULOS V. Local Length Ratio as a Measure of Critical Points Detection for Line Simplification[C]//The Symposium of the 5th ICA Workshop on Progress in Automated Map Generalization. Paris, France: ICA, 2003: 28-30.
[7] 艾廷华, 刘耀林. 保持空间分布特征的群点化简方法[J]. 测绘学报, 2002, 31(2): 175-181. AI Tinghua, LIU Yaolin. A Method of Point Cluster Simplification with Spatial Distribution Properties Preserved[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(2): 175-181.
[8] MULLER J C. Fractal and Automated Line Generalization[J]. The Cartographic Journal, 1987, 24(1): 27-34.
[9] 郭庆胜, 刘小利, 陈宇箭. 线与线之间的空间拓扑关系组合推理[J]. 武汉大学学报(信息科学版), 2006, 31(1): 39-42. GUO Qingsheng,LIU Xiaoli,CHEN Yujian.Combinational Reasoning of Topological Spatial Relations between Two Lines[J]. Geomatics and Information Science of Wuhan University, 2006, 31(1): 39-42.
[10] 何建华, 刘耀林. GIS中拓扑和方向关系推理模型[J]. 测绘学报, 2004, 33(2): 156-162. DOI: 10.3321/j.issn:1001-1595.2004.02.012. HE Jianhua, LIU Yaolin. An Integrated Model for Topology & Direction Relation Reasoning[J]. Acta Geodaetica et Cartographica Sinica, 2004, 33(2): 156-162. DOI: 10.3321/j.issn:1001-1595.2004.02.012.
[11] 王家耀, 崔铁军, 王光霞. 图论在道路网自动选取中的应用[J]. 解放军测绘学院学报, 1985(1): 79-86. WANG Jiayao,CUI Tiejun,WANG Guangxia.Applications of Graph Theory in Automatic Selection of Road Network[J]. Journal of Geomatics Science and Technology, 1985(1): 79-86.
[12] CHEN Jun, LI Chengming, LI Zhilin, et al. A Voronoi-based 9-intersection Model for Spatial Relations[J]. International Journal of Geographical Information Science, 2001, 15(3): 201-220.
[13] WINTER S, FRANK A U. Topology in Raster and Vector Representation[J]. GeoInformatica, 2000, 4(1): 35-65.
[14] 邓敏, 李成名, 刘文宝. 利用拓扑和度量相结合的方法描述面目标间的空间关系[J]. 测绘学报, 2002, 31(2): 164-169. DENG Min, LI Chengming, LIU Wenbao. Describing Spatial Relations between Area Objects via Combining Topology with Metrization[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(2): 164-169.
[15] 陈述彭, 鲁学军, 周成虎. 地理信息系统导论[M]. 北京: 科学出版社, 1999. CHEN Shupeng, LU Xuejun, ZHOU Chenghu. Introduction to Geographic Information System[M]. Beijing: Science Press, 1999.
[16] 王鹏波, 武芳, 翟仁健. 一种用于道路网综合的拓扑处理方法[J]. 测绘科学技术学报, 2009, 26(1): 64-68. WANG Pengbo, WU Fang, ZHAI Renjian. A Topologic Operation Method for Automated Generalization of Road Networks[J]. Journal of Geomatics Science and Technology, 2009, 26(1): 64-68.
[17] WHITE E R.Assessment of Line-Generalization Algorithms Using Characteristic Points[J].The American Cartographer, 1985, 12(1): 17-28.
[18] MCMASTER R B. A Statistical Analysis of Mathematical Measures for Linear Simplification[J]. The American Cartographer, 1986, 13(2): 103-116.
[19] MCMASTER R B. Automated Line Generalization[J]. Cartographica, 1987, 24(2): 74-111.
[20] 武芳, 朱鲲鹏. 线要素化简算法几何精度评估[J]. 武汉大学学报(信息科学版), 2008, 33(6): 600-603. WU Fang,ZHU Kunpeng.Geometric Accuracy Assessment of Linear Features' Simplification Algorithms[J]. Geomatics and Information Science of Wuhan University, 2008, 33(6): 600-603.
[21] 陈竞男, 钱海忠, 王骁, 等. 提高线要素匹配率的动态化简方法[J]. 测绘学报, 2016, 45(4): 486-493. DOI: 10.11947/j.AGCS.2016.20150074. CHEN Jingnan, QIAN Haizhong, WANG Xiao, et al. Improving the Matching Rate of Line Feature by Using Dynamic Simplification[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(4): 486-493. DOI: 10.11947/j.AGCS.2016.20150074.
[22] 邓敏, 陈杰, 李志林, 等. 曲线简化中节点重要性度量方法比较及垂比弦法的改进[J]. 地理与地理信息科学, 2009, 25(1): 40-43. DENG Min, CHEN Jie, LI Zhilin, et al. An Improved Local Measure Method for the Importance of Vertices in Curve Simplification[J]. Geography and Geo-Information Science, 2009, 25(1): 40-43.
[23] 何宗宜. 地图数据处理模型的原理与方法[M]. 武汉: 武汉大学出版社, 2004. HE Zongyi. Elements and Methods of Model for Cartographical Data Processing[M]. Wuhan: Wuhan University Press, 2004.
[24] 张青年. 逐层分解选取指标的河系简化方法[J]. 地理研究, 2007, 26(2): 222-228. ZHANG Qingnian. Drainage Generalization by Layered Division of The Number of Retained Rivers in River Trees[J]. Geographical Research, 2007, 26(2): 222-228.
[25] 邵黎霞, 何宗宜, 艾自兴, 等. 基于BP神经网络的河系自动综合研究[J]. 武汉大学学报(信息科学版), 2004, 29(6): 555-557. SHAO Lixia, HE Zongyi, AI Zixing, et al. Automatic Generalization of River Network Based on BP Neural Network Techniques[J]. Geomatics and Information Science of Wuhan University, 2004, 29(6): 555-557.