c - Intersection of polygons

Question

There are two polygons given. how can one determine whether one polygon is inside, outside or intersecting the other polygon? Polygons can be Concave or convex.

Answer 1

You want to use the separating axis theorem for convex polygons. Basically, for each face of each polygon you project each polygon onto the normal of that face and you see if those projections intersect.

You can perform various tricks to reduce the number of these computations that you have to perform- for example, you can draw a rectangle around the object and assume that if two objects' rectangles do not intersect, they themselves do not intersect. (This is easier because it's less computationally expensive to check the intersection of these boxes, and is generally quite intuitive.)

Concave polygons are more difficult. I think that you could decompose the polygon into a set of convex polygons and attempt to check each combination of intersection, but I wouldn't consider myself skilled enough in this area to try it.