# Drone Deployment Algorithms for Effective Communication Establishment in Disaster Affected Areas
## 3 Proposed Methods
### Region Filling
#### 3.4.4. Filling the Coverage Circles Along the \(X\) and \(Y\) Axes  
Figure 8 shows how we find circles to be filled along the \(x\)-axis. The initial circle near the base station (0, 0) is placed to pass through (0, 0). The value of \(d\) for the initial drone is the coverage radius. The center of the initial circle \((d.x,d.y)\) is placed such that the angle made by the line between \((d.x,d.y)\) and (0, 0) and the \(x\)-axis is \(45^{\circ}\), meaning that any wasted coverage is equally distributed along both the \(x\) and \(y\) directions. The point at which the circle meets the \(x\)-axis is marked as \((x_{1},y_{1})\). To find the next circle in the \(x\)-direction, we assume that it has the same radius (\(r\)) as the initial circle and grazes the \(x\)-axis. In the figure, its center is \((x_{2},y_{2})\). In order to distribute the wastage equally in both directions, we fix the center of the new circle at \((x,y)\) at a distance \(r\) from \((x_{1},y_{1})\) along the angle (\(\theta\)), obtaining a new center and radius for the new circle at \((x,y)\). We refine the new circle again with respect to the new center and new radius. This procedure continues until the center in the previous round and that in the current round match. This is analogous to the rounds of the \(k\)_-means_ clustering algorithm [43]. The detailed method used for filling circles along the \(x\)-axis is provided in Algorithm 2. ```
Input:\((x,y)\)--position of the drone, \(h_{ref}\)--height of reference point, \(h_{fixed}=0\) Output:\(b,h,r,e\)
1:\(dist_{1}\leftarrow\sqrt{x^{2}+y^{2}}\)
2:\(dist_{2}\leftarrow\sqrt{(x-m)^{2}+(y-n)^{2}}\)
3:\(dist\gets Minimum(dist_{1},dist_{2})\)
4:if\(dist=dist_{1}\)then
5:\(b\gets 0\)
6:\(h_{b}\gets H_{0,0}\)
7:else
8:\(b\gets 1\)
9:\(h_{b}\gets H_{m,n}\)
10:endif
11:if\(h_{fixed}\
eq 0\)then
12:\(h\gets h_{fixed}\)
13:else
14:\(h\leftarrow\dfrac{W\times H_{max}-dist}{W}\)
15:if\(h<H_{min}\)then
16:\(h\gets H_{min}\)
17:endif
18:\(h_{t}\gets H_{x,y}\)
19:if\((h+h_{ref}-h_{t})<h_{td}\)then
20:\(h\gets h_{t}+h_{td}-h_{ref}\)
21:endif
22:endif
23:\(r\leftarrow\tan(\alpha)\times h\)
24:\(h_{small}\gets SH_{x,y,r}\)
25:if\(h+h_{ref}-h_{small}>H_{max}\)then
26:\(h\gets H_{max}+h_{small}-h_{ref}\)
27:\(Perform\)\(16\)\(to\)\(18\)
28:endif
29:\(r\leftarrow\tan(\alpha)\times h\)
30:\(e\gets B-C\times(dist+W\times(h-h_{b}))\)
31:return\((b,h,r,e)\)
```  
**Algorithm 1** FindDroneParameters—Calculating the base station (\(b\)), height (\(h\)), radius of coverage (\(r\)), and leftover energy (\(e\)) of the drone  
The algorithm uses two functions, _ArbitraryDistant_ and _EquiDistant_. The former finds a point \((x,y)\) at a distance \(r_{1}+r\) from \((x^{\prime},y^{\prime})\) and at a distance \(r_{2}+r\) from \((x^{\prime\prime},y^{\prime\prime})\), where(\(x^{\prime}\), \(y^{\prime}\)) and (\(x^{\prime\prime}\), \(y^{\prime\prime}\)) are any two points and \(r_{1}\), \(r_{2}\), and \(r\) are arbitrary. There may be two different points for (\(x,y\)) on a plane; in order to always choose the point inside the rectangle, we use a separate variable _special_ in the algorithm. The latter (_EquiDistant_) fixes the position of a drone object at an equal distance from the positions provided by the parameter points. We continue the process of finding new circles as long as it is possible to set the center of the new circle equidistant from the points (\(x_{1},y_{1}\)) and (\(m,0\)). The final output of filling along the \(x\)-axis is shown in Figure 9.  
Filling the circles along the \(y\)-axis (_FillAlongYAxis_) is quite similar to the procedure described above. The only difference is the change in direction, as shown in Figure 10.  
Figure 8: Finding the next circle along the \(x\)-axis (_FillAlongXAxis_). Figure 10: Finding the next circle along \(y\)-axis (_FillAlongXAxis_). Figure 9: The output of filling circles along the \(x\)-axis.