# An Effective Algorithm for Finding Shortest Paths in Tubular Spaces
## 4 The ESP Searching Algorithm Based on Visibility
### The Proposed Algorithm  
The principle of this method is based on Remark 1. Ensuring that two points can see each other in the discrete approach is equivalent to proving that the line segment joining those points must cross all the meshed circular disks between them. In the Algorithm 2, we use \(\mathbf{C}_{i}\) to denote the intersection point between the searching shortest path and the cross-section \(S_{i},~{}i\in\{0,\ldots,N+1\}\). The objective of Algorithm 2 is then equivalent to finding the series of \(\mathbf{C}_{i}\). It is important to note that \(\mathbf{C}_{i}\) is not necessarily a node of \(G(V,A)\). Indeed, the algorithm determines the correct direction of \(\mathbf{C}_{i-1}\), thereby determining the position of \(\mathbf{C}_{i}\) as the intersection point between this direction and the next cross-section \(S_{i}\). The correct direction of \(\mathbf{C}_{i-1}\) was found using Remark 1 by checking which partition \(\mathbf{C}_{i-1}\) belongs to (with precedence from **P1** to **P3**). The value **1** of \(flag\) marks that \(\mathbf{C}_{i-1}\) can see the ending cross-section \(S_{N+1}\). The **Oriented Drilling Process** is an algorithm employed for Partition 3, which returns to the next value of the \(\mathbf{C}_{i}\) series by the intersection point between the longest-length-of-sight direction and the next cross-section.  
Figure 8: Three partitions of the shortest path correspond to three sections of the tube. At \(\mathbf{A}\) belonging to **P3**, the VP cannot see the ending cross-section \(S_{end}\). The correct direction corresponds to the longest length of sight. At \(\mathbf{B}\) belonging to **P2**, \(S_{end}\) can see been, but not \(\mathbf{\dot{\Omega}}\). The correct direction is towards the visible point **Y** in \(S_{end}\) so that the angle \(\theta\) between **BY** and **B\(\mathbf{\Omega}\)** is the smallest one. At \(\mathbf{C}\) in **P1**, the particle can see \(\mathbf{\Omega}\). The correct direction is towards \(\mathbf{\dot{\Omega}}\).  
```
Input:\(\boldsymbol{\mathfrak{P}},\boldsymbol{\Omega}\), and \(\boldsymbol{r}_{[||]^{\prime}},\forall i\in\{1,\ldots,N\},\forall j\in\{1,\ldots,M\}\). Output:\(\boldsymbol{C}_{i},\forall i\in\{0,\ldots,N+1\}\). // Initialisation \(\boldsymbol{C}_{0}\leftarrow\boldsymbol{\mathfrak{P}},\boldsymbol{C}_{N+1} \leftarrow\boldsymbol{\mathfrak{Q}},\boldsymbol{C}_{i}\leftarrow\emptyset, \forall i\in\{1,\ldots,N\}\); \(flag\gets 0\) // Marking if the \(\boldsymbol{C}_{i-1}\) can see \(S_{N+1}\) or not // Loop Process for\(i\gets 1\) to \(N+1\)do if\(\boldsymbol{C}_{i-1}\) can see \(\boldsymbol{C}_{N+1}\)then // \(\boldsymbol{C}_{i-1}\) is belong to Partition 1 \(\boldsymbol{C}_{k}\leftarrow\overline{\boldsymbol{C}_{i-1}\boldsymbol{C}_{N+1}} \cap S_{k},\forall k\in\{i,\ldots,N\}\); \(flag\gets 1\); break; else \(\theta\leftarrow+\infty\) ; // Angle between the correct direction and \(\overline{\boldsymbol{C}_{i-1}\boldsymbol{\mathfrak{Q}}}\) for\(j\gets 1\) to \(M\)do \(\boldsymbol{C}_{distal}\leftarrow\boldsymbol{r}_{[N+1][]}\) ; // Temporary examined vertex of \(S_{N+1}\) if\(\boldsymbol{C}_{i-1}\) can see \(\boldsymbol{C}_{Distal}\)then \(flag\gets 1\) ; // \(\boldsymbol{C}_{i-1}\) is belong to Partition 2 \(\boldsymbol{C}_{temp}\leftarrow\overline{\boldsymbol{C}_{i-1}\boldsymbol{C}_{ distal}}\cap S_{i}\) ; // Possible value for \(C_{i}\) \(\theta_{temp}=Angle\Big{(}\overline{\boldsymbol{C}_{i-1}\boldsymbol{C}_{ distal}},\overline{\boldsymbol{C}_{i-1}\boldsymbol{\mathfrak{Q}}}\Big{)}\) ; // Possible value for \(\theta\) if\(\theta>\theta_{temp}\)then \(\theta\leftarrow\theta_{temp}\); \(\boldsymbol{C}_{i}\leftarrow\boldsymbol{C}_{temp}\);  end if  end for  end for  end for
```  
**Algorithm 2**Proposed method.