Area of rectangle-rectangle intersection

问题:

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.

回答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?

回答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.

回答3:

You can calculate the intersection points by solving intersection equations for all pairs of sides of the figures: /frac{x - a}{b - a} = /frac{x - c}{d - c}

The points that you obtain in such a fashion can lie on the sides of the paralelepide, though they must not. You have to check whether the intersection points you obtained by solving the equations lie on the sides of the figure or not. If they do, you can calculate the length of the sides of the figure that stretch out into the inside of the both figures, and calculate the square of the intersection by taking their multiple.

I guess my method sounds a bit over-complicated, but this is the first thought that came to my mind.

回答4:

It may help to think of the problem in terms of triangles instead of rectangles. Finding the area of a triangle given three points in space is relatively straight forward.

You can find the intersecting area by subtracting the rectangle area by the sum of the areas of the triangles as shown in the image below.

Essentially it becomes a triangulation problem.

There is a good intro here with some pointers on data structures and algorithms.

EDIT:

There are some free triangulation libraries that you could reuse.

If you know the area of the two triangles you are starting off with you can find the total area of the union of the rectangles, so the intersection would be the total area of both rectangles - the union area.

回答5:

If you happen to use Qt then the intersection can be computed as QPolygonF intersection. Roughly as so:

QPolygonF p1,p2, intersected;
p1 << QPointF(r1x1,r1y1) << ... << QPointF(r1x4, r1y4);
p2 << QPointF(r2x1,r2y2) << ... << QPointF(r2x4, r2y4);
intersected = p1.intersected(p2);

float area = polyArea(intersected); // see code block below

(r1 = rectangle 1, r2 = rectangle 2, with 4 respective x and y coordinates).

Now compute the area (using the already mentioned Shoelace formula):

inline float polyArea(const QPolygonF& p)
{
    //https://en.wikipedia.org/wiki/Polygon#Area_and_centroid
    const int n = p.size();
    float area = 0.0;
    for (int i=0; i<n; i++)
    {
        area += p[i].x()*p[(i+1)%n].y() - p[(i+1)%n].x()*p[i].y();
    }
    if (area < 0)
        return -0.5*area;
    else
        return 0.5*area;
}

My code here: public domain

回答6:

Maybe you need to use opencv. Use the fillPoly() function to generate a rectangle. Make sure the fill rectangle is white (255, 255, 255). Then use the copyTo() function and you will get the overlap area. Then check the value of each pixel , if it is white then +1.