Area of rectangle-rectangle intersection

Question

Below are 2 rectangles. Given the coordinates of the rectangle vertices - (x1, y1)...(x8, y8), how can the area of the overlapping region (white in the figure below) be caclulated?

Note that:

1. Coordinates of points might be any
2. Rectangles may or may not overlap
3. Assume area is 0 when rectangles don't overlap, or they overlap at point or line.
4. If one rectangle is inside the other, then calculate area of smaller rectangle.

Answer 1

Since you stated that the rectangles may not be aligned, possible answers may be nothing, a point, a line segment, or a polygon with 3-8 sides.

The usual way to do this 2d boolean operation is to choose a counterclockwise ordering of the edges, and then evaluate edge segments between critical points (intersections or corners). At each intersection you switch between an edge segment of the first rectangle to an edge of the second, or visa-versa. You always pick the segment to the left of the previous segment.

There are LOTS of details, but the basic algorithm is to find all intersections and order them on their edges with an appropriate data structure. Choose an intersection (if there is one) and choose a line segment leading away from that intersection. Find the segment of the other rectangle to the left of the chosen starting segment. In the picture, we choose the green segment on intersection a (in the direction indicated by the arrow) as the reference segment. The segment of the other rectangle that is to the right, is the segment from a to b. Use that as the next reference segment, and choose a green segment to the left of it. That's the segment from b to c. Find segment cd the same way. The next segment is from d to the corner, so the corner is in the vertex list for the intersection as well. From the corn we get back to a.

To choose the left side each time, you use the determinate of the coordinates of the direction vectors for the edges that meet. If the determinant for the ordered pair of directed edges is positive, you're going the right way.

Now that you have the vertices of the intersection polygon, you can use the surveyor's formula to get the area.

Some of the details that I'm leaving to you are:

• What if a corner is coincident to to an edge or vertex of the other triangle?

• What if there are no intersections? (one rectangle is inside the other, or they are disjoint--you can use point-in-polygon checks to figure this out. See the Wikipedia article on polygons.

• What if the intersection is a single point or a segment?

Answer 2

There is another way that you may find interesting, but maybe not applicable in this case, and that is:

1. determine the minimum rectangle( whose sides are parallel to coordinate axes ) that contains both of the given rectangles, lets call that new one a bounding box.
2. pick a random dot that is in the bounding box and check whether it is in both rectangles or not
3. repeat step 2 for as long as you want( it depends on the precision you want for your result ), and have two counters, one to keep track of the number of dots inside both of the rectangles, and the other which is the number of repetitions of step 2

4. the final solution is the area of the bounding box multiplied by the number of dots inside both rectangles and then divided by number of repetitions of step 2, or in a form of a formula:

   intersection_area = bounding_box_area * num_of_dots_inside_both / num_of_repetitions

The result will, of course, be more precise when the number of repetitions is larger. By the way, this method is called Monte Carlo method.