Spark框架下矢量多边形求交算法研究

Research on vector polygon intersection algorithm in Spark framework

提出一种分布式内存计算框架Spark下的矢量多边形求交算法,解决了大数据环境下并行矢量多边形求交计算过程中网络数据传输成本高、冗余计算量大的问题。该算法根据空间填充曲线构建空间网格分区,并利用多边形最小外包矩形(MBR)进行网格填充,以传输MBR代替传统算法中直接传输多边形几何体的过程,减少了算法的网络数据传输量。针对复杂多边形跨越多个网格分区的场景,提出一种跨区数据交点定位策略,从而消除跨区多边形的冗余计算。实验结果表明,本文方法能够显著提高并行矢量多边形求交算法的计算效率。

A vector polygon intersection algorithm in Spark framework is proposed,which is a distributed memory computing framework. It solves the problems of current parallel polygon intersection algorithm,such as high cost of network data transmission and redundant computation. Firstly,a spatial grid partitioning strategy based on space filling curves and a grid filling method with polygon＇s minimum bounding rectangle（ MBR） are introduced to reduce the network data transmission by transmitting MBR instead of polygon. Secondly,during the phase of data distribution,aiming at the scenario of complicated polygon which cross several grids,a polygon intersection location approach is adopted to eliminate the redundant computation of cross-district polygon. The results of the comprehensive experiments show that the proposed method can significantly improve the efficiency of the vector polygon intersection algorithm.