# 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.

-