一种异构多核架构快速查询多边形图层间空间关系的方法

目前,空间关系查询中常用的Plane Sweep 算法是一种串行方法,而关于多核CPU的并行查询算法,在面对海量数据查询时,由于CPU核心数及线程数量的限制,其难以满足查询效率需求。针对该问题,本文提出了一种全新的异构多核架构多边形图层间空间关系查询的并行算法。首先,利用STR 树索引过滤不相交的多边形;然后,对过滤后多边形的线段构建四叉树索引,利用CPU+GPU架构并行计算线段的相交以判断多边形环间的拓扑关系;再根据环间的拓扑关系计算多边形间的维度扩展九交模型(DE-9IM)参数值,据此确定多边形间的空间关系;最后,通过实验验证了该算法的准确性和高效性。实验表明,本算法能有效缩短大数据量的空间查询时间。在实验中逐渐增加目标数据集和源数据集多边形的数量,当两数据集都为50 000 个多边形时,以包含关系为例,相比于ArcGIS,本文提出的算法可达到2 倍的加速比。

A Quick Method for Query Spatial Relationships between Polygon Layers Based on Heterogeneous Multi-core Architecture

The commonly used Plane Sweep algorithm in spatial relationship query is a serial algorithm. Some scholars had studied some parallel query algorithms that based on multi-core CPU. However, due to the limitations induced by the number of CPU's core and thread, when dealing with massive data query, these methods are incapable to meet the requirements for query efficiency. To solve this problem, this paper proposes a new parallel algorithm of spatial relationship query between polygon layers based on heterogeneous multi-core architecture. The algorithm used STR-tree index to filter the disjointed polygons first. After the filtration, we built a quadtree index to manage the line segments of the polygons, so that we could quickly get the line segment combination to prepare for computing the intersection situations. Then, the CPU+GPU architecture was adopted to parallel compute the line segments'intersection situation. In details, we firstly put each line segment combination into each thread of GPU to calculate the relevant intersection situation, and the intersection type was counted using CPU. Next, the topological relations between the polygon rings were judged according to the type of line segment intersection, thus the values of DE-9IM parameters between these polygons were calculated based on the topological relations, and accordingly, the spatial relationship between the polygons were determined. At last, the efficiency and accuracy of the algorithm was verified by an experiment. In the experiment, we gradually increased the polygon number of the source layer and the target layer. When both of the two layers had 50000 polygons, here took the Contains relation as an example, we found that the computation time of the parallel algorithm is 15.143s faster than ArcGIS, and the speedup ratio can reach up to 2. In general, the parallel algorithm has more obvious advantages in dealing with higher volumes of data.