# 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
The fact that it is realized with graphical manipulations on a digital image does not increase its complexity. [PERSON] and [PERSON] who used a standard A* with a quadtree representation of the terrain, mentioned that the complexity of their method is only marginally affected by the number of pixels in the images [PERSON] and [PERSON] (2018). Both the graph construction and the A* calculations remain the same whatever the number of pixels because these depend only on the nature of the distribution of the obstacles. They mentioned expecting the contribution of the number of pixels to the complexity to be of \(O(n)\), where n is the density of pixels. This is also the complexity given by [PERSON] and [PERSON] for the line supercover algorithm that we use constantly in our algorithm to trace the straight-lines ([PERSON] and [PERSON], 2018; [PERSON] and [PERSON], 2018). Given the important similarity between the A* algorithm and [PERSON]'s algorithm, [PERSON] and [PERSON] undertook to compare them for solving the shortest path problem ([PERSON] and [PERSON], 2018). They found \"the only difference being that A* tries to look for a better path by using a heuristic function, which gives priority to nodes that are supposed to be better than others while [PERSON]'s just explore all possible ways\". A* scans the terrain preferably in the direction of the destination, whereas [PERSON] searches equally in all directions. Thus, the latter ends up exploring a much larger area before the target is found, making it slower than A*, although no one has yet quantized this difference. They mention that this advantage can be demonstrated by the loop count of Dijkstra and A*; the more nodes there are, the higher the difference between the loop counts will be. They actually then performed some tests with a network of 101 road intersections in a Google map of the vicinity of the city of Kota Matsum in Indonesia. They counted both the number of loops and the execution times for the same shortest path problems with the A* and the Dijkstra algorithm. They found that the loop count of the A* algorithm was indeed consistently smaller than that of [PERSON]'s algorithm, even for small numbers of nodes. For small problems, the execution times of both were similar. However, for large problems, with about 100 nodes, the loop count of A* was about three-quarters that of the Dijkstra, and its execution time was about one-quarter smaller. [PERSON] et al. examined the complexity of bitangent algorithms to solve the shortest path problem for a terrain with disk obstacles [PERSON] et al. (2018), in which the nodes and edges are defined as described by [PERSON]. Given that the core of our approach is essentially the same one as that of [PERSON], except for the shape of the obstacles, we do not expect our algorithm to differ very much in complexity from his. The authors note that when there are \(N\) disks, there are then \(O(N^{2})\) nodes and \(O(N^{2})\) edges. Most shortest path algorithms are some version of [PERSON]'s algorithm for which the length of the edges is their weight. They remarked that, for a graph with V nodes and E edges, [PERSON]'s algorithm can be implemented to run in \(O(E+V\log V)=O(N^{2}\log N)\) time. Therefore, the complexity of the A* algorithm is bounded above by this expression. A final remark about the storage memory space used by our proposed method is worthwhile. The input data is a digital image that is read in the computer memory. This image is then replaced by the image of the labeled blobs (the \"etiquettes\" image). The contour of the obstacles can be painted in this image, thus not requiring any additional memory space. Therefore, the permanent data on which the algorithm works takes essentially the same amount of memory space as the initial digital image. The main task performed by our algorithm, is the calculation of rectilinear tangents; we note that once they have been calculated, only their end points are stored in memory.