# GPU-Accelerated Algorithm for Polygon Reconstruction
## 3 Algorithm
This structured memory layout design ensures both efficient organization and quick data access. Even without using dynamic array containers such as _std::vector_, the algorithm can efficiently manage and access polygon data. To avoid running out of memory pool space, we need to estimate the amount of space required to store the results. The space needed to store vertex information is comparable to the size of the segment set, while the space required for storing polygon header data depends on the number of polygons in the segment set. With \(n\) segments, at most \(n/3\) polygons can be formed. Therefore, we reserve space for polygon header data based on \(n/3\) polygons, using redundant space to prevent memory pool overflow. The detailed steps of the algorithm are presented as follows:  
1. Hash table creation on GPU: Create a hash table on the GPU, where both the keys and values are vertex types: \[v=\{x,y\}\in R^{2}\] All line segment data are transferred to the global memory of the GPU. The start and end points of each segment are inserted into the hash table as key-value pairs in parallel. For example, for line segment \(S=\{v_{i}^{1},v_{i}^{2}\}\), the key-value pair inserted into the hash table is as follows: \[key=v_{i}^{1}\] \[value=v_{i}^{2}\]
2. Polygon construction: After all key-value pairs are inserted, a unique starting vertex \(v_{1}(x_{1},y_{1})\) is assigned to each thread. A common practice is to use the thread ID as an index to select the starting point from the set of line segments. All threads then search the hash table with the starting point as the key, retrieve the corresponding value, and repeat this process until the value equals the initial starting point, thus constructing a complete polygon. This search or query process consists of two rounds. Figure 2: Memory layout for storing results. First round: The threads record the number of vertices in the polygon. Since we cannot directly determine whether two line segments belong to the same polygon, in order to avoid multiple threads constructing the same polygon, we require that during the hash search process, the starting point is always the vertex on the rightmost (or upper right) side. If, during the search process, a vertex is found to be located to the upper right of the starting point, the search is stopped, the result is marked as invalid, and the data for the current thread are discarded. The vertex sequence \(P=\{v_{1},v_{2},v_{3},\ldots,v_{n}\}\) must satisfy the following conditions: \[x_{1}>=max(x_{2},x_{3},...,x_{n})\] \[and\] \[\{\text{if}\,x_{1}=max(x_{2},x_{3},\ldots,x_{n})\] \[\text{then}\,y_{1}=max(y_{2},y_{3},...,y_{n})\}\] (b) Second round: The threads with a valid result will conduct a second round of querying. During this process, the thread will apply for space from the pre-set memory pool to store polygon header information and polygon vertex data. 3. Determining polygon orientation: After completing the above steps, the starting point of each polygon is the rightmost (or upper-right) vertex, which is often a vertex of the polygon's convex hull. Using this vertex and the two adjacent vertices, the polygon's orientation (CW or CCW) can be determined. If the orientation is clockwise, the polygon is classified as an inner contour, otherwise, it is classified as an outer contour. 4. Outer-inner contour matching: To associate inner contours with their outer contours, the algorithm first sorts the polygon headers by the left x-coordinate of the polygon's bounding box. For each inner contour, its corresponding outer contour must appear before it in this sorted order. Each thread is assigned an inner contour and searches backward through the header data for an outer contour candidate whose bounding box fully encloses that of the inner contour. Once a candidate is found, the ray-casting method is used to confirm whether the outer contour encloses the inner contour. The outer contour's index is then recorded in the inner contour's header. 5.