# 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  
### Region Segmentation Method Based on the DH Model  
In order to improve the coverage quality of mountainous terrain, to some extent, the coverage path needs to be generated on the basis of conforming to the surface of the 3D map of mountainous terrain. Taking into account the mountainous features, a region segmentation method based on the DH model is proposed.  
Figure 2: Schematic diagram of the simplified 3D map construction of mountainous terrain.  
In virtue of the proposed DH model, it is easy to obtain the surface regions of the simplified mountain model, which are the combinations of the side surface of the frustum and the upper surface of the cone in the DH model. With regard to the flat region excluding the mountain model in the 3D map, it is necessary to divide the flat region into sub-regions, ensuring that the points located in each sub-region have the shortest distance to the sub-region. Conventional segmentation methods are based on auxiliary grids, such as Voronoi diagrams [15; 30] and regular grids [18; 31]. However, these approaches are not applicable to the abovementioned scenarios, since these bottom surfaces of the DH models have been excluded from the flat region in the 3D map.  
Considering that the bottom surface of the DH model is circular, a sub-region segmentation method based on a distance field is adopted. Firstly, by projecting the DH models onto the corresponding XY-plane space, these DH models in the 3D map can be denoted as circles. These projection circles will be used for further sub-region segmentation. The circle center is indicated by \(O\), and the circle radius is denoted by \(R\), as shown in Figure 3. Secondly, for the points located in the flat region excluding these circles of DH models in the projection 2D space, a Cartesian distance between the point and the circle has been adopted to classify the ownership of these points. These points that have the shortest distance to the same circle constitute a sub-region. As is shown in Figure 3, these projection circles are represented by yellow color. Taking the vertex \(P\) located in the flat region as an example, since \(P\) has the shortest distance to the projection circle 3, \(P\) belongs to the sub-region 3. Based on the above procedure, the flat region in the 3D map can be classified into three sub-regions, which are indicated by red color, green color, and blue color, respectively.  
The computational complexity of the proposed region segmentation method based on the DH model mainly focuses on the procedure of distance field calculation. The worst-case computational complexity is \(O\big{(}n^{2}\big{)}\), where \(n\) is the number of pixels on the side of the projection 2D square. Nevertheless, the proposed DH model simplifies the construction process of the 3D map, and the vertices located in the projection circles of DH models need to be excluded and do not participate in the calculation of the distance field. Moreover, once the distance field of the projection 2D square is established, it can still provide the computational basis for the subsequent procedure of the equal-interval circle CPP method, offering a nearly constant time complexity for the circle path generation method.  
Figure 3: Schematic diagram of region segmentation method based on DH model.