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.

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

Answer 3

There is an easyish method to check whether a point lies in a polygon. According to this Wikipedia article it is called the ray casting algorithm.

The basic idea of the algorithm is that you cast a ray in some arbitrary direction from the point you are testing and count with how many of the edges of the polygon it intersects. If this number is even then the point lies outside the polygon, otherwise if it is odd the point lies inside the polygon.

There are a number of issues with this algorithm that I won't delve into (they're discussed in the Wikipedia article I linked earlier), but they are the reason I call this algorithm easyish. But to give you an idea you have to handle corner cases involving the ray intersecting vertices, the ray running parallel and intersecting an edge and numeric stability issues with the point lying close to an edge.

You can then use this method in the way Thomas described in his answer to test whether two polygons intersect. This should give you an O(NM) algorithm where the two polygons have N and M vertices respectively.

Answer 4

Here is a simple algorithm to know if a given point is inside or outside a given polygon:

bool isInside(point a, polygon B)
{
    double angle = 0;
    for(int i = 0; i < B.nbVertices(); i++)
    {
        angle += angle(B[i],a,B[i+1]);
    }
    return (abs(angle) > pi);
}

• If a line segment of A intersects a line segment of B then the two polygons intersect each other.
• Else if all points of polygon A are inside polygon B, then A is inside B.
• Else if all points of polygon B are inside polygon A, then B is inside A.
• Else if all points of polygon A are outside polygon B, then A is outside B.
• Else the two polygons intersect each other.