Polygon intersection

Question

There are two polygons. How can you determine if one polygon is inside, outside, or intersects another polygon? Polygons can be concave or convex.

Answer 1

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

You can perform various tricks to reduce the amount of these calculations that you must perform, for example, you can draw a rectangle around an object and assume that if two rectangles of objects do not intersect, they themselves do not intersect. (This is simpler because it is less computationally expensive to check the intersection of these boxes and is usually quite intuitive.)

Concave polygons are harder. I think you can decompose a polygon into many convex polygons and try to check every intersection combination, but I would not find myself qualified enough in this area to try.

Answer 2

As a rule, such problems are easily solved with the help of a sweep algorithm. However, the main purpose and advantage of using the sweep approach is that it can effectively solve the problem when the input consists of two relatively large sets of polygons. Once a scan line solution is implemented, it can also be effectively applied to a pair of polygons, if necessary. You might want to consider moving in that direction if you need to solve a huge 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 using sequential tests such as point-vs-polygon and segment-vs-polygon.

Answer 3

Here is a simple algorithm to find out 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 segment of line A intersects a segment of line B, then two polygons intersect each other.
• If all points of the polygon A are inside the polygon B, then A is inside B.
• If all points of the polygon B are inside the polygon A, then B is inside A.
• If all points of the polygon A are outside B, then A is outside B.
• Two more polygons intersect each other.

Answer 4

There is an easy way to check if a point is in a polygon. According to this Wikipedia article, it is called a ray casting algorithm.

The main idea of ​​the algorithm is that you throw a ray in any arbitrary direction from the point you are testing, and calculate how many edges the polygon 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 problems with this algorithm that I will not delve into (they are discussed in the Wikipedia article that I linked earlier), but this is the reason why I call this algorithm easy. But in order to give you an idea, you have to handle corner cases using intersecting vertex rays, a ray that runs in parallel and intersects boundary and numerical stability problems with a point lying close to the edge.

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