## 3 Algorithm Design: Hybrid Voronoi-A* Framework and Pseudocode
The top-left corner of the top-down view serves as the coordinate's origin, and the bottom-left corner of the 3D view also serves as the coordinate's origin. Therefore, the sum of the Y-coordinate values of

Figure 6: The flowchart of the proposed approach (Voronoi-A*). the same point in both views corresponds to the image's width. The simulation results of five algorithms under this terrain are as follows. 1. The planning path under the Voronoi-A* fusion algorithm simulation environment, as shown in Figure 1, features a UAV flight path with DEM cross-layer flights, enabling 3D obstacle traversal and successfully overcoming a mountain peak obstacle. This scenario's planning process includes all steps, such as Voronoi vertex selection, A* search expansion, cross-layer flight, and interpolation optimization. Figure 6(a) illustrates the first step of the algorithm's search for Voronoi vertices, while Figure 6(b) describes the algorithm's rapid path search from the starting point to the endpoint. In this step, an A* expansion search is performed after crossing layers, resulting in the unoptimized search path. The blue line indicates a climb during this segment of the flight, the red * marks the start of the flight, and the green * marks the endpoint. Figure 6(c) shows the optimized flight path after interpolation optimization. Figure 6(d) presents the final 3D flight path. 2. The APF algorithm's planned path in the simulation environment is shown in Figure 8, where the algorithm's attraction coefficient is 15, the repulsion coefficient is 5, and the influence radius is 10 pixels. Due to the potential field balance issue in complex environments, it is clearly evident that the aircraft's flight path directly passes through high mountains, resulting in a crash. Therefore, in terrains with complex topography and numerous three-dimensional obstacles, this method is not feasible. 3. The planned path of the RRT algorithm in the simulation environment is shown in Figure 9. Compared to the Voronoi-A* fusion algorithm, the path is noticeably more winding and complex. Additionally, due to the introduction of random factors, the consistency of the path planning is poor each time. 4. The planned path of the A* algorithm in the simulation environment is shown in Figure 10. It can be observed that the A* algorithm successfully plans a path that bypasses obstacles. In comparison to Figure 7, due to the influence of the A* search range, the number of planned path points increases, which results in higher computational complexity, longer calculation times, and a significantly longer total flight distance. Figure 7: Voronoi–A* algorithm simulation diagram for scene 1. The test results of the four algorithms in this scenario, in addition to the start point (5, 177) and end point (351, 51), are compared, with statistics shown in Table 2. \(\pm\) represents the average value of the statistical results of 20 tests carried out for each algorithm. Figure 11a shows 2D simulation results, with four algorithms' paths color-coded, while Figure 11b presents the statistical analysis results of 20 RRT trials, comparing time, waypoint count, and path length against their respective averages. The green line represents \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Method** & **Collision** & **Number of Waypoints** & **Length (500 m)** & **Time (S)** \\ \hline Voronoi-A* & No & 17 & 373.78 & 3.36 \(\pm\) 1.67 \\ A* & No & 349 & 375.56 & 85.14 \(\pm\) 12.21 \\ APF & Yes & 469 & 362.80 & 5.11 \(\pm\) 1.3 \\ RRT & No & 143 \(\pm\) 20 & 524.54 \(\pm\) 77 & 99.21 \(\pm\) 86.76 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Mountainous terrain test comparison chart. Figure 8: APF algorithm simulation diagram for scene 1. Figure 10: A* algorithm simulation diagram for scene 1. Figure 9: RRT algorithm simulation diagram for scene 1.

the self-developed Voronoi-A* fusion algorithm, the red line represents the A* algorithm, the magenta line represents the APF algorithm, and the blue line represents the RRT algorithm.