一种基于单调链和Geohash索引的公共边裂缝处理算法

A Common Edge Crack Processing Algorithm Based on a Monotonic Chain and Geohash Index

在分析矢量数据压缩时产生公共边裂缝的原因以及解决该问题的常用方法的优缺点的基础上,提出一种基于单调链和Geohash的公共边裂缝处理算法.首先,算法采用单调链扫描线算法从图形集中为每一个矢量图形快速确定可与之相交的图形子集;其次,利用Geohash索引快速查找相交图形的公共点,继而提取出公共边和非公共边;然后,设计一个索引结构存储公共边的压缩信息,用于公共边只压缩一次的前提下保证图形集的完整性;最后,从有效性和时间效率2个方面对算法进行分析和评价.实验结果表明,算法对图形进行逻辑分段保证了公共边在相邻图形中化简结果的一致,与目前比较优秀的同类算法相比,在可行性以及在时间效率上都具有一定的优越性.

Based on the analysis of the causes of common edge cracks in vector data compression and the advantages and disadvantages of some methods to solve this problem,a common edge crack processing algorithm based on a monotonic chain and a Geohash index is proposed in this paper.Firstly,a monotone chain scanline algorithm is applied to quickly determine the intersection vector graphics which possibly have common edges with a tested vector graphic.Secondly,by making full use of the quick search feature of Geohash index,the common points between the vector graphic and its adjacent graphics are fast found,so as to efficiently extract the common edges and non-common edges from the vector graphic data.Then,an index data structure is designed to store the compressed information of the common edge which can ensure the integrity of the graph set under the premise that the common edge is compressed only once.Finally,the effectiveness and time efficiency of the algorithm are analyzed and evaluated.The experimental results show that this kind of logical segmentation of vector graphic data ensures the simplification consistency for the common edges between adjacent graphics.Compared with the current excellent similar algorithms,it has certain advantages in feasibility and time efficiency.