how to find out if a shape is passable

I have a complex polygon (possibly concave) and a few of its edges marked as entry/exit points. there is a possibility that inside this polygon may lie one or more blockades of arbitrary shape. what approaches could I use to determine whether a path of certain width exist开发者_开发知识库s between a pair of entry/exit edges?

having read through the question it looks like a homework type - it is not. I just wish to have a at least a few leads I could pursue, as this is new to me.

Take a look at Motion Planning - there's a wealth of information there.

It depends on if the route needs to have a width to it. If the object that has to move through has a finite size, you need to take the Minkowski difference of your domain polygon with the moving object's polygon, then you try to route through that.

One way to compute paths exactly is to compute the visibility graph of the polygon. The visibility graph has vertices corresponding to the vertices of the domain polygon (possibly with holes where the obstacles are), and two vertices are connected by an edge if they can "see" each other. The shape is passable if there exists a set of edges joining an entry to an exit. You can also compute things like shortest paths. Computing the visibility graph in a naive way is not hard, but slow. There are very advanced algorithms for doing it, but they (AFAIK) have not been implemented. I tried implementing a few several years ago, with only mediocre results. Most of them assume vertices in general position, using exact arithmetic, whereas practical applications would use floating point numbers.