How much do two rectangles overlap?

问题:

I have two rectangles a and b with their sides parallel to the axes of the coordinate system. I have their co-ordinates as x1,y1,x2,y2.

I'm trying to determine, not only do they overlap, but HOW MUCH do they overlap? I'm trying to figure out if they're really the same rectangle give or take a bit of wiggle room. So is their area 95% the same?

Any help in calculating the % of overlap?

回答1:

Compute the area of the intersection, which is a rectangle too:

SI = Max(0, Min(XA2, XB2) - Max(XA1, XB1)) * Max(0, Min(YA2, YB2) - Max(YA1, YB1))

From there you compute the area of the union:

SU = SA + SB - SI

And you can consider the ratio

SI / SU

(100% in case of a perfect overlap, down to 0%).

回答2:

The formula for intersection will be

SI= Max(0, Min(XA2, XB2) - Max(XA1, XB1)) * Max(0, Min(YA2, YB2) - Max(YA1, YB1))

then the union will be S=SA+SB-SI

And finally, the ratio will be SI / S.

回答3:

I recently ran into this problem as well and applied Yves' answer, but somehow that led to the wrong area size, so I rewrote it.

Assuming two rectangles A and B, find out how much they overlap and if so, return the area size:

IF A.right < B.left OR A.left > B.right
    OR A.bottom < B.top OR A.top > B.bottom THEN RETURN 0

width := IF A.right > B.right THEN B.right - A.left ELSE A.right - B.left
height := IF A.bottom > B.bottom THEN B.bottom - A.top ELSE A.bottom - B.top

RETURN width * height

回答4:

Just fixing previous answers so that the ratio is between 0 and 1 (using Python):

    # (x1,y1) top-left coord, (x2,y2) bottom-right coord, (w,h) size
    A = {'x1': 0, 'y1': 0, 'x2': 99, 'y2': 99, 'w': 100, 'h': 100}
    B = {'x1': 0, 'y1': 0, 'x2': 49, 'y2': 49, 'w':  50, 'h':  50}

    # overlap between A and B
    SA = A['w']*A['h']
    SB = B['w']*B['h']
    SI = np.max([ 0, 1 + np.min([A['x2'],B['x2']]) - np.max([A['x1'],B['x1']]) ]) * np.max([ 0, 1 + np.min([A['y2'],B['y2']]) - np.max([A['y1'],B['y1']]) ])
    SU = SA + SB - SI
    overlap_AB = float(SI) / float(SU)
    print 'overlap between A and B: %f' % overlap_AB

    # overlap between A and A
    B = A
    SB = B['w']*B['h']
    SI = np.max([ 0, 1 + np.min([A['x2'],B['x2']]) - np.max([A['x1'],B['x1']]) ]) * np.max([ 0, 1 + np.min([A['y2'],B['y2']]) - np.max([A['y1'],B['y1']]) ])
    SU = SA + SB - SI
    overlap_AA = float(SI) / float(SU)
    print 'overlap between A and A: %f' % overlap_AA

The output will be:

    overlap between A and B: 0.250000
    overlap between A and A: 1.000000

回答5:

Assuming that the rectangle must be parallel to x and y axis as that seems to be the situation from the previous comments and answers.

I cannot post comment yet, but I would like to point out that both previous answers seem to ignore the case when one side rectangle is totally within the side of the other rectangle. Please correct me if I am wrong.

Consider the case

a: (1,1), (4,4)
b: (2,2), (5,3)

In this case, we see that for the intersection, height must be bTop - bBottom because the vertical part of b is wholly contained in a.

We just need to add more cases as follows: (The code can be shorted if you treat top and bottom as the same thing as right and left, so that you do not need to duplicate the conditional chunk twice, but this should do.)

if aRight <= bLeft or bRight <= aLeft or aTop <= bBottom or bTop <= aBottom:
    # There is no intersection in these cases
    return 0
else:
    # There is some intersection

    if aRight >= bRight and aLeft <= bLeft:
        # From x axis point of view, b is wholly contained in a
        width = bRight - bLeft
    elif bRight >= aRight and bLeft <= aLeft:
        # From x axis point of view, a is wholly contained in b
        width = aRight - aLeft
    elif aRight >= bRight:
        width = bRight - aLeft
    else:
        width = aRight - bLeft

    if aTop >= bTop and aBottom <= bBottom:
        # From y axis point of view, b is wholly contained in a
        height = bTop - bBottom
    elif bTop >= aTop and bBottom <= aBottom:
        # From y axis point of view, a is wholly contained in b
        height = aTop - aBottom
    elif aTop >= bTop:
        height = bTop - aBottom
    else:
        height = aTop - bBottom

return width * height

回答6:

While the accepted answer given is correct, I think it's worth exploring this answer in a way that will make the rationale for the answer completely obvious. This is too common an algorithm to have an incomplete (or worse, controversial) answer. Furthermore, with only a passing glance at the given formula, you may miss the beauty and extensibility of the algorithm, and the implicit decisions that are being made.

First, consider one way to define a two dimensional box is with:

• (x, y) for the top left point
• (x, y) for the bottom right point

This might look like:

I indicate the top left with a triangle and the bottom right with a circle. This is to avoid opaque syntax like x1, x2 for this example.

Two overlapping rectangles might look like this:

Notice that to find the overlap you're looking for the place where the orange and the blue collide:

Once you recognize this, it becomes obvious that overlap is the result of finding and multiplying these two darkened lines:

The length of each line is the minimum value of the circle point between the lines we wish to compare, minus the maximum value of the triangle points.

Here, I'm using the two-toned shape to show that both the orange and the blue are compared. The small letter after the shape indicates that the triangles are compared along that axis.

For example, in the top equation in this previous image you can see the orange and blue triangles are compared to look for the maximum value between the two. The attribute that is compared is the x attribute. The maximum x value between the orange and blue triangles is 210.

Another way to say the same thing is: the length of the line that can fit onto both of the lines that we are comparing is found by subtracting the closest point on the longest side of the line from the furthest point on the closest side of the line.

Finding those lines gives complete information of the overlapping areas.

Once you have this, finding the percentage of overlap is trivial:

But wait, if the orange rectangle does not overlap with the blue one then you're going to have a problem:

With this example, you get a -850 for our overlapping area, that can't be right. Even worse, if a detection doesn't overlap with either dimension (neither on the x or y axis) then you will still get a positive number because both dimensions are negative. This is why you see the Max(0, ...) * Max(0, ...) as part of the solution; it ensures that if any of the overlaps are negative you'll get a 0 back from your function.

The final formula in keeping with our symbology:

It's worth noting that using the max(0, ...) function may not be necessary. You may want to know if something overlaps along one of its dimensions rather than all of them; if you use max then you will obliterate that information. For that reason, consider how you want to deal with non-overlapping images. Normally, the max function is fine to use, but it's worth being aware what it's doing.

Finally, notice that since this comparison is only concerned with linear measurements it can be scaled to arbitrary dimensions or arbitrary overlapping quadrilaterals.

To summarize:

intersecting_area = 
max(0, min(orange.circle.x, blue.circle.x) - max(orange.triangle.x, blue.triangle.x)) * max(0, min(orange.circle.y, blue.circle.y) - max(orange.triangle.y, blue.triangle.y))

percent_coverage = intersecting_area / (orange_area + blue_area - intersecting_area)

回答7:

[ymin_a, xmin_a, ymax_a, xmax_a] = list(bbox_a)
[ymin_b, xmin_b, ymax_b, xmax_b] = list(bbox_b)

x_intersection = min(xmax_a, xmax_b) - max(xmin_a, xmin_b) + 1
y_intersection = min(ymax_a, ymax_b) - max(ymin_a, ymin_b) + 1

if x_intersection <= 0 or y_intersection <= 0:
    return 0
else:
    return x_intersection * y_intersection

回答8:

@User3025064 is correct and is the simplest solution, though, exclusivity must be checked first for rectangles that do not intersect e.g., for rectangles A & B (in Visual Basic):

If A.Top =< B.Bottom or A.Bottom => B.Top or A.Right =< B.Left or A.Left => B.Right then
    Exit sub   'No intersection
else
    width = ABS(Min(XA2, XB2) - Max(XA1, XB1))
    height = ABS(Min(YA2, YB2) - Max(YA1, YB1))
    Area = width * height      'Total intersection area.
End if

回答9:

The answer of @user3025064 is the right answer. The accepted answer inadvertently flips the inner MAX and MIN calls. We also don't need to check first if they intersect or not if we use the presented formula, MAX(0,x) as opposed to ABS(x). If they do not intersect, MAX(0,x) returns zero which makes the intersection area 0 (i.e. disjoint).

I suggest that @Yves Daoust fixes his answer because it is the accepted one that pops up to anyone who searches for that problem. Once again, here is the right formula for intersection:

SI = Max(0, Min(XA2, XB2) - Max(XA1, XB1)) * Max(0, Min(YA2, YB2) - Max(YA1, YB1))

The rest as usual. Union:

SU = SA + SB - SI

and ratio:

SI/SU