# Large-Area Coverage Path Planning Method Based on Vehicle-UAV Collaboration
## 3 Coverage Path Planning Method Based on Vehicle-UAV Collaboration
### Coverage Area Segmentation Method Based on Dynamic Adjustment  
In this subsection, a coverage area segmentation method based on dynamic adjustment is presented for dividing the large area into sub-areas with approximately equal sizes. The core idea of dynamic adjustment is to determine the positions of supply points through multiple adjustments, and all sub-areas are repeatedly adjusted to ensure that the points within each sub-area have a shorter distance to the corresponding supply point. The coverage area segmentation method starts from the abovementioned regular hexagons. In the proposed coverage area segmentation method, the effectiveness of the hexagons is mainly determined based on the position of the center point. If the center point is located inside the polygon \(C\) of coverage area, then the hexagonal unit is valid, and vice versa: the hexagonal unit is invalid if the center point is located outside the polygon \(C\), as shown in Figure 4.  
These valid hexagons are retained, while invalid hexagons need to be removed and their adjacent hexagonal units need to be modified. Firstly, the edges of invalid hexagons are removed. For these valid but incomplete hexagons, if one endpoint in the remaining edge has no connection with other edge, the edge is called a single independent edge, and this edge needs to be extended to intersect with the polygon \(C\) to form a new edge. Thus, the extended edges, the partial polygon contour of \(C\) and the remaining edges together form the boundary of the modified hexagonal unit. Through the above process, the segmentation of the large coverage area is completed, and sub-areas and their corresponding contours can be generated, as shown in Figure 5.  
Figure 4: Schematic of hexagonal grid coverage results. Figure 3: Schematic diagram of a regular hexagon. Owing to the modification of incomplete hexagons, the original center also needs to be modified. The gravity position of these modified sub-areas is used to act as the new center point, according to (5), which is the classical polygon gravity formula. \[ \begin{cases}C_{x}=\frac{\sum P_{xy}}{n}\\ C_{y}=\frac{\sum P_{yy}}{n}\end{cases}  \tag{5}\]  
where \((P_{ix},P_{yy})\) represents the points in the contour of polygon, the number of points is \(n\) and \((C_{x},C_{y})\) indicates the new center of gravity. The modified center of each sub-area is illustrated in Figure 6. These centers of each sub-area act as the supply points. In order to refine the segmentation, the sub-area generation method is further performed based on these modified supply points. A fundamental principle is to ensure that, compared to the distance to supply points in other sub-areas, the point located in the current sub-area has the shortest distance to the corresponding supply point. The points on the common edge between two sub-areas have equal distances to the two adjacent supply points. Considering the above constraints, a further adjustment method based on a Voronoi diagram (VG) [36] needs to be performed on these sub-areas. Firstly, the supply points are used as the discrete points for the construction of the VG. Construction of Delaunay triangulation is carried out on these discrete points. The relationship between the construction of each triangle and its corresponding three discrete points is recorded. The circumcircle center of each triangle is calculated. Secondly, the adjacent three triangles that share the same edge with current triangle \(p\)_Tri_ need to be adjusted by traversing the triangle linked list. If the adjacent triangles exist, the circumcircle center of the adjacent triangle connects to the circumcircle center of triangle \(p\)_Tri_, and the new added line is stored in the Voronoi edge linked list. Conversely, the outermost perpendicular ray will intersect with contour \(C\) of the coverage area, and the new edge generated from the perpendicular line is also added to the Voronoi edge linked list. Finally, the traversal process is finished, all the Voronoi  
Figure 5: Coverage area segmentation and sub-area generation.