# An Algorithm to Find the Shortest Path through Obstacles of Arbitrary Shapes and Positions in 2D
## 2 Some Earlier Works  
Finding a free path through a field of obstacles in 2D is a problem that has been much-studied in computational geometry. [PERSON]'s method [8], for controlling [PERSON] the robot, was a harbinger of the approaches to solving that problem. This robot navigated autonomously through a field of obstacles with the help of a video camera. It represented the obstacles by polygons, and used [PERSON]'s A\({}^{\star}\) algorithm [9], acting on the visibility graph, to find the locally best path. The edges of the visibility graph (V-graph) are the collision free straight-lines linking the point of origin to the polygon vertices, and its nodes are the end points of these lines. The past generated was not globally best because a representation of all of the landscape was not available to the robot. Reviews of the prevalent methods to find free paths in 2D can be found in [10; 11; 12]. The most popular such methods are based on graphs that correspond to quadtree or trapezoidal decompositions of the landscape [13], roadmaps derived from the Voronoi diagram [14] and visibility graphs [15; 16]. Much of the shortest path research involved polygonal obstacles because these can be represented analytically by mathematical expressions. [PERSON]'s approach with the visibility graph (V-graph) has been pursued by those, for example in [15; 16], who use these data for graph optimisation algorithms, either the A\({}^{\star}\) or [PERSON] algorithm [17]. Most of the improvements that have been made consist in simplifications of the graph data, which result from determining which vertices of the V-graph do not have a chance of being in the shortest path. [PERSON] presented two approaches to the analysis of polygonal landscapes in [18]. The first one consists in using [PERSON]'s algorithm to construct a tree of all of the shortest paths between all of the vertices of the polygonal obstacles. This tree is then used to construct the shortest path map (SPM), from which the shortest paths to any point \(T\) in free space can be obtained. The second approach [19] consists in simulating a wave front that propagates out of the source \(S\) and that undergoes a local perturbation each time it encounters an obstacle vertex. The results obtained for polygonal obstacles were generalized by [PERSON] and [PERSON] who based their method on splinegons [20]. These are curved geometrical forms that replace the sides of polygons by curves such that the area bounded by this curve and its replaced polygon side is convex. These objects can be represented mathematically, and allow for a straightforward generalization of the trapezoidal cell decomposition of the space [21], with some sides of the trapezoids being replaced by the curved sides of the splinegons. A tangent graph is defined for the resulting objects and the Dijskra algorithm is used to generate the shortest path. Although the methods to find shortest paths in polygonal and splinegon obstacles are very efficient, they have not been generalized to obstacles of arbitrary shapes and it is not clear how they could be. [PERSON]'s thesis generalized [PERSON]'s method for the motion of an actual robot that had a video camera as range sensor [22]. Although the size of the environment in which the robot moved was relatively limited, the concepts introduced are valid for more complex landscapes. His approach consisted in mapping the obstacles in three dimensions into circles projected on the ground and his robot had to compute a 2D path through these circles. This path consisted in a series of unobstructed straight line segments tangent to the circles, linked by circular arcs that followed the boundary of the obstacles. Thus, he represented the environment by a tangent graph, the edges of which were these compounded path segments. Any one of the standard graph optimization algorithms could then be used to generate the shortest path. [PERSON] et al. analyzed the computations involved in finding the shortest path through a landscape of disks [23].