## 3 Algorithm Design: Hybrid Voronoi-A* Framework and Pseudocode
Path Planning Success Rate: The Voronoi-A* fusion algorithm successfully avoided obstacles and had no collisions in all test scenarios, while the APF algorithm failed to handle three-dimensional obstacles, resulting in crashes in mountainous and hilly terrain (success rate of only 33%). The RRT algorithm exhibited unstable performance, with planning failures occurring. **Path Efficiency:**

1. Path Length: The Voronoi-A* path length is shorter than that of the traditional A* algorithm. For example, in mountainous terrain, the length is reduced by 0.5% (373.78 vs. 375.56 units), and in canyon terrain, it remains more efficient (132.12 vs. 134.28 units). 2. Number of Waypoints: The number of waypoints is reduced by an average of 92% compared to the A* algorithm (for example, in mountainous terrain, only 17 points are needed, whereas the A* algorithm requires 349 points), significantly reducing flight complexity. **Computational Efficiency**:

The path planning time of Voronoi-A* is significantly superior to that of all the comparison algorithms:

1. Voronoi-A* has a faster average of 96.1% compared to the A* algorithm (e.g., in mountainous terrain, 3.36 s vs. 85.14 s). 2. It is 7.2 times faster than the RRT algorithm in canyon terrain (0.81 s vs. 5.88 \(\pm\) 3.47 s). 3. The APF algorithm is fast (2.41 s) in open areas (such as canyons), but it completely fails in complex environments with dense obstacles. **Three-Dimensional Adaptability:**

Voronoi-A* enables 3D obstacle avoidance through multi-layered flights, whereas APF and RRT only support 2D planning in certain scenarios. For example, in mountainous terrain, APF fails to cross peaks, causing the path to collide with obstacles, while Voronoi-A* successfully navigates around them in 3D. In summary, the Voronoi-A* fusion algorithm, by combining the hierarchical strategy of Voronoi diagrams with the A* heuristic search, demonstrates significant advantages in path planning success rates, path optimality, computational efficiency, and three-dimensional obstacle avoidance. It provides an efficient and reliable solution for drone path planning in complex mountainous environments. ## 5 Conclusions

This study proposes a UAV trajectory planning method that is suitable for complex terrain. The method adopts a combined strategy comprising \"Voronoi vertex-based quick \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & **Voronoi–A* & A* & APF & RRT \\ \hline
**Success of Planning** & **100\%** & 100\% & 33\% & 96.7\% \\
**Average Number of Waypoints** & **8** & 207 & 284 & 85 \\
**Average Time (Seconds)** & **1.66** & 30.73 & 3.01 & 60.35 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Comprehensive performance comparison table (average). trajectory generation + A* supplementary expansion of the trajectory.\" Specifically, the algorithm first simplifies 3D route planning hierarchically using an adaptive DEM stratification strategy. Then, it uses the Voronoi vertex set within the flight plane as a sparse point network and employs a greedy heuristic search strategy for rapid trajectory planning, attempting to cross obstacles through backup planes. For obstacles that cannot be avoided, the traditional A* algorithm is used to locally connect 2D trajectories at the flight level. Finally, interpolation search is used to optimize the UAV's flight trajectory. In the three specifically designed simulation scenarios, this combined algorithm significantly outperforms traditional single algorithms in terms of path planning success rates, computational efficiency, and adaptability to 3D terrain. It should be noted that the Voronoi-A* fusion algorithm can quickly generate suitable and flyable paths by employing a global sparse search strategy via greedy optimization.