## 3 The Proposed Method
### Generation of the First Constrained Polygonal Space  
Searching for a path by leveraging full map information can be very time consuming, and it may result in serious computing overhead in complex and large urban environments. To address these issues, we convert the full 3D map into a CPS that guarantees \(P\) from \(s\) to  
Figure 2: Example of obstacle-free (\(\xi_{free}\)) and obstacles (\(\xi_{obstacles}\)) regions in environment map \(W\). \(t\), and at the same time makes pathfinding computations faster. The space can be reduced using five main steps: (i) stipulating both \(s\) and \(t\) for a mission, (ii) sketching a straight-line \(\overline{l_{o}}\) between \(s\) and \(t\), (iii) extracting pertinent obstacles (i.e., only those obstacles where edges/vertices cross with the \(\overline{l_{o}}\)), (iv) analyzing the geometry of the extracted obstacles, and (v) drawing a minimum-span \(\zeta_{min}\) polygonal space \(S_{1}^{3}\) from the base vertices of pertinent obstacles in such a way that a cross section of the reduced space (e.g., \(S_{1}^{3}\)) is not completely blocked by all of the pertinent obstacles' cross sections. More specifically, the \(\zeta\) is selected in such a way that the path can be found in each scenario from the constrained space. Obstacles that are on the \(\overline{l_{o}}\) between \(s\) and \(t\) are called pertinent obstacles. After receiving the \(s\) and \(t\) locations for the flight, we sketch a \(\overline{l_{o}}\) from \(s\) to \(t\). After sketching the \(\overline{l_{o}}\), four outputs can be derived, which are: (I) neither penetration nor collision, (II) not penetration, but the possibility of a collision exists, (III) penetration, but all obstacles have a lower height, and the UAV can go over them safely, and (IV) both penetration and collision. All four results are demonstrated in Figure 3.  
If the \(\overline{l_{o}}\) does not collide with any obstacle, and the collision possibility is zero, then path \(P=\overline{l_{o}}\), which is an optimal path (e.g., a straight line) as given in Figure 3a. Moreover, if the \(\overline{l_{o}}\) does not penetrate any obstacles, but there remain some obstacles in close proximity to the \(\overline{l_{o}}\) with which the UAV could collide with a higher probability, then we deal with these obstacles to generate a safe \(P\), as demonstrated in Figure 3b. In the third case, as given in Figure 3c, few obstacles are penetrated by the \(\overline{l_{o}}\), all obstacles have a lower height, and the UAV can go over them safely. In the fourth case, as given in Figure 3d, some obstacles are penetrated by the \(\overline{l_{o}}\), and we need to bypass them at a lower cost to find a \(P\) between \(s\) and \(t\) while fulfilling the stated objectives. Such obstacles are extracted from the map and utilized for pathfinding from the CPS. The complete pseudo-code utilized for extracting pertinent obstacles is illustrated in Algorithm 1. In Algorithm 1, map \(W\) encompassing \(N\) distinct obstacles, \(s\), and \(t\), are given as input. The set \(E\), where (\(E\subseteq N\)) of the pertinent obstacles is retrieved as output. Line 2 can do \(\overline{l_{o}}\) sketching between \(s\) and \(t\). Lines 3-7 can do obstacles' extraction that are crossed by the \(\overline{l_{o}}\). At the end, set \(E\) of pertinent-obstacles is collected. Moreover, if no intersection occurs between the obstacles and the \(\overline{l_{o}}\), and, then, \(E=\emptyset\) will be the output. After getting set \(E\) of pertinent obstacles, we enlarge the obstacles by a safe distance (\(d_{safe}\)), and apply the flying minimum and maximum limits, denoted as \(h_{min}\) and \(h_{max}\), respectively. Subsequently, we analyze the pertinent obstacle cross sections that are on the \(\overline{l_{o}}\) between \(s\) and \(t\).