Content area
Polygon overlay operations are used for various purposes such as GIS searches and queries, VLSI, and basic geometric operations of intersection, union and difference. Performing the polygon overlay operation on complex polygons can be computationally intensive. This operation is even more computationally intensive when the polygon overlay operation is performed on a large dataset of polygons, as in GIS and VLSI scenarios. This paper presents two parallel algorithms implemented on the GPU that focus on the active list portion of the traditional serial plane sweep algorithm. The first algorithm uses a single block of threads to simulate the active list data structure in hardware; this algorithm is slow due to GPU thread block size limitations and synchronization points, but demonstrates favorable time complexity. The second algorithm uses dynamic parallelism to remove synchronization and scales to utilize available GPU hardware (single GPU). Experiments on both synthetic and real world data sets are performed. The results show improvement in execution time and low memory usage compared with algorithms presented by Bentley and Ottmann [BOa], Franklin et al [FNK+], Audet et al [AAMA], and Paudel and Puri [PP]. Speedups of up to 38.8x over the serial sweep line algorithm on real world data are achieved.