Find area of overlapping rectangles in Python / OpenCV with a raw list of points

Question

I have the coordinates x1, y1, x2, y2 of a rectangle and a list of other coordinates for other rectangles.

I want to compare the value of the one I already have over with the others to see if they overlap more than 50% of the original rectangle.

I checked other resources but still, I could get my head around it:

• https://codereview.stackexchange.com/questions/151309/check-if-two-rectangles-overlap
• https://codereview.stackexchange.com/questions/31352/overlapping-rectangles

Thigmotaxis

Answer 1

Let's first simplify your problem to a single dimension:

You have an interval A = [a0, a1] and want to find out how much does another interval B = [b0, b1] intersects with it. I will represent A with = and B with -.

There are 6 possible scenarios:

• A contains B, intersection = b1 - b0

  a0  b0  b1  a1
  ==============
      ------
  

• B contains A, intersection = a1 - a0

  b0  a0  a1  b1
      ======
  --------------
  

• B intersects A from the left, intersection = b1 - a0

  b0  a0  b1  a1
      ==========
  ----------
  

• B intersects A from the right, intersection = a1 - b0

  a0  b0  a1  b1
  ==========
      ----------
  

• B is to the left of A, intersection = 0

  b0  b1  a0  a1
          ======
  ------
  

• B is to the right of A, intersection = 0

  a0  a1  b0  b1
  ======
          ------
  

Based on that, we can define a function that, given two intervals A = [a0, a1] and B = [b0, b1], returns how much they intersect:

def calculateIntersection(a0, a1, b0, b1):
    if a0 >= b0 and a1 <= b1: # Contained
        intersection = a1 - a0
    elif a0 < b0 and a1 > b1: # Contains
        intersection = b1 - b0
    elif a0 < b0 and a1 > b0: # Intersects right
        intersection = a1 - b0
    elif a1 > b1 and a0 < b1: # Intersects left
        intersection = b1 - a0
    else: # No intersection (either side)
        intersection = 0

    return intersection

That's pretty much everything you need. To find out how much do two rectangles intersect, you just need to execute this function on both the X and the Y axis and multiply those amounts to get the intersecting area:

# The rectangle against which you are going to test the rest and its area:
X0, Y0, X1, Y1, = [0, 0, 10, 10]
AREA = float((X1 - X0) * (Y1 - Y0))

# Rectangles to check
rectangles = [[15, 0, 20, 10], [0, 15, 10, 20], [0, 0, 5, 5], [0, 0, 5, 10], [0, 5, 10, 100], [0, 0, 100, 100]]

# Intersecting rectangles:
intersecting = []

for x0, y0, x1, y1 in rectangles:       
    width = calculateIntersection(x0, x1, X0, X1)        
    height = calculateIntersection(y0, y1, Y0, Y1)        
    area = width * height
    percent = area / AREA

    if (percent >= 0.5):
        intersecting.append([x0, y0, x1, y1])

The result will be:

• [15, 0, 20, 10] does not intersect in the X-axis, so width = 0.
• [0, 15, 10, 20] does not intersect in the Y-axis, so height = 0.
• [0, 0, 5, 5] intersects only 25%.
• [0, 0, 5, 10] intersects 50% and will be added to intersecting.
• [0, 5, 10, 100] intersects 50% and will be added to intersecting.
• [0, 0, 100, 100] intersects 100% and will be added to intersecting.

Purington

Answer 2

The overlap area is the product of the overlap width and the overlap height.

To find the width overlap of the rectangles XY and xy, take the rightmost of the left edges and the leftmost of the right edges. Numerically, max(X1, x1) and min(X2, x2). Thus the overlap width is min(X2, x2) - max(X1, x1). If this is negative, there is no overlap at all. Repeat for the height.

Thus, the area of overlap can be expressed with a single formula:

max(0, min(X2, x2) - max(X1, x1)) . max(0, min(Y2, y2) - max(Y1, y1))

[Total cost: six comparisons, two subtractions, one product (plus one comparison to the target area).]

As a micro-optimization, you can conclude "no" immediately if

min(X2, x2) - max(X1, x1) < 50% (X2 - X1)

[With some probability, the cost is reduced to three comparisons and one subtraction.]

Petr