# GPU-Accelerated Algorithm for Polygon Reconstruction
## 3 Algorithm  
In our algorithm, hash table and memory pool technology are employed efficiently to accomplish the polygon construction task. Specifically, linking line segments into polygons involves indexing for the next vertex based on the current one. By utilizing hash tables, we can quickly locate vertices in a high-concurrency environment of the GPU, significantly improving the process efficiency. To minimize hash collisions, we use an adaptive linear hash function, which is defined as follows:  
\[H(x,y)=(x\times length+y)\%\,capacity\]  
In this formula, in addition to the vertex coordinates \((x,y)\), there are two parameters: length and capacity. These parameters are computed based on the segment set during the initial stage of the algorithm. The parameter length refers to the length of the minimum bounding rectangle that contains all the vertices in the segment set, while capacity refers to the size of the hash table, which is typically set to 1.5 times the number of segments to keep the hash table's load factor around 0.7. This hash function is designed to minimize the performance loss caused by hash collisions, even in cases where the vertex coordinate distribution is extremely uneven. Since frequent memory allocation in a GPU environment incurs substantial computational overhead, we opted for pre-allocated continuous memory spaces to store the final result. Given that the number of vertices in each polygon is unknown at runtime, we utilized memory pool technology to manage memory more effectively. The memory pool enables flexible allocation and deallocation of space within a fixed memory block, avoiding the performance bottleneck caused by frequent memory allocation, while ensuring efficient memory utilization and orderly result storage. The memory layout used to store the algorithm output is divided into three parts:  
1. **Polygon header information**: The first section contains the header information for each polygon, which includes metadata related to the outer contour and its corresponding inner contours (holes). The header data of the inner contours are stored immediately after the header data of the outer contours they are enclosed within, ensuring logical continuity and easy access for traversal or further processing. 2. **Redundant space**: Since the number of polygons in the line segment set cannot be predicted in advance, memory is allocated based on the maximum estimated number of polygons. This conservative allocation strategy can prevent insufficient memory during execution but may cause some memory to be unused. A more aggressive allocation strategy can be adopted based on actual application scenarios. 3. **Vertex information**: The final section of the memory stores the vertex data for all polygons. The vertices of the outer contour are arranged in a counterclockwise (CCW) order, while the vertices of the inner contours (holes) are arranged in a clockwise (CW) order. As illustrated in Figure 2, the second row depicts the overall memory layout, including the header information and vertex coordinates for all polygons. The first row provides an example of the header information of a polygon, while the third row illustrates the corresponding vertex data of a polygon. The meaning of each parameter in the polygon header information is as follows:  
1. Index: The index of the polygon. 2. Number of vertices: The total count of vertices for the polygon. 3. Hole flag: Indicates whether the polygon is an inner contour. A value of 1 denotes that the polygon is an inner contour, while 0 indicates it is an outer contour. 4. Memory offset: The starting position of the polygon's vertex data in memory. This value allows quick access to the corresponding vertex data. 5. Bounding box \((x_{1},y_{1},x_{2},y_{2})\): The minimum bounding box of the polygon, where \(x1\) and \(y1\) represent the coordinates of the lower-left corner and \(x2\) and \(y2\) represent the coordinates of the upper-right corner. These coordinates help quickly determine the spatial position and size of the polygon.