使用Python / OpenCV查找重叠矩形的区域，给定一个原始点列表。

Question

我有一个矩形的坐标，包括x1, y1, x2, y2，以及其他矩形的坐标列表。我想比较已有矩形与其他矩形的重叠情况，判断它们是否与原始矩形的重叠面积超过50%。我查看了其他资源，但仍然无法理解。以下是相关资源链接：

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

- Alexis

Answer 1

首先，让我们把你的问题简化为一个维度：

你有一个区间 A = [a0, a1]，想知道另一个区间 B = [b0, b1] 与它相交的程度。我会用 = 表示 A，用 - 表示 B。

有6种可能的情况：

• 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
  ======
          ------
  

基于此，我们可以定义一个函数，给定两个区间 A = [a0, a1] 和 B = [b0, b1]，返回它们相交的部分大小:

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

那基本上就是你需要的全部内容了。要找出两个矩形相交的面积，只需在X和Y轴上执行此函数，并将这些数量相乘即可：

# 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])

结果将是：

• [15, 0, 20, 10] 在X轴上没有交集，因此 width = 0。
• [0, 15, 10, 20] 在Y轴上没有交集，因此 height = 0。
• [0, 0, 5, 5] 只有 25% 的交集。
• [0, 0, 5, 10] 有 50% 的交集，将添加到 intersecting 中。
• [0, 5, 10, 100] 有 50% 的交集，将添加到 intersecting 中。
• [0, 0, 100, 100] 有 100% 的交集，将添加到 intersecting 中。

- Danziger

Answer 2

重叠区域是重叠宽度和重叠高度的乘积。

要找到矩形XY和xy的宽度重叠，取左边缘最右侧和右边缘最左侧。数值上，为max(X1, x1)和min(X2, x2)。因此，重叠宽度为min(X2, x2) - max(X1, x1)。如果这个值为负数，则没有重叠。重复以上步骤计算高度。

因此，重叠面积可以用一个公式表示：

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

[总成本：六次比较，两次减法，一次乘法（加上一次与目标区域的比较）]

作为微观优化，如果您可以立即得出“否定”结论，则可以立即得出“否定”结论。

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

[有一定的概率，成本将降低到三次比较和一次减法。]

- user1196549