How to know if a form is passable
I have a complex polygon (possibly concave) and several edges of it marked as in / out points. there is a possibility that one or more freeform blocks may be inside this polygon. What approaches could I use to determine if there is a path of a specific width between a pair of in / out edges?
after reading the question it looks like a type of homework - it is not. I just want to have at least a few bends that I can pursue as this is new to me.
a source to share
It depends on whether the route should be wide. If the object to be traversed is of finite size, you need to take the Minkowski difference of your domain polygon to the moving object's polygon, then you will try to traverse that.
One way to compute paths is to compute the visibility graph of the polygon. The visibility graph has vertices that correspond to the vertices of the area polygon (possibly with holes where there are obstacles), and two vertices are connected by an edge if they can "see" each other. The form is skipped if there are many edges connecting the record to the output. You can also compute things like shortest paths. Computing the visibility graph in a naive way is not difficult, but slow. There are very advanced algorithms for this, but they (AFAIK) have not been implemented. I tried to implement it a few years ago with only mediocre results. Most of them assume vertices in general position using exact arithmetic, while practical applications will use floating point numbers.
a source to share