## 3 The Proposed Coverage Flight Path Planning Algorithm
### Waypoints Graph Generation by Connecting Footprints' Sweeps  
The waypoint graph (WG) is constructed by connecting the footprint sweeps' endpoints for the pathfinding. Mathematically, WG is a double edge graph \(\Gamma\) of inter-reachable locations: \(\Gamma=\{W,E\}\), where \(W\) represents the nodes set and \(E\) represents the edge set. The nodes of the \(\Gamma\) are the footprints' sweeps endpoints, while edges are straight lines for each sweep and connection from one sweep to another. Each footprint sweep is a line segment with the two endpoints \(a\) and \(b\) (i.e., \(F_{i}=\overline{ab}\)) as shown in Figure 6b. We connect the footprints' sweeps endpoint with the coincident (i.e., neighbours) sweeps endpoints to form a WG. Furthermore, in the WG construction process, we consider the obstacles' effect, UAV manoeuvrability constraints and footprints sweep visiting sequence to form the connected \(\Gamma\). We devise a strategy to avoid obstacles by applying three avoidance options (i.e., left, right, top) in footprints' sweeps inter-connection. Given \(N\) footprints' sweeps in the form of line segments, we compute the collision-free connections between footprints' sweeps. While constructing the WG, the proposed algorithm evaluates and selects the best obstacles' avoidance option from the candidate options. For the appropriate options selection, the distance is computed between two sweeps by introducing the two points on three sides of the obstacles. The selection of the appropriate obstacle's avoidance option \(AOAO\) for an obstacle \(O_{i}\) is carried out on the basis of following equation:  
\[AOAO_{i}=min\{d_{left},d_{right},d_{top}\}, \tag{7}\]  
where \(d_{left}\), \(d_{right}\) and \(d_{top}\) represent the minimum distance required to avoid an obstacle \(i\) from left, right, and top, respectively. The value of \(d\) for each option can be computed between two sweeps with the help of two intermediate points. For example, the distance required to find the collision-free connection between two footprints' sweeps \(F_{i}\) and \(F_{i+1}\) is the sum of the three individual distances (i.e., \(d\{(a,b),c),(c,d),(d,(a,b))\}\). The value of each option can be calculated with the help of following equation:  
\[d_{left}=\sum_{j=1}^{3}d_{j}, \tag{8}\]  
where \(d_{j}\) represents the minimum distance needed to connect two footprints' sweeps by bypassing an obstacle safely from left. Similarly, the distance values for the other two options are calculated and evaluated for the low cost connection formation. Meanwhile, if no obstacle exists between the footprints' sweeps, and collision can be avoided, then footprints' sweeps are connected with each other via straight lines. The waypoint graph \(\Gamma\) obtained from the AOI possess all properties of a roadmap. A pictorial overview of the waypoint graph \(\Gamma\) obtained by connecting endpoints of the \(N\) footprints' sweeps from the AOI having size \(1500\times 1500\times 400\) is shown in Figure 7a. In Figure 6(a), the yellow lines represent the footprints' sweeps and blue lines represent the collision-free connection between sweeps. Meanwhile, the black colour represents the area scanned by sensor footprints' sweeps. The proposed approach is applicable for both types of the UAVs, rotary-wing and fixed-wing. The rotary-wing UAVs present maneuverability advantages when making turns during the flight compared to the fixed wing UAVs. The WG produced by connecting the footprints' sweeps endpoints is directly usable for the rotary-wing UAV. Meanwhile, the fixed-wing UAV has strong maneuverability restrictions, demanding a bigger space to make turns. Therefore, the back-and-forth/zamboni flight pattern can be adopted to generate the WG, where the sweeps will be connected as shown in Figure 6(b). In the BF/Zamboni flight pattern, the adjacent sweeps can be connected with the gap \(g\) of two or three depending upon the complexity of the AOI and sweeps placements. The suggested pattern can simplify the turn and UAV doesn't need to slow down while making the turn.