## 2 Methodology
### Optimization of Flight Path  
The standard process for general UAV flight path planning typically consists of the following three steps: (1) modeling the flight environment space, (2) connecting the starting point and endpoint using a routing algorithm to form an initial flight path, and (3) further optimizing the initial flight path [40]. 1. Interpolation Optimization of Flight Path  
The fast search based on Voronoi vertices is a sparse search process with the advantage of high search speeds; this is highly practical when the UAV has sufficient endurance. However, the disadvantage is that it cannot compare with heuristic algorithms in generating flight paths with optimization goals. However, the waypoints based on the fast search model still have significant optimization potential. The flight path generated after the search is as follows:  
\[P=\bigcup_{i=1}^{n}\overline{P_{i-1}P_{i}} \tag{14}\]  
where \(\overline{P_{i-1}P_{i}}\) is the line segment connecting the points \(P_{i-1}\) and \(P_{i}\). Fixed-distance interpolation is performed on this segment to generate a new set of interpolation points, as follows:  
\[Q_{i}=\big{\{}q_{i,k}=P_{i-1}+k\cdot\delta\cdot u_{i}\big{|}k=0,1,\ldots\ldots.m_{i}\big{\}} \tag{15}\]  
where \(u_{i}=\frac{P_{i}-P_{i-1}}{\|P_{i}-P_{i-1}\|}\) represents the direction of the unit vector, and \(m_{i}=\left\lfloor\frac{\|P_{i}-P_{i-1}\|}{\delta}\right\rfloor\) represents the number of points after the interpolation of the line segment. Figure 4: Schematic of flight segment connections using the A* algorithm. The sequence of the flight path segment \(Q_{i}\) is followed to detect the point \(q_{i,k}\) in the area. If there is no collision in \(\overline{q_{i,k}P_{i+1}}\), then point \(q_{i,k}\) is added to list \(P^{\prime}\). If no \(q_{i,k}\) values meet the conditions, then \(P_{i}\) is retained and added to the \(P^{\prime}\) list. The value of \(P^{\prime}_{i}\) is updated to \(P_{i}\), and interpolation searches are continually performed on \(\overline{P_{i}P_{i+1}}\) until the endpoint \(P_{n}\) is added to \(P^{\prime}\). Compared to the initial flight path, this optimization method allows for the reconstruction of the path, ensuring that the new trajectory connects both the starting and ending points, with each segment of the sub-path avoiding obstacles; moreover, the total path is as short as possible, as illustrated in Figure 5.  
Optimization of the Position of Voronoi Vertices  
In theory, the vertices obtained after Voronoi division are the farthest from obstacles in the horizontal space, providing a higher safety margin. However, this approach does not take into account the altitude relative to the ground when UAVs fly in complex mountainous environments. Height measurements can be carried out at the vertices and their neighbors using planar detection, and the point with the largest height margin can be selected as the optimized point for use. The vertex optimization method involves generating a candidate set \(P_{ij}\) for each initial vertex \(P_{i}\in Vec\) by performing a plane rasterization process. \[P_{ij}=\left\{P_{ij}\right\}\left|\,j\in[1,N],N=round((R\div L)^{2})\right\} \tag{16}\]  
Here, \(R\) represents the neighborhood search radius, \(L\) represents the elevation data scale, and \(N\) represents the number of search points. The safety margin for elevation is calculated at each point in the search area as follows:  
\[\Delta h_{ij}=\mathrm{h}-h_{ij} \tag{17}\]  
where \(h_{ij}\) is the height value corresponding to the point in the DEM, while h denotes the height of the current flight plane. The principle of safety margin maximization is adopted as follows:  
\[\mathrm{P}^{\prime}_{i}=\max(\Delta h_{ij}),\forall j\in\left\{j\middle|\Delta h _{ij}>0\right\} \tag{18}\]  
The optimized vertices are then updated to the new Voronoi vertex set. By establishing the vertex optimization mechanism, the altitude margin for drone flights is significantly improved, making the flight path more reliable.