# Is there a classic algorithm to find the shortest path between two points in a bidimentional space with polygon obstacles?

I'm looking for an algorithm to find the shortest(s) path that have no intersection with the interior of a set of polygons in a bi-dimensional space:

Is this a classical problem with a well-known solution or an equivalent or a special case of a wider range of classical problem ?

-
Since the shortest path will consist of a sequence of line segments, it seems it can be solved by Dijkstra's shortest path algorithm applied to a suitable network of polygon edges and line-of-sight connections between polygon nodes and the starting & ending points. – hardmath Jan 7 '13 at 15:40
Possible duplicate: stackoverflow.com/questions/5303538/… – Colin McQuillan Jan 7 '13 at 15:48
@ColinMcQuillan: That problem asks that the point not make "diagonal" movements, which if understood to mean restricting to motion parallel to the axes would make it quite a different problem, though possibly one in which a Euclidean metric is replaced by an $L^1$ metric. – hardmath Jan 7 '13 at 15:52
@hardmath that was my first guess, but it appears that finding out the "suitable" graph to use the Dijkstra is not trivial at all ;=) – Samuel Rossille Jan 7 '13 at 15:56

A paper on this topic is Shortest Paths in the Plane with Polygon Obstacles by Storer and Reif (published 1994 but submitted 1985).

They claim an improvement on previous methods assuming a precomputed Voronoi diagram.

-

If you want exact solution, then this is a very tedious problem, e.g. you construct a visibility graph (which could be huge) and run Dijkstra; many approaches use Voronoi diagrams (which is not a very pleasant tool to deal with). If you need only some approximation, then it is much easier. The practical approach is usually via compartmentalization, and the overall idea often follows some discretization of your 2D space and traditional search afterwards. Heuristics are helpful, so this is more like A* rather than Dijkstra (which is a special case of A*). Hybrid algorithm looks doable, but take into account that the set of possible shortest paths may be exponential in size.

-

A shortest path can be found quite efficiently by Dijkstra's algorithm (at least if we assume that distances can be computed and compared efficiently). There are (modern) algorithms for the geometric case with better theoretical properties, but for practical use a good (and "classic") heuristic algorithm is A* search.

-