# A UAV Coverage Path Planning Method Based on a Diameter-Height Model for Mountainous Terrain
## 3 UAV Coverage Path Planning Method Based on the DH Model
### Coverage Path Planning Method Based on the DH Model
#### 3.2.3 The Coverage Path Connection Method with Trajectory Minimization and Obstacle Avoidance  
All the coverage paths are generated separately under different patterns but lack connection paths between them. Thus, it is necessary to construct the auxiliary connection lines to convert these paths into a complete coverage trajectory while ensuring the trajectory with the shortest length and obstacle avoidance. It is noted that the equal-interval circle paths consist of closed and open (non-closed) paths; the open path has two endpoints, and either of the two points can serve as the starting point. However, the closed path can be split into an open path at any vertex on the path, and the splitting vertex can serve as both the starting point and the ending point. Apparently, the equal-interval spiral ascent path is an open path. Essentially, connecting these open paths and closed paths with the purpose of shortest path length in this research work can be approximately classified as a typical Traveling Salesman Problem (TSP). The TSP is a classic combinatorial optimization problem, which is significant in operations research and theoretical computer science. Due to the fact that the feasible solution to this problem is the complete arrangement of all vertices, as the number of vertices increases, a combinatorial explosion occurs, making it an NP-complete (NPC) problem. It cannot be denied that in practical applications, approximate solutions can generally meet the requirements of NPC problems. Therefore, the approximation solution is expected to find a near-optimal solution for the TSP, providing a specific percentage of the optimal solution and requiring a reasonable time. In this research, an efficient approximation connection method is proposed. Firstly, by constructing an auxiliary connection path to connect the ending point to the starting point, the open equal-interval spiral path can be transformed into a closed path. The starting point located on the bottom surface of the DH model is selected as the split vertex of the modified closed spiral path. All these paths with circular and spiral types are illustrated as blue lines, as shown in Figure 7. Secondly, a greedy strategy is adopted for connecting these open paths and closed paths. The auxiliary connection path is constructed between these endpoints or split points that have the shortest distance. The above connecting process is repeated until all these open and closed paths are combined into a complete coverage path; then, the coverage path connection algorithm terminates. Thus, a global coverage trajectory with the approximate shortest path length can be generated, as shown in Figure 7. The added auxiliary connection paths are indicated by red lines. Figure 6: Schematic diagram of equal-interval circle path for the flat region in the projection 2D space. During the path connection procedure, it is noted that the added auxiliary connection lines cannot pass through the obstacles in the 3D map, and the obstacle avoidance should be paid attention to, as is shown in Figure 8. The auxiliary connection line is represented by the black dashed line, it passes through an obstacle and connects the starting and ending points, which are indicated by blue points. In virtue of the proposed DH model, a local obstacle avoidance algorithm could be easily implemented. Firstly, the intersection points between the auxiliary connection line and the DH model need to be calculated. Secondly, it is noted that a safe threshold distance \(\delta\) is needed for the UAV to safely fly around the obstacles. The intersection points need to move \(\delta\) distance along the auxiliary connection line in the direction of their respective endpoints. The vertices generated at the new position after movement are indicated as split points, which are termed split point A and split point B. Moreover, according to the intersection points, the cross-section of the DH model can be acquired.