# Research on Automatic Generation of Park Road Network Based on Skeleton Algorithm
## 4 Road Network Generation Method
### Polygon Simplification Based on Semantic Information  
The integration of skeleton algorithms into road design tasks holds significant potential, but also comes with drawbacks. The points generated by the skeleton algorithm prioritize graphic features, potentially leading to an excessive number of points that do not align with actual road requirements. Therefore, it is essential to simplify these points using appropriate methods. In the context of vector data, polygons are formed by sequentially connected points, and the quantity of these points often dictates the precision of the polygon. However, an excessive number of points may lead to a proliferation of redundant roads after applying the skeleton algorithm (Figure 3a). On the other hand, too few points can result in significant deviation from reality, producing roads that inadequately capture the morphological variations in natural features. Therefore, prior to employing the skeleton algorithm, it is crucial to appropriately simplify the polygons in order to align more closely with actuality in terms of both generated road network morphology and sub-skeleton distribution. For polygon simplification, this study will utilize the well-established Douglas-Peucker simplification algorithm [38; 39]. The Douglas-Peucker algorithm is a widely employed digital curve simplification method that effectively reduces complex curves to approximate forms with minimal points, while preserving the fundamental geometric shape and features of the original curve. It is straightforward to implement [40; 41] and adaptable for use in various programming languages and platforms. This algorithm finds extensive application in map digitization, GIS modeling, and computer graphics, and can be seamlessly integrated with graph skeleton algorithms. The Douglas-Peucker simplification algorithm primarily relies on geometric scale to decide whether a point should be retained or discarded, without considering specific semantic information associated with points on the polygon. However, during road design processes, these specific points often connect essential roads and therefore should consistently be preserved throughout polygon simplification procedures. Consequently, this study has adapted the Douglas-Peucker simplification algorithm to ensure that both geometric scale and semantic information are taken into account during polygon simplification in the following steps:  
Step 1: Input the polygon coordinates, semantic point set, and deviation threshold \(\varepsilon\). Step 2: The special points with semantic information are projected onto the polygon based on their coordinates, thereby becoming part of the point set on the polygon and forming a new point set as follows:  
\[\mathrm{P}=\left\{\mathrm{P}_{1}\left(\mathrm{x}^{1},\mathrm{y}^{1}\right), \mathrm{P}_{2}\left(\mathrm{x}^{2},\mathrm{y}^{2}\right),\dots,\mathrm{P}_{n} \left(\mathrm{x}_{n},\mathrm{y}_{n}\right)\left|\mathrm{n}\in\mathrm{N}\right\}\right\} \tag{1}\]Step 3: For each point on the polygon, add a Boolean attribute reserved that is set to true if the point belongs to the new semantic points created in step 2, and false otherwise. The new point set is represented as follows:  
\[\text{P}=\left\{ \begin{aligned} &\text{P}_{1}(\text{x}_{1},\text{y}_{1}, \text{reserved}_{1}),\text{P}_{2}(\text{x}_{2},\text{y}_{2},\text{reserved}_{2 }),\\ &\ldots,\text{P}_{n}(\text{x}_{n},\text{y}_{n},\text{reserved}_{n })\mid\text{n}\in\text{N}\end{aligned} \right\} \tag{2}\]  
Step 4: The lengths of the line segments between each pair of points on the polygon are calculated, and the longest segment is selected as separator l. And l divides the polygon into two segments, denoted as \(\text{L}_{1}(\text{l})\) and \(\text{L}_{2}(\text{l})\), with the starting and ending points of separator l marked as \(\text{p}_{\text{s}}\) and \(\text{p}_{\text{e}}\), respectively, i.e., \(\text{l}(\text{p}_{\text{s}},\text{P}_{\text{e}})\).