# How can I compute the shortest path in Euclidean environments with non-convex polygons?

Can someone suggest papers or algorithms about calculating shortest paths in Euclidean spaces with non-convex polygon as obstacles?

-
Note that unless your start point, end point or another polygon lies in the space between a non-convex polygon and its convex hull, you can replace the non-convex polygon by its complex hull. Easy to see by just drawing a non-convex polygon and its convex hull, then considering which shortest paths go through the difference. – MSalters Jan 24 '14 at 8:28

The simplest approach is to turn the non-convex polygons into multiple convex ones, then do normal convex collision and pathfinding (via A* or D* or whatever). The first process is often called triangulation in computational geometry, and there are several common ways to do it.

-

This may not be the exact answer to your question but I may suggest you an approach on this issue.

Actually your problem is two problems combined.

1. Finding shortest paths
2. Finding collisions

And the second problem is embedded into first. I may recommend understanding blind search first. Here's a very simple presentation about it: Blind Search

If you read the document for building the state space, you will need to generate state points and they must be legal meaning these states can be on your shortest path so they shouldn't collide with any objects in your space. From now on you can continue with Euclidian collision algorithms. After building your state space and search tree restricted with collisions you may chose any of the shortest path algorithms or one of your own or a modified hybrid one.

-