GIS应用中的矢量数据压缩算法研究

发布时间：2018-03-10 19:51

本文选题：矢量数据压缩　切入点：Douglas-Peucker算法　出处：《四川师范大学》2017年硕士论文　论文类型：学位论文

【摘要】：矢量数据压缩一直以来都是GIS领域的一个研究热点。通过减少矢量图形的数据量,来满足不同层次和尺度的应用需求,达到降低数据传输、处理时间和存储开销,提高图形的分析、渲染效果的目的。矢量数据压缩算法的研究历史可追溯至四十多年前。目前已出现了许多压缩算法,如Douglas-Peucker算法(DP算法)、Lang法、Li-Openshaw算法、基于小波分析的压缩算法,以及一些结合智能算法(例如遗传算法、动态规划算法、粒子群算法)的压缩算法。对该问题的研究虽然已有一些成果,但随着技术的进步,以及不断衍生的新需求,矢量数据压缩领域仍有一些问题未得到良好的解决。本文针对DP算法可能存在的问题进行了分析和优化,针对算法在处理多矢量数据时可能导致的两类拓扑异化问题进行分析研究并给出有效可行的解决方案,保证了多矢量图形压缩时的拓扑一致性。论文主要工作如下:(1)提出了一种基于节点重要性的分段DP算法,并对其进行了大量的实验验证。实验结果表明,与经典DP算法相比,本文算法在图形形状保持度和时间效率上都有所提高。(2)针对相邻图形公共边在化简时容易发生的裂缝问题,本文提出了一种基于扫描线和Geohash索引的公共边提取算法。首先利用单调链扫描线算法确定每个图形的相交图形;其次对于外接矩形相交的两图形,利用图形的Geohash索引快速查找两图形的公共点,提取公共边和非公共边,并标记公共边的顶点顺序;最后对于压缩过的公共边进行标记,保证公共边只处理一次。实验结果表明,该算法不仅可解决公共边裂缝问题,在时间效率上也具有较大优越性。(3)针对化简时存在的自相交或相交拓扑异化问题,本文提出了一种基于Geohash索引的相交拓扑异化快速处理算法。首先将化简前、后曲线围城的多边形区域转化为Geohash编码,以得到的Geohash编码集合作为查询条件在自身图形以及相关图形中检索编码对应的点,再通过射线法精确判断这些点是否位于化简前、后曲线围城的多边形区域内。若存在点位于该多边形区域内,则说明可能会发生自相交或相交,进行校正处理。实验结果表明,该算法能够保证压缩时无自相交或相交拓扑异化的发生,时间效率也较高。(4)在Microsoft Visual Studio 2010开发环境下使用C#编程语言,采用面向对象思想设计并开发了一个小型软件系统作为测试平台,并对测试平台进行了测试。
[Abstract]:Vector data compression has always been a research hotspot in the field of GIS. By reducing the data volume of vector graphics, it can meet the application requirements of different levels and scales, and reduce the data transmission, processing time and storage overhead. The research history of vector data compression algorithm can be traced back to more than 40 years ago. At present, many compression algorithms have appeared, such as Douglas-Peucker algorithm, DP algorithm, Li-Openshaw algorithm, wavelet analysis based compression algorithm, etc. And some compression algorithms combining intelligent algorithms (such as genetic algorithm, dynamic programming algorithm, particle swarm optimization algorithm). There are still some problems in the field of vector data compression which have not been solved well. This paper analyzes and optimizes the possible problems in DP algorithm. In this paper, two kinds of topology alienation problems caused by the algorithm in dealing with multi-vector data are analyzed and studied, and an effective and feasible solution is given. The main work of this paper is as follows: 1) A piecewise DP algorithm based on node importance is proposed, and a large number of experiments are carried out to verify it. The experimental results show that compared with the classical DP algorithm, the proposed algorithm is more efficient than the classical DP algorithm. In this paper, the shape preserving degree and time efficiency are improved. In this paper, a common edge extraction algorithm based on scan line and Geohash index is proposed. Firstly, the monotone chain scan line algorithm is used to determine the intersection of each graph. The Geohash index of graphics is used to quickly find the common points of the two graphics, to extract the common edges and non-common edges, and to mark the vertex order of the common edges. Finally, the compressed common edges are marked to ensure that the common edges are processed only once. The experimental results show that, This algorithm can not only solve the problem of common edge crack, but also has great superiority in time efficiency. In this paper, a fast algorithm of intersecting topological dissimilation based on Geohash index is proposed. Firstly, the polygon region of the curve besieged before and after the simplification is transformed into Geohash coding. The obtained Geohash coding set is used as the query condition to retrieve the corresponding points in their own graphics and related graphics, and then the ray method is used to determine precisely whether these points are located before the simplification. If the point of existence is in the polygon region, the self-intersection or intersecting may occur, and the experimental results show that, The algorithm can ensure that there is no self-intersection or intersecting topology dissimilation in compression, and the time efficiency is also high. The algorithm uses C # programming language in Microsoft Visual Studio 2010 development environment. In this paper, a small software system is designed and developed with the object oriented idea as the test platform, and the test platform is tested.
【学位授予单位】：四川师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：P208

【参考文献】