## 2 Methodology
### Voronoi Vertex-Based Search Model Based on Weight-Based Heuristic  
A Voronoi diagram is used to divide space into several regions based on the principle of minimum distance. The core idea is that any point within a region should be closer to its corresponding generating object than to any other generating object [38]. In this design, obstacles within the flight layer selected through the adaptive DEM method are utilized as Voronoi objects for vertex generation. The Voronoi vertex generation algorithm proceeds through the following steps. In the corresponding 2D terrain profile of the flight level, obstacles are classified according to their position \(G=\{g_{1},g_{2},\ldots,g_{n}\}\), and Voronoi vertices are generated at loci equidistant to multiple obstacles, which are defined by the following. For any pixel p in the image,  
\[\mathrm{DT}(\mathrm{p})=\min_{q\in G}\|\,p-q\| \tag{7}\]  
where \(\|\,p-q\|\,\) is the Euclidean distance between \(p\) and obstacle pixel \(q\). The vertex \(v\) satisfies  
\[\exists g_{i},g_{j}\subseteq G(i\
eq j):\mathrm{DT}(v,g_{i})=\mathrm{DT} \big{(}v,g_{i}\big{)}\ \wedge\|\
abla\,DT(v)\|\approx 0 \tag{8}\]  
\(v\) is equidistant to at least two obstacles and lies at the local maxima of DT. \(\
abla\mathrm{DT}=\left(\frac{\partial\mathrm{DT}}{\partial x},\frac{\partial \mathrm{DT}}{\partial y}\right)\) is the gradient field at point \((x,y)\). Figure 1: Schematic diagram of the DEM flight stratification model. Candidate vertices, \(V_{candidate}\), are then identified, where the gradient magnitude approaches zero, shown as follows:  
\[V_{candidate}=\left\{p|\|\
abla\,DT(p)\|<\varepsilon\right\}\ \left(\varepsilon\approx 1 0^{-3}\,\right) \tag{9}\]  
Finally, vertices that only retain the local maxima in DT are filtered as follows:  
\[V_{final}=\left\{v\in V_{candidate}|DT(v)>DT(q),\forall q\in N_{8}(v)\right\} \tag{10}\]  
where \(N_{8}(v)\) denotes the 8-neighborhood value of \(v\). The proposed method's advantage in trajectory planning is a result of its ability to generate a trajectory in a two-dimensional plane with distances equal to the obstacles, a feature that is particularly important in mountainous environments. Typically, there are valleys and plains between two mountain peaks, which means that the generated route points will have the maximum distance from the obstacles, thus avoiding collisions and ensuring higher safety in the generated flight path. There are two key elements in the planar image processed using the Voronoi algorithm. One is the set of edges that divides the obstacles, and the other is the set of vertices where these edges intersect. In the field of route planning, the traditional approach is to generate trajectories along the Voronoi edges, followed by turn optimization. This method often results in longer and less-direct routes. We construct a new discrete search space based on the vertices of the Voronoi diagram formed at the flight altitude, assigning weights to all points within this search space and then performing a ranked search. The discrete search space Vec is defined as follows:  
\[\text{Vec}=\left\{\text{start},v_{1},v_{2},\dots v_{p},\text{end}\right\} \tag{11}\]  
Among them, start represents the starting point of the flight plan, end represents the ending point of the flight plan, and \(p\) refers to the number of vertices in the set after Voronoi processing. Based on the current step's starting and ending point information, the heuristic weight values for all vertices, \(v_{p}\), are calculated. Then, all feature points that have no obstacles along the line connecting them to the current starting point are filtered out, and they are subsequently sorted according to their weights. The feature point with the highest weight is selected, and it is connected to the starting point, rendering this vertex the new starting point for the next iteration.