地球信息科学学报 ›› 2019, Vol. 21 ›› Issue (10): 1502-1509.doi: 10.12082/dqxxkx.2019.190214

• 地球信息科学理论与方法 • 上一篇    下一篇

矢量瓦片地图线化简算法研究

金澄1,2,3,安晓亚2,3,*(),崔海福4,赵宇君5,王惠5   

  1. 1. 信息工程大学地理空间信息学院,郑州 450052
    2. 西安测绘研究所,西安 710054
    3. 地理信息工程国家重点实验室,西安 710054
    4. 中国地质大学(武汉)信息工程学院,武汉 430074
    5. 武汉中地研究院,武汉 430074
  • 收稿日期:2019-05-07 修回日期:2019-07-08 出版日期:2019-10-25 发布日期:2019-10-29
  • 通讯作者: 安晓亚 E-mail:xya2001@tom.com
  • 作者简介:金澄(1976-),男,陕西西安人,高级工程师,主要研究方向为地理信息服务。E-mail:jinchengno1@163.com
  • 基金资助:
    国防“973”计划项目(613317)

An Algorithm for Simplifying Linear Elements of Vector Tile Maps

JIN Cheng1,2,3,AN Xiaoya2,3,*(),CUI Haifu4,ZHAO Yujun5,WANG Hui5   

  1. 1. Faculty of Geospatial Information, University of Information Engineering, Zhengzhou 450052, China
    2. Xi'an Research Institute of Surveying and Mapping, Xi'an 710054, China
    3. State Key Laboratory of Geo-information Engineering, Xi'an 710054, China
    4. Faculty of Information Engineering, China University of Geosciences, Wuhan 430074, China
    5. Wuhan Zhongdi Research Institute, Wuhan 430074, China
  • Received:2019-05-07 Revised:2019-07-08 Online:2019-10-25 Published:2019-10-29
  • Contact: AN Xiaoya E-mail:xya2001@tom.com
  • Supported by:
    Defense “973” of China(613317)

摘要:

线状要素化简对提高矢量瓦片地图服务过程中数据传输效率和可视化表达效果至关重要。常见经典化简算法大多不考虑化简前后曲线空间关系的一致性保持,导致易发生化简结果尖锐化、局部极值点缺失和产生相交等异常问题,如果考虑化简前后空间关系的一致性,则影响化简效率。鉴于此,结合矢量瓦片地图服务应用需求,本文提出一种改进的Visvalingam算法,采用最小堆技术解决了最小权重值查找效率低下问题,利用线自相交拓扑关系判断策略,从全局考虑线上其它点对当前点的影响,解决了线化简前后拓扑关系的一致性保持问题。将改进的算法与原始算法在拓扑关系、几何特征、位置精度和化简效率等方面进行实验对比分析,结果表明改进算法可顾及线状要素的拓扑关系,保证化简前后线状要素的整体形态及其拓扑关系不变,能够更高效地应用于矢量瓦片地图在线服务中。

关键词: 矢量瓦片地图, 地图服务, 地图综合, 拓扑关系, Visvalingam算法, 线化简, 最小堆

Abstract:

The simplification of linear elements is very important to improve the efficiency of data transmission and visual expression in vector tile map services. Most classical simplification algorithms do not consider the consistency of curves' spatial relations before and after the simplification, which leads to abnormal problems such as sharpening the results of simplification, missing local extremum points, generating line intersection. Considering consistency will affect the efficiency of simplification. In this context, an improved Visvalingam algorithm was proposed according to the application requirements of the vector tile map service.The algorithm applies the minimum heap technology to solve the problem of low efficiency of minimum weight value search, and uses the judgment strategy of self-intersecting topological relation of the line to consider the influence of other points on the current point from the global perspective. In so doing, we can solve the problem of consistency preservation of the topological relationship before and after the simplification of linear elements. The improved Visvalingam algorithm was compared with the original Visvalingam algorithm in terms of topological relationship, geometric features, position accuracy, and simplification efficiency. Results show that the improved Visvalingam algorithm accounted for the topological relations of linear elements and ensuredthe consistency of the overall morphology and topologicalrelationship before and after thesimplification.Our findings suggest that the prosposed Visvalingam algorithm can be applied to the online vector tile map service more efficiently.

Key words: vector tile maps, map service, map generalization, topological relationship, Visvalingam algorithm, linear simplification, minimum heap