一种基于预存交点的矢量空间叠加分析算法

A vector spatial overlay analysis algorithm based on pre-storing intersections

针对矢量空间叠加分析服务实时性的需求,提出了一种基于预存交点信息的矢量空间叠加分析算法。在叠加分析算法中实现了存储计算一体化的交点数据结构,能够满足交点额外空间占用率小的存储需求和快速获取交点信息的计算需求。在叠加分析时,将图层之间的交点离线计算并存储,以查询交点的方式代替传统算法中计算交点的方式,用少量的空间代价避免了计算交点的时间开销。在保证叠加分析算法结果正确性的同时,极大提高了叠加分析算法的效率。实验结果表明,与传统计算模式相比,本文方法在低于10%的额外空间占用率的代价下,使得算法计算的时间减少92. 4%,并且并行算法能够取得较为理想的并行加速比。

Vector spatial overlay analysis is a key operation in the geographic information system (GIS). Recently, it is challenging to provide real-time service, especially for large scale vector spatial data. Therefore, an overlay algorithm based on pre-storing information of intersections is proposed. The structure of intersection for storage and computation integration is designed in vector map overlay algorithm. It can satisfy the storage requirement of low storage space overhead, and meet the computation requirement of intersections access. This work calculates and stores the information of intersections offline. Then, it gets the information of intersections by querying instead of calculating, which is different from the traditional method, effectively reduces the overhead of intersection calculation with less storage cost. This method greatly improves the efficiency of real-time special analysis without impairing the correctness of analysis results. The experiment shows that this work reduces the overlay algorithm time by 92.4%, with the overhead of the storage space less than 10% compared with the traditional algorithm. Besides, the proposed method can effectively improve the speedup and parallel efficiency.