Abstract: Simple feature model-based non-weighted polygon overlapping analysis operations include eight basic tools: intersection, difference, merge, symmetrical difference, union, update, identity, and spatial join. It is assumed that the determination of the "one-to-many" or "many-to-many" mapping relationships between polygons of the two overlapping layers is the primary prerequisite to the implementation of parallel polygon overlay toolset at the feature layer level. Polygon difference, intersection, identity, update, and spatial join algorithms must address the "one-to-many" mapping relationships between polygons of the overlapping layers. However, the "many-to-many" relationships must be handled by polygon merge, symmetrical difference, and union algorithms. In this research, we analyzed the differences and similarities among the parallel implementation approaches and optimization methods of the eight polygon overlapping tools from the perspective of data parallelism with the OpenMP parallel programming model. We proposed an improved group-relation-minimizing data partition method to realize complex data decomposition without geometry cutting and sewing, and adopted a vertex number indicator-based strategy for load balancing, and several optimization approaches, including the method of avoiding potential bottleneck in polygon merging, strategy for addressing the defect in polygon symmetrical differencing using the XOR operator of the Vatti polygon clipping algorithm, and the strategies of pre-filtering of features with R-tree and bulk loading of structural stored vector data in MySQL. We developed and implemented the parallel polygon overlapping toolset by systematically summarizing the applicative data decomposition method, characters of overlay operations, the Vatti polygon clipping algorithm, load balancing and parallel schedule strategies. The logical flow of parallel polygon union algorithm was introduced as an example to describe the general process of designing parallel polygon overlapping tools. Parallel overlapping case study was also conducted to analyze the effectiveness of the implementation and optimization methods. The experimental results show that the improved group-relation-minimizing data partition method can bring approximately 92% parallel acceleration and more parallel robustness for polygon union; different expected group size specified in the data division method proposed in this research can lead to different parallel speedup benchmarks; the vertex-number based load balancing strategy can give the parallel difference tool about 21% performance improvement; the two-way merge algorithm applied in the parallel merge tool can address the potential performance bottleneck; the dynamic schedule strategy of OpenMP can bring higher speedup than the static and guided schedule strategies; the pre-filtering approach can bring more than 20-fold acceleration for parallel polygon difference; the bulk loading strategy of structural stored vector data can effectively reduce the performance loss due to the disk I/O. The implementation approaches and optimization methods introduced in this study show different applicable features on the developing of the eight overlapping tools. The methods and strategies introduced above can be potential alternatives when launching similar parallelization tasks of other spatial analysis algorithms. This research not only provided theoretical basis and guidance of methodologies for the design and development of parallel polygon overlapping tools at the feature layer level in the multi-core environment, but also presented important practical significance in improving the system resource utilization and computational efficiency of spatial analyses for massive personal and low-cost GIS applications.

Key words: data partition, load balance, OpenMP, parallel optimization, parallel polygon overlapping, task schedule