# Airspace Geofencing and Flight Planning for Low-Altitude, Urban, Small Unmanned Aircraft Systems
## 3 Definitions and Algorithms
### Constructing a Geofence Volume from an Urban Map  
Keep-out geofences are constructed around obstacles (i.e., buildings) to assure separation between UAS and obstacles or no-fly airspace zones. The construction of keep-out geofence volumes from a building and terrain map must be efficiently carried out to constrain the computation time needed to generate geofence-based path planning solutions. For this work, we utilize a visibility graph approach to path planning, as illustrated in Section 3.3. The time complexity of visibility graph generation is \(O(n^{2}log(n))\), where \(n\) is the total number of vertices in all polygons. In a real-world environment, the number of keep-out geofences in the urban environment can be significant (i.e., 14,000 building cluster geofence polygons in the southern Manhattan map). We utilize two algorithms to achieve map simplification. First, we downsample geofence vertices in the map as shown in Algorithm 2 per [38] with user-defined parameters \(n_{maxVert}\) and \(p_{dunSample}\). This updated set of keep-out geofences is then used to construct a region of interest (ROI) visibility graph. The ROI in the map is first constructed as a rectangular box surrounding departure and destination points. Then, polygon intersection, point-in-polygon, and convex hull operations are used to define the actual region of interest for which geofence-based path planning solutions are generated. Generation of the flight planning visibility graph ROI is shown in Algorithm 3. Figure 4 shows an example of polygon vertex set downsampling. Figure 5 illustrates an initial rectangular ROI \(P_{recROI}\) example. Figure 3: Example application of Algorithm 1. A sample 3-D flight path is shown on the left. A corresponding flight trajectory keep-in geofence is shown on the right. ```
1:Set of Keep-out Geofences \(\mathcal{S}_{\mathit{geo}}\), Downsample Threshold \(n_{\mathit{maxVert}}\), Downsample Tolerance In Percentage \(p_{\mathit{downSmple}}\)
2:Set of Downsampled Keep-out Geofences \(\mathcal{S}_{\mathit{ds}}\)
3:
4:\(\mathcal{S}_{\mathit{ds}}\leftarrow[]\lhd\) initialize the output set
5:
6:for\(\mathcal{S}\in\mathcal{S}_{\mathit{geo}}\)do
7:if\(len(\mathcal{S})/2>n_{\mathit{maxVert}}\)then
8:\(\mathcal{S}_{\mathit{out}}\leftarrow\mathit{DecimatePoly}(\mathcal{S},p_{ \mathit{downSmple}})\lhd\) downsample polygon vertices
9:\(k\gets 1\)
10:for\(j=1:len(\mathcal{S}_{\mathit{out}})\)do
11:\(\mathcal{G}[k:k+1]\leftarrow\mathcal{S}_{\mathit{out}}[j,1:2]\lhd\) obtain geofence data structure
12:\(k=k+2\)
13:endfor
14:endif
15:\(\mathcal{S}_{\mathit{ds}}\leftarrow\mathcal{S}_{\mathit{ds}}.\mathit{add}( \mathcal{G})\)
16:endfor
17:return\(\mathcal{S}_{\mathit{ds}}\)
```  
**Algorithm 2** Reduce Map Geofence Vertex Set. ```
1:Inputs: Departure Point \(\mathcal{P}_{\mathit{start}}\), Destination Point \(\mathcal{P}_{\mathit{end}}\), ROI Inital Buffer \(\delta_{ROI}\), Keep-out Geofence Set \(\mathcal{S}_{\mathit{geo}}\)
2:Keep-out Geofences in ROI \(\mathcal{S}_{ROI}\)
3:
4:\(P_{\mathit{recROI}}\leftarrow\mathit{getRecROI}(\mathcal{P}_{\mathit{start}}, \mathcal{P}_{\mathit{end}},\delta_{ROI})\lhd\) get Rectangular ROI vertices
5:
6:\(//\)get convexhull ROI where geofencing solutions are generated
7:\(\mathcal{S}_{\mathit{intersect}}\leftarrow[]\lhd\) initialize the intersecting geofence set
8:for\(\mathcal{S}\in\mathcal{S}_{\mathit{geo}}\)do
9:if\(\mathit{searchIntersect}(S,P_{\mathit{recROI}})\
eq\emptyset\)then
10:\(\mathcal{S}_{\mathit{intersect}}\leftarrow\mathcal{S}_{\mathit{intersect}}.