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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-01-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/15/3/1111 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850068105405923328 |
|---|---|
| author | Ruian Ji Zhirui Niu Lan Chen |
| author_facet | Ruian Ji Zhirui Niu Lan Chen |
| author_sort | Ruian Ji |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-b092575a0bcd4ec9802a67de0bdbb5ca |
| institution | DOAJ |
| issn | 2076-3417 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj-art-b092575a0bcd4ec9802a67de0bdbb5ca2025-08-20T02:48:09ZengMDPI AGApplied Sciences2076-34172025-01-01153111110.3390/app15031111GPU-Accelerated Algorithm for Polygon ReconstructionRuian Ji0Zhirui Niu1Lan Chen2Institute of Microelectronics of the Chinese Academy of Sciences, Beijing 100029, ChinaInstitute of Microelectronics of the Chinese Academy of Sciences, Beijing 100029, ChinaInstitute of Microelectronics of the Chinese Academy of Sciences, Beijing 100029, ChinaPolygon 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.https://www.mdpi.com/2076-3417/15/3/1111computational geometrypolygon reconstructionpolygon clippingGPU |
| spellingShingle | Ruian Ji Zhirui Niu Lan Chen GPU-Accelerated Algorithm for Polygon Reconstruction Applied Sciences computational geometry polygon reconstruction polygon clipping GPU |
| title | GPU-Accelerated Algorithm for Polygon Reconstruction |
| title_full | GPU-Accelerated Algorithm for Polygon Reconstruction |
| title_fullStr | GPU-Accelerated Algorithm for Polygon Reconstruction |
| title_full_unstemmed | GPU-Accelerated Algorithm for Polygon Reconstruction |
| title_short | GPU-Accelerated Algorithm for Polygon Reconstruction |
| title_sort | gpu accelerated algorithm for polygon reconstruction |
| topic | computational geometry polygon reconstruction polygon clipping GPU |
| url | https://www.mdpi.com/2076-3417/15/3/1111 |
| work_keys_str_mv | AT ruianji gpuacceleratedalgorithmforpolygonreconstruction AT zhiruiniu gpuacceleratedalgorithmforpolygonreconstruction AT lanchen gpuacceleratedalgorithmforpolygonreconstruction |