## 3 The Proposed Coverage Flight Path Planning Algorithm
### Locating Area of Interest on the Modelled Map and Extracting Free Spaces Geometry
#### 3.2.2 Extracting Free Spaces Geometry  
After locating the AOI in an enclosed form on the map, we extract free spaces geometry from the AOI. To do so, we first perform the obstacles' existence checks in the AOI. With the help of these checks, the AOI can be classified into three categories such as obstacles-free environment, obstacles inhibiting environment and area boundary obstacles only. We simplify the AOI boundary by considering the obstacles that intersect with the AOI edges or vertices and lying in close proximity of the AOI edges by shrinking the AOI inward considering the UAV size. Those obstacles which are on the boundary of the AOI or in close proximity that can impact the UAV safety are removed and configuration space (CS) is simplified for mission. Later, we draw a line from one vertices of the AOI to its nearest adjacent vertices and rotate it to all \(n\) vertices to determine the obstacles' existence. If no obstacles intersect with the line, then the AOI can be regarded as the obstacle-free. Meanwhile, if the obstacles exist, the proposed algorithm determines whether the obstacles are part of the area boundary obstacles only or in-field obstacles. In the former case, the proposed algorithm performs the coverage in simplified CS where the AOI is obstacle-free. In the latter case, the obstacles' enlargement (i.e., pushing the intersections by a \(D_{safe}\) out of obstacles.) and clustering are carried out to extract the free spaces geometry from the AOI. We enlarge the obstacles by safe distance \(D_{safe}\) and cluster the nearby obstacles which overlap each other due to \(D_{safe}\) addition or become so close to each other that UAV can collide. \(D_{safe}\) is an integer number whose value can be adjusted considering the UAV size, operating environment and obstacles shape. A pictorial overview of the enlarged obstacle by \(D_{safe}\) addition is shown in Figure 4.  
We apply the minimum UAV altitude limits \(H_{min}\) to discard the obstacles that fall below the \(H_{min}\) and UAV can go over safely. Through the above-mentioned process, the AOI can be classified into traversable and non-traversable parts. In the traversal parts, we fit UAV sensor footprints' sweeps considering the appropriate coverage direction for the coverage missions. Selecting the Best Coverage Direction (s) by Analyzing the Span of the Area of Interest and Exploiting Free Spaces Geometry Information  
Selecting the best coverage direction is extremely important to reduce the number of turns in the flight path to preserve the UAV resources. The turns are costly in terms of the energy, mission time, and path length because the UAV has to reduce the speed, perform turn, and increase speed again. Figure 5 presents the overview of the coverage path obtained from the same AOI with two different directions. The path on the left has only three turns and the path on the right has eleven turns. Figure 4: Overview of the enlarged obstacle by \(D_{safe}\) value. Figure 3: Different obstacles’ intersections with the area of interest boundary. In this work, we select the best coverage direction (s) by analyzing the span \(D\) of the AOI and exploiting free spaces' geometry information. We compute the horizontal span \(H_{s}\) and vertical span \(V_{s}\) of the AOI for the best coverage direction selection for regular shaped AOI. Additionally, we exploit the free spaces' geometry knowledge to select the appropriate coverage direction (s). The coverage direction is chosen parallel to the maximal span axis and considering the free spaces tendency. We employ either one or multiple coverage directions depending upon the AOI complexity to reduce the number of turns. For the irregular shaped AOI, we compute the convex-hull and transform it to some approximate regular shape for the span calculation and best coverage direction selection. When both spans of the AOI are equal, the appropriate coverage direction is chosen considering the obstacles placement and free spaces tendency.