# A Framework for Coverage Path Planning Optimization Based on Point Cloud for Structural Inspection
## 2 Proposed Framework
### Optimization Process  
After analyzing the filters' points, we have a surface layer that presents the surface information. In this step, the optimization of path planning begins. For photometric  
Figure 2: Comparison between Convave Hull and Convex Hull algorithms. issues, the framework considers the intersection among images: the intersection angle and incidence angle. For 3D reconstructions, the number of overlapping photos is an essential factor for these points' accuracy [38]. Figure 3 illustrates the variables considered in the problem model. The rectangle formed by \(Dist_{Vert}\) and \(Dist_{Hor}\) forms the Field of View (FOV) of the UAV camera. These dimensions, as seen in Equations (1) and (2), depend on the distance from the UAV to the surface (\(D_{S}\)) and the horizontal and vertical opening angles of the camera (respectively \(\theta_{hor}\) and \(\theta_{vert}\)):  
\[tan(\frac{\theta_{hor}}{2})=\frac{Dist_{hor}}{2D_{S}} \tag{1}\]  
\[tan(\frac{\theta_{vert}}{2})=\frac{Dist_{vert}}{2D_{S}} \tag{2}\]  
The mission carried out by the aircraft has the format of horizontal transfers at different heights, and the images will be taken after a \(D_{min}\) shift. These displacements create a region of intersection among the photos, as highlighted in color blue in Figure 4. Equation (3) represents the percentage of coverage calculation in relation to \(Dist_{Hor}\). The \(D_{min}\) distance was designed to capture images with the UAV hovering to prevent the image from losing quality. Suppose the camera can capture a moving image without loss of quality. In that case, the parameter \(D_{min}\) will be used to reconstruct the surface shape that will be inspected. It is not necessarily part of the optimization. The image can be captured at a shorter possible distance, and, in Equation (7), the \(Time_{shot}\), which is the downtime for image capture, can be zero:  
\[Coverage_{hor}=(1-\frac{D_{min}}{Dist_{hor}})*100 \tag{3}\]  
Figure 3: Problem variables. The differences among the missions' heights also generate a vertical intersection between the photos. The vertical offset (\(D_{vert}\)) depends on the height of the surface, defined by the difference between the maximum height (\(h_{max}\)) and minimum height (\(h_{min}\)), and the number of vertical waypoints (\(N_{Vert}\)) that have been defined for the mission. Figure 5 illustrates the vertical intersection between photos. Equation (4) shows the calculation of vertical displacement, while Equation (5) presents the vertical coverage:  
\[D_{vert}=\frac{|h_{max}-h_{min}|}{(N_{Vert}+1)} \tag{4}\]  
\[Coverage_{vert}=(1-\frac{D_{vert}}{Dist_{vert}})*100 \tag{5}\]  
The intersection angle is defined as the angle that surrounds all images taken from that point. When the intersection angle increases, the correspondences may become discontinuous. Note that large intersection angles make image matching difficult, whereas small ones result in low intersection precision [39]. Thus, for better accuracy, it is given that the intersection angle should be close to 90\({}^{\circ}\)[38]. The incidence angle is defined as the angle between the image normal and the surface normal. As can be noticed, when it is closer to 0 degrees, the quality of the images is better and thus also the accuracy of the points [38]. Figure 6 shows the angles of incidence and intersection. The blue region represents the intersection region, where the 4 UAVs that can capture the same point are identified. The incidence angle is identified in red, between the UAV and the surface normal. Figure 4: Horizontal coverage. Figure 5: Vertical coverage. The objectives considered are to decrease the mission time and increase the intersection area between the images, besides adjusting the angles. For these purposes, the variables are \(D_{min},D_{S}\), and \(N_{Vert}\). The time is computed considering the distance displaced by the aircraft and its average speed, adding an image capture time at each waypoint, as shown in Equation (7).