# GPU-Accelerated Algorithm for Polygon Reconstruction
## 5 Experiment
### Result  
Tables 1-4 present the test results of our algorithm on different polygon datasets. \"Polygon Number\" refers to the number of polygons in the dataset, and \"Segment Number\" is the number of line segments that make up these polygons. The third and fourth columns show the time (in milliseconds) required by the traditional CPU algorithm and our GPU  
Figure 5: Test polygons that served as the source of line segments used in the experiments. (**a**) A slice of the Manhattan test set. (**b**) A slice of the non-Manhattan test set. algorithm, respectively, to process these line segments. The final column represents the speedup achieved by our algorithm. The results show that, compared with the CPU-based algorithm, the GPU-based algorithm achieves an average speedup of 46.1\(\times\) on the non-Manhattan test set without holes, and 45.2\(\times\) on the non-Manhattan test set with holes. It achieves an average speedup of 17.9\(\times\) on the Manhattan test set without holes and 16.8\(\times\) on the Manhattan test set with holes. Overall, the proposed GPU algorithm demonstrates substantial performance improvements on the RTX 2080 Ti. The new algorithm exhibits varying speedup ratios when processing Manhattan and non-Manhattan polygons, which can be attributed to the characteristics of both the polygons and the algorithm. Compared to the CPU-based algorithm, the performance advantage of the proposed algorithm mainly lies in the line segment connection process, particularly in the hash table search. Apart from redundant searches caused by uncertain polygon starting points, this process is well-suited for large-scale parallel computing devices such as GPUs. Therefore, the GPU-based algorithm performs better on test sets where a single polygon contains more vertices. In the non-Manhattan test sets, with and without holes, the average number of line segments per polygon is 144.2 and 110.6, respectively, significantly higher \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Polygon** & **Segment** & **Boost Polygon** & **Our Algorithm** & \\
**Number** & **Number** & **on CPU (ms)** & **on GPU (ms)** & **Speedup** \\ \hline
27,000 & 3,894,300 & 2592.9 & 51.3 & 50.5 \\
36,750 & 5,300,575 & 3605.4 & 77.8 & 46.3 \\
48,000 & 6,923,200 & 4674.8 & 97.2 & 48.1 \\
60,750 & 8,762,175 & 5932.4 & 125.7 & 47.2 \\
75,000 & 10,817,500 & 7269.9 & 157.9 & 46.0 \\
90,750 & 13,089,175 & 8810.0 & 205.3 & 42.9 \\
108,000 & 15,577,200 & 10,689.2 & 257.0 & 41.6 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Test results for non-Manhattan polygons without holes. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Polygon** & **Segment** & **Boost Polygon** & **Our Algorithm** & \\
**Number** & **Number** & **on CPU (ms)** & **on GPU (ms)** & **Speedup** \\ \hline
42,300 & 4,679,100 & 3227.4 & 64.4 & 50.1 \\
57,575 & 6,368,775 & 4398.9 & 96.5 & 45.6 \\
75,200 & 8,318,400 & 5701.5 & 140.0 & 40.7 \\
95,175 & 1,052,797 & 7264.7 & 153.6 & 47.3 \\
117,500 & 12,997,500 & 8865.1 & 223.7 & 39.6 \\
142,175 & 15,726,975 & 10,848.0 & 228.0 & 47.6 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Test results for non-Manhattan polygons with holes. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Polygon** & **Segment** & **Boost Polygon** & **Our Algorithm** & \\
**Number** & **Number** & **on CPU (ms)** & **on GPU (ms)** & **Speedup** \\ \hline
250,000 & 4,500,000 & 1069.8 & 63.4 & 16.9 \\
291,600 & 5,248,800 & 1247.5 & 70.8 & 17.6 \\
336,400 & 6,055,200 & 1515.2 & 80.4 & 18.8 \\
384,400 & 6,919,200 & 1627.2 & 91.0 & 17.9 \\
435,600 & 7,840,800 & 1815.2 & 1 than the average number of line segments per polygon in the Manhattan test sets, which is 18 and 6.4, respectively. When processing polygons with holes, our algorithm exhibits slightly worse performance compared to polygons without holes, given the same number of line segments. This is due to the memory layout used to store the results. Each polygon's header information must be recorded in the results.