# An Algorithm to Find the Shortest Path through Obstacles of Arbitrary Shapes and Positions in 2D
## 2 Some Earlier Works
[PERSON] and [PERSON] contributed an important approach to deal with obstacles with curved boundaries of arbitrary shapes [24; 25]. It is based on a tangent graph, which we will call the L-A graph. They noted that the boundary of an obstacle can be decomposed into a sequence of convex arcs, connected by nonconvex arcs. Correspondingly, they defined a graph, the edges of which are the convex boundary segments of the obstacles and the free tangents that connect them. The nodes of their graph are the points of contact of these tangents on the boundary of the obstacles. However, as can be realized by looking at the landscapes in the figure of Section 6, realistic obstacles normally have a very large number of indentations so that the corresponding L-A graphs would have such a large number of edges and nodes that the shortest path solution time would be considerable. [PERSON] et al. thereafter used an L-A graph with an iterative tangent searching algorithm [26]. A set of paths is maintained and an iteration process adds tangents to all unfinished paths to create new paths. Some paths are removed when they are considered to have no chance of being part of the optimal path. This iteration proceeds until all paths reach the target and the shortest path then becomes obvious. In all of the shortest path methods described above for polygons and splinegons, the obstacles are represented by mathematical formulas. However, for real-world obstacles with arbitrary curved boundaries, as [PERSON] and [PERSON] point out, using algorithms with mathematical formulas is somewhat unrealistic because these formulas would be very costly to generate and awkward to use [27]. It may, however, be worthwhile to do when the same terrain is used for a long enough period of time, as [PERSON] and [PERSON] have demonstrated, with their application to ships moving near some coasts and islands [28]. They successfully represented their landscapes by quadtrees. They quote that a 100 km by 100 km region can be represented, with a 10 m resolution, by a quadtree with a hundred thousand or fewer nodes. They then use the results of [PERSON] and [PERSON], together with the A* algorithm, to determine the shortest path. They give some judicious considerations to the elimination of certain nodes, in particular, those that lie inside the convex hulls of obstacles, and have no chance of appearing in the shortest path. For the application they consider, a mathematical representation of the terrain can be constructed once and for all, and temporary local modifications due to tides and waves could thereafter be incorporated as they occur. [PERSON] et al. described the computation of the shortest path on a terrain surface [29]. This subject is very important in mission planning for terrestrial vehicles. The authors represent the terrain surface by polygons and prove the crucial theorem that the shortest geodesic path on this terrain corresponds to the shortest Euclidean path on the planar unfolding [30]. The 2D projected surface is considered as free space and its boundaries as obstacles. The problem is thus reduced to one of finding the Euclidean shortest path in 2D with polygonal obstacles, which is solved similarly to that of [PERSON] and [PERSON]. If the calculations could be parallelized, then a representation of the terrain by elementary polygons could be advantageously used with sufficiently many polygons to yield the precision desired for the paths constructed. Help in developing this approach can be provided by the work of [PERSON] and [PERSON], who have described a parallel simulation of collision avoidance in 3D of objects that are described by ten thousands to millions of polygons [31]. In their approach, the interactions are calculated between the objects instead of having to consider their individual components' polygons individually.