# Research on Automatic Generation of Park Road Network Based on Skeleton Algorithm
## 4 Road Network Generation Method
### Convex Hull Operation Based on Semantic Information  
Within the park, certain functional or landscape zones have relatively small areas and encompass multiple distinct sub-regions in close proximity to each other. Each sub-region is typically represented as an individual polygon in vector data, such as a cluster of buildings or vegetation. Introducing the polygon groups representing these sub-regions directly into the skeletonization algorithm results in the formation of impractical pathways within adjacent polygons, significantly disrupting the connectivity of the road network (Figure 4a). To address the issue of appeal, this study introduces the convex hull operation [(42)]. The convex hull operation originates from graphics and serves as a practical geometric calculation tool. It fully preserves the geometric shape and boundary features of the original point set and possesses characteristics such as simple output, efficient calculation, and a strong visualization effect. Widely utilized in computer graphics [(43)] and GIS [(44)], it plays a crucial role in analyzing various graphics, images, and spatial data. The classical convex hull algorithms encompass the Gift Wrapping Algorithm [(45)], [PERSON]'s algorithm [(46)], the Monotone Chain Algorithm [(47)], and the Quick Hull Algorithm [(48)], among others. The Gift Wrapping Algorithm was published by [PERSON] in 1973. [PERSON]'s algorithm is a sequential algorithm used to determine the convex hull of a set of n points in the plane (n \(\geq\) 3). The Quick Hull Algorithm is based on a divide-and-conquer strategy and is very similar to quick sort, which divides the problem into two sub-problems and discards some of the points in the given set as interior points, then concentrating on the remaining points. The selection of the algorithm is contingent upon factors like the quantity of points, the distribution of the points, as well as the requisite time and space complexity. For instance, the Gift Wrapping and Graham Scan algorithms are straightforward to implement and perform effectively for small- to medium-sized datasets, whereas the Divide and Conquer and Chan's Algorithm are more efficacious for larger datasets. This study employs the scikit-geometry library for calculating the convex hull of geometric figures. Scikit-geometry ([[https://scikit-geometry.github.io/scikit-geometry/skeleton.html](https://scikit-geometry.github.io/scikit-geometry/skeleton.html)]([https://scikit-geometry.github.io/scikit-geometry/skeleton.html](https://scikit-geometry.github.io/scikit-geometry/skeleton.html)) (accessed on  
Figure 4: Skeleton graph before and after convex hull operation. (**a**) Road network generated before convex hull simplification; (**b**) road network generated after convex hull simplification. 27 November 2023)) is a library founded on SciPy 1.10.1, offering interfaces for geometric operations, including the computation of convex hulls. The convex hull operation connects the outermost points of the point set to form a convex polygon. Substituting the original polygon group with the convex polygon in skeleton calculation can effectively prevent the generation of primary skeleton branches within the polygon group and produce secondary skeleton branches that align with practical requirements. However, this operation may also exclude points directly connected to major roads and possessing specific significance; therefore, these semantic points should be represented on the formed convex polygon (Figure 4b), akin to handling semantic points in polygon simplification algorithms.