# An Algorithm to Find the Shortest Path through Obstacles of Arbitrary Shapes and Positions in 2D
## 4 Details of the Implementation
### Data Representation
#### 4.8.3 The Algorithm Pseudo-Code
\begin{tabular}{l l l l} \(\begin{array}{l}\mathit{Set}\mathit{EndNodels}=\{\mathit{NodeId}(S)\}\end{array}\) & \(\mathit{ExpandedNodes}=\mathit{\phi}\) & \(\mathit{FreeTangents}=\mathit{\phi}\) \\ \end{tabular}   
Set Node(\(S\))'s properties: \begin{tabular}{l l l l l} \(\begin{array}{l}\mathit{Set}\mathit{EndNodels}=\{\mathit{NodeId}(S)\}\end{array}\) & \(\mathit{ExpandedNodes}=\mathit{\phi}\) & \(\mathit{FreeTangents}=\mathit{\phi}\) \\ \end{tabular}   
Set Node(\(S\))'s properties: \begin{tabular}{l l l l} \(\begin{array}{l}\mathit{Set}\mathit{EndNodels}=\{\mathit{NodeId}(S)\}\end{array}\) & \(\mathit{ExpandedNodes}=\mathit{\phi}\) & \(\mathit{FreeTangents}=\mathit{\phi}\) \\ \end{tabular}   
Set \(ExpandedObsts=\phi\)  
Set \(ObstNos=\{1,2,...,N,N+2,-1,-2,...,-N\}\)  
_Computation Steps_  
1. Select for expansion the node \(x\) that has the minimum f and denote by \(NoObstx\) its obstacle number. 2. If \(NoObstx=N+2\) then mark \(x\) and \(Obst(x)\) as expanded and terminate the computation. 3. If \(Obst(x)\) is expanded, execute the IntegrateExpandedNode procedure and go to Step 5. **For all obstacle numbers**\(NoObsty\) in \(ObstNos\) that differ from \(NoObstx\),  
compute the bitangents as follows:  
If \(Obst(x)\) has no embeddings from \(Obst(y)\) and \(Obst(y)\) has no embeddings from \(Obst(x)\), compute the simple bitangent Tan(\(x\),\(y\)) between the two obstacles \(x\) and \(y\). If \(Obst(x)\) has no embeddings from \(Obst(y)\) and \(Obst(y)\) has embeddings from \(Obst(x)\), execute the \(PassageEnteringAlgorithm\) and let Tan(\(x\),\(y\)) denote the passage entering tangent. If \(Obst(x)\) has embeddings from \(Obst(y)\) and \(Obst(y)\) has embeddings from \(Obst(x)\), compute the set TanL(\(x\),\(y\)) of all of the mutual tangents. If \(Obst(x)\) has embeddings from \(Obst(y)\) and \(Obst(y)\) has no embeddings from \(Obst(x)\), compute the simple bitangent Tan(\(x\),\(y\)) between the obstacles \(NoObstx\) and \(NoObsty\). Incorporate the bitangents as follows:  
**for Tan(\(x\),\(y\)) or each element** Tan(\(x\),\(y\)) in the set TanL(\(x\),\(y\)):  
If Tan(\(x\),\(y\)) is not free, then continue. Otherwise, compute the tangent convex arc \(ConvexArc\) on \(Obst(x)\) that starts at the position of \(x\) and ends at the leaving position of Tan(\(x\),\(y\)) on \(Obst(x)\). If \(ConvexArc\) is not free, then put Tan(\(x\),\(y\)) into the \(FreeTangents\) set of \(Obst(x)\) to be dealt with later on, and continue. Otherwise, set \(gy=x\),\(g+\) length of \(ConvexArc+\) length of Tan(\(x\),\(y\));  
set \(fy=gy+\)EDist(\(y\), \(T\));  
define \(Node(y)\) with the following parameters  
\(OnObst=NoObsty\)\(Post=Tan(x\),\(y\)).ToPosn\(FromObst=NoObstx\)  
\(TanLength=Tan(x\),\(y\)).TanLength\(g=gy\)\(f=fly\)\(OutTangents=\phi\)  
If the structure for \(Obst(y)\) does not already exist,  
define it with the following properties:  
\(ObstNos=ObstNo\)\(EndNodes=[Node(y)]\)\(ExpandedNodes=\phi\)\(FreeTangents=\phi\)  
Mark it as an end obstacle. Otherwise, add \(y\) to the \(Obst(y)\) set of \(EndNodes\). Insert Tan(\(x\),\(y\)) into the \(OutTangents\) set of node \(x\). **End of the loop: \"_For all obstacle numbers_\". (4) If \(Obst(x)\) was not an expanded obstacle,  
mark it as expanded and unmark it as an end node. If it has not been discarded at Step (3), mark it as expanded. (5) Go to Step 1. _End of computation._  
Once the algorithm has been run, the shortest path can be read backward, starting with the end node \(T\) and following the successive father nodes, until node \(S\) is reached. **5. Some Remarks on the Complexity**  
Analyzing the complexity of our proposed refined A* search algorithm, combined with our new theorem, is a formidable task in itself that we should undertake in a separate study. It is intuitively clear, however, that, since a step of the A* algorithm is eliminated, our algorithm should be better than the standard version of the A* algorithm. For the moment, we will simply recall some general facts about an upper bound for its complexity.