# OADC: An Obstacle-Avoidance Data Collection Scheme Using Multiple Unmanned Aerial Vehicles
## 4 Algorithms
### Obstacle Avoidance Algorithm (VRAOA)  
In the proposed OADC scheme, the vector rotation angle-based obstacle avoidance (VRAOA) algorithm is applied to determine the detour points. The input and output of VRAOA are the shape of the obstacle and a convex polygon, respectively, as shown in Figure 3. Algorithm 1 shows the pseudo-code of the VRAOA, which is explained using a graph representation and a vector representation shown in Figures 1 and 2, respectively. Assume an arbitrary obstacle shape ABCDEFGHIJKLMNA shown in Figure 1. In this graph, the coordinates are A, B, C, D, E, F, G, H, I, J, K, L, M, and N. The edges on the boundary are A-B, B-C, C-D, D-E, E-F, F-G, G-H, H-I, I-J, J-K, K-L, L-M, M-N, and N-A. Consider that the set \(E\) contains all the edges, and the set \(C\) contains all the coordinates which connect the edges. First, a starting point and an ending point \(P_{\text{s}}\) is selected from \(C\), which has the minimum coordinate value on the y-axis (line 1, Algorithm 1). For example, in Figure 1, the \(P_{\text{s}}\) is the point A, which has the minimum value on the y-axis. In line 2 of Algorithm 1, \(P_{\text{s}}\) is also set to the current visiting point \(P_{\text{c}}\). A unit vector \(\vec{u}\) is considered for each \(P_{\text{c}}\). Two types of unit vectors in two cases were considered: (1) an x-axis unit vector \(<1,0>\) for when the x-axis coordinate \(x_{\text{c}}\) of the current visiting point \(P_{\text{c}}\) is greater than or equal to the x-axis coordinate \(x_{\text{s}}\) of the \(n_{\text{s}}\); (2) a y-axis unit vector \(<0,1>\) for when the x-axis coordinate \(x_{\text{c}}\) of \(P_{\text{c}}\) is smaller than \(x_{\text{s}}\) (lines number 4-8). Then, the vector values are calculated from the current visiting point \(P_{\text{c}}\) to all other points in the polygon. When \(P_{\text{c}}=P_{\text{s}}\), calculate the vector values for all points in C except \(P_{\text{c}}\) (in lines 9-10). For example, in Figure 1, for point A, the vectors will be from A to points B, C, D, E, F, G, H, I, J, K, L, M, and N, which is shown in Figure 2 with the orange lines. Otherwise, in lines 11-12, the vector values for all points in \(C\) and \(P_{\text{s}}\) are calculated except for \(P_{\text{c}}\). This step makes the VRAOA algorithm more efficient. The reason is as follows. There is no such possibility of visiting any previous point in C from any current visiting point \(P_{\text{c}}\) because the right rotation angle is always considered while choosing the next visiting point. For example, in Figure 1, if L is the current visiting point, then there is no possibility of visiting any other previous point before L. In this case, only M and N can be visited to end the tour in A while considering the right rotation angle from the current visiting point L.  
Subsequently, in line 15, for each current visiting point \(P_{\text{c}}\), calculate the rotation angles \(\theta_{i}\) between the unit vector considered for \(P_{\text{c}}\) and the other vectors \(v_{i}\) for all \(i\) in \(C\). However, the equation used in line 15 to calculate the right rotation angles is not always correct. Recall  
Figure 1: Graph representation for VRAOA algorithm. Figure 2: Vector representation for point “A” of the VRAOA algorithm. that in VRAOA, the right-direction rotation angle from a unit vector is always considered for each current point. To have an accurate rotation angle, if the unit vector is in the y-axis direction and the x-axis vector value of the other vector is greater than or equal to zero, then the angle found from the equation should be subtracted from 360\({}^{\circ}\). Similarly, when the unit vector is in the x-axis direction and the y-axis vector value of the other vector is less than zero, then to find the actual rotation angle, the angle obtained from the equation should be subtracted from 360\({}^{\circ}\). Otherwise, the angle calculated from the equation in line 15 is the correct rotation angle (line numbers 16-22).