Find if two areas intersect given the polygons` edges

Question

This problem has been puzzling me for some time now. I did find a solution where I can find every point in each polygon, then check for intersections. However, this is computationally expensive, and not practical at all.

There are four lines in the following image; two red and two blue lines. I would like to check if the area between the two red lines intersects with the area between the two blue lines.

The following variables are known:

1. The point where each line starts
2. Angle of each line
3. Where the line ends (always at image's edge)

I was thinking about using the slope's formula to check where does the origin point of the red lines falls in relation to each blue line. But I'm not sure if this was the best approach.

Thanks in advance.

Answer 1

There are principally two approaches to this problem:

1. Linear programming

Express the problem as a system of linear inequalities and solve it as a linear programming problem as described here: Solve a system of linear equations and linear inequalities. In your case the inequalities will be of the form (x - ox[i])*sin(a[i]) - (y - oy[i])*cos(a[i]) > 0 or (x - ox[i])*sin(a[i]) - (y - oy[i])*cos(a[i]) < 0 depending on how you define the angle a[i] of the i-th line and at which side of the line lays the polygon. (ox[i], oy[i]) are coordinates of the i-th vertex. If the inequalities are strict or not, that depends on how you want to treat boundary cases where the polygons touch with a vertex or an edge. This is a good easily generalizable approach, but it may be slow.

2. Intersection testing

In the general case (no vertices and edges coincide) there are 4 possibilities: (1) some edges intersect; (2) polygon 1 is inside polygon 2; (3) polygon 2 is inside polygon 1; (4) polygons do not intersect. You need to test for the first 3 cases.

For case 1 you need to implement a segment intersection test as described here How can I check if two segments intersect? and try to intersect each edge of polygon 1 with each edge of polygon 2, which is not a problem in your case because there will be at most 2*2 = 4 tests. If you detect at least one intersection, you are done.

For cases 2 and 3 you need to test if the vertex of polygon 1 is inside polygon 2 and vice versa. This may be done using the same tests IsOnLeft and IsOnRight described in How can I check if two segments intersect?: if a point is at the left of the right line and at the right of the left one, it is inside.

In any case you should pay special attention to degenerate and boundary cases: what if edges of a polygon coincide, or a vertex of one polygon lays on an edge of the other, or edges of different polygons coincide. You may detect and treat such cases differently depending on your particular purposes.