How to compute the shortest path in Euclidean enviroments with non-convex polygons

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

thanks

-

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.

-