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