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.

Solution 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.

Solution 2

Generally, problems like that are solved easily by a sweep-line algorithm. However, the primary purpose and benefit of using the sweep-line approach is that it can solve the problem efficiently when input consists of two relatively large sets of polygons. Once the sweep line solution is implemented, it can also be efficiently applied to a pair of polygons, if need arises. Maybe you should consider moving in that direction, in case you'll need to solve a massive problem in the future.

However, if you are sure that you need a solution for two and only two polygons , then it can be solved by a sequential point-vs-polygon and segment-vs-polygon tests.