一种顾及空间关系约束的线化简算法

doi:10.11947/j.AGCS.2017.20160546

测绘学报 ›› 2017, Vol. 46 ›› Issue (4): 498-506.doi: 10.11947/j.AGCS.2017.20160546

一种顾及空间关系约束的线化简算法

李成名^1,2, 郭沛沛^1,2, 殷勇^1,2, 武鹏达², 顾腾³

1. 山东科技大学测绘科学与工程学院, 山东青岛 266590;
2. 中国测绘科学研究院, 北京 100830;
3. 东华理工大学测绘工程学院, 江西南昌 330013

收稿日期:2016-10-31 修回日期:2017-03-27 出版日期:2017-04-20 发布日期:2017-05-05
通讯作者: 郭沛沛 E-mail:guopeipei925@163.com
作者简介:李成名(1968-),男,博士,研究员,主要从事数字城市、智慧城市、地图制图与综合自动化研究。
基金资助:
国家科技支撑计划（2015BAJ06B01）；测绘地理信息公益性行业科研专项（201512027）；国家基础测绘项目（A1615）

A Line Simplification Algorithm Considering Spatial Relations between Two Lines

LI Chengming^1,2, GUO Peipei^1,2, YIN Yong^1,2, WU Pengda², GU Teng³

1. College of Geomatics, Shandong University of Science and Technology, Qingdao 266590, China;
2. Chinese Academy of Surveying and Mapping, Beijing 100830, China;
3. School of Geomatics, East China University of Tecnology, Nanchang 330013, China

Received:2016-10-31 Revised:2017-03-27 Online:2017-04-20 Published:2017-05-05

摘要/Abstract

摘要： 线要素化简在制图表达与综合领域一直是研究的热点和难点之一。然而，经典化简算法多针对单独线要素进行处理，缺乏对该线要素与周边线要素之间整体空间关系的考虑，并且，存在计算结果生硬（D-P算法）、局部极值点缺失，特别是在曲度较大之处出现相交异常（L-O算法）等问题。为此，本文提出一种顾及空间关系约束的线化简算法，建立线要素全局化简方法（LGSM）和矢量位移、面积位移等5类评价指标。采用等高线、河流和道路3类线要素实际数据进行了试验，充分检验了本文算法的优越性，其处理结果符合开方根模型规律，降低了曲线复杂度，在保证全局空间关系不变条件下，不仅更好地保持了曲线整体形状特征，而且光滑美观、精度高。

关键词: 线化简, 空间关系约束, 全局化简方法, 开方根模型

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

中图分类号:

P208

李成名, 郭沛沛, 殷勇, 武鹏达, 顾腾. 一种顾及空间关系约束的线化简算法[J]. 测绘学报, 2017, 46(4): 498-506.

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.

参考文献

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

一种顾及空间关系约束的线化简算法

A Line Simplification Algorithm Considering Spatial Relations between Two Lines

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价

[1]	张立华, 唐露露, 贾帅东, 戴泽源. 多条海岸线协同化简的层次化三角网分区法[J]. 测绘学报, 2019, 48(4): 520-531.
[2]	刘民士, 龙毅, 费立凡. 顾及拓扑一致性的水系三维曲线化简[J]. 测绘学报, 2016, 45(4): 494-501.
[3]	翟仁健武芳朱强. 曲线形态的结构化表达[J]. 测绘学报, 2009, 38(2): 0-174.