GPU-Accelerated Algorithm for Polygon Reconstruction

Polygon reconstruction is widely used across various fields. Although the current polygon reconstruction algorithms have achieved near-linear time complexity, they still fail to meet the speed demands imposed by the exponential growth in polygon numbers. The development of GPU technology provides a promising solution to this issue. This paper proposes a GPU-based algorithm that leverages hash tables and memory pools to transform the polygon reconstruction problem into an efficiently parallelizable task. Experimental results on Nvidia RTX 2080Ti demonstrate that the new algorithm achieves 17× and 46× speedups on Manhattan and non-Manhattan polygon test sets, respectively. Compared to traditional CPU algorithms, the new algorithm significantly improves processing speeds, especially when handling layouts with complex polygons. It demonstrates strong scalability and performance advantages, providing crucial support for enhancing the overall efficiency of CAD tools.