# Determination of Point-to-Point 3D Routing Algorithm Using LiDAR Data for Noise Prediction
## 3 Methodology
### Building Corner Extraction Step 1 to Step 3
#### 3.3.1 Route over the Top (Step 4 to Step 9)  
Authors understood the possibility of sound diffraction over the top of the building. The route that followed was for propagation of noise from source to destination over the top of the building. Initially, for the principal route finding, it was required to consider the positions of source and destination points and the building in between, as shown in Figure 5(a) [10] in a 3D coordinate access system. Step 4: For the simulated area shown in Figure 5(a), a cutting plane in the XZ plane (abcd) was considered as shown in Figure 5(b). A direct route from the 2D source coordinate to the destination is represented by a line in Figure 5(c). The two-point form of a line is used for finding the equation of line between the source at point \((x_{s},y_{s},z_{s})\) and destination \((x_{d},\)\(y_{d},z_{d})\) with calculated direction ratios. \[ \begin{array}{l}I=(x_{d}-x_{s})\\ m=(y_{d}-y_{s})\\ n=(z_{d}-z_{s})\end{array} \]  
Here, \(l\), \(m\), \(n\) is DR's. The two-point form of a line passing through these two 3D points is denoted by:  
\[\frac{(x_{sd}-x_{s})}{(x_{d}-x_{s})}=\frac{(y_{sd}-y_{s})}{(y_{d}-y_{s})}= \frac{(z_{sd}-z_{s})}{(z_{d}-z_{s})}\]  
where \((x_{sd},\)\(y_{sd},\)\(z_{sd})\) represents any random point on the line, and these '\(x_{sd}\)', '\(y_{sd}\)', and '\(z_{sd}\)' can be put as variables. Step 5: When considering the building edges in 2D XY plane, the equation for each edge is formed that are (A1A2, A2A3, A3A4, A4A1, B1B2, B2B3, B3B4, B4B1,..., F4F1). These edges are stored in an array named as building edges array. \[ \begin{array}{l}Building\ edges\ array\\ =[\text{A1A2, A2A3, A3A4, A4A1, B1B2, B2B3, B3B4, B4B1}\ldots,\text{F4F1}]\end{array} \]  
Step 6: It was required to check whether the line equation between a pair of source and destination intersects with line equations that were present in the building edges array in Step 5. To find the intersection point of two lines, the following is used: The source-destination line equation \(U\) with (\(l\), \(m\), \(n\)) are DR's and the line equation of building edges- \(U_{1}\) with (\(a_{1}\), \(b_{1}\), \(c_{1}\)), \(U_{2}\) with (\(a_{2}\), \(b_{2}\), \(c_{2}\)), etc. For calculating point of intersection P with DR's (\(a_{p},b_{p},c_{p}\))  
\[ \begin{array}{l}Point\ of\ Intersection\ P(\text{i1})=U\times U_{1}\\ P(\text{i1})=((m*c_{1}-b_{1}*n),\ (a_{1}*n-l*c_{1}),\ (l*b_{1}-m*a_{1}))\end{array} \]  
If \(c_{p}=0\), that means the line does not intersect. Step 7: The author found the intersection point as i1, i2, i3, i4,......, stored in an array \(I=[\text{i1, i2, i3, i4, i5, i6}]\) shown in Figure 6(a). Considering the z plane here with the XZ and YZ plane. For each building intersection point adds up Z value to the intersection points, so the height points become j1, j2, j3, j4, etc. Additionally, the height was named as O1, O2, O3, O4, etc. Find the tallest height out of the O1, O2, O3, O4 shown in Figure 6(b). Here, we find the maximum is O3 where O3 = i3 - j3. After finding the O3 as tall now, we consider two travels for finding a route, one from \(S\) to j3 (upward travel) and from j3 to \(D\) (downward travel) is shown in Figure 7b. \"-\"represents the line, for, e.g., i3-j3, which means line between i3 and j3 point. \[upward\ array=[\text{S},\text{i1-j1},\text{i2-j2},\text{i3-j3}]\] \[downward\ array=[\text{i3-j3},\text{i4-j4},\text{i5-j4},\text{i6-j6}, \text{D}]\]  
Figure 6: (**a**) A Simulated area is taken for understanding the working of route determination with a pair of source and destination points, and (**b**) “abcd” is the XZ cutting plane created between the source to find out intersecting buildings and points. Intersecting buildings are Building B, Building E, and Building F, and (**c**) (B1, B2, B3, B4), (E1, E2, E3, E4) and (F1, F2, F3, F4) are the building corners on ground, which is calculated by the intersection of the XZ plane (that has shown in the previous figure) with the buildings. The source is denoted by “S” and destination by “D”.