Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

enter image description here

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

share|improve this question
    
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
1  
@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
add comment

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.