两个矩形重叠多少？

Question

我有两个矩形 a 和 b，它们的边平行于坐标系的轴。我的坐标为 x1,y1,x2,y2。

我试图确定，它们不仅重叠，而且重叠了多少？我试图弄清楚它们是否真的是相同的矩形，是否有一点回旋余地。那么它们的面积是95%一样吗？

对计算重叠百分比有帮助吗？

Answer 1

计算交集的面积，它也是一个矩形：

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

从那里您可以计算并集的面积：

SU = SA + SB - SI

您可以考虑比率

SI / SU

（在完美重叠的情况下为 100%，低至 0%）。

Answer 2

虽然 接受的答案是正确的，但我认为值得以一种能够完全阐明答案的基本原理的方式探索这个答案明显的。这是一种太常见的算法，不可能有不完整的（或更糟糕的是，有争议的）答案。此外，如果只浏览一下给定的公式，您可能会错过算法的优美性和可扩展性，以及正在做出的隐式决策。

我们将构建使这些公式直观的方法：

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)

首先，考虑定义二维框的一种方法是：

• (x, y) 代表左上角点
• (x, y) 代表右下角

这可能看起来像：

我用三角形表示左上角，用圆圈表示右下角。这是为了避免像本例中的 x1, x2 这样的不透明语法。

两个重叠的矩形可能如下所示：

请注意，要找到重叠，您要寻找橙色和蓝色碰撞的位置：

一旦你认识到这一点，很明显重叠是以下结果的结果找到并乘以这两条深色线：

每条线的长度是两个圆点的最小值减去两个三角形点的最大值。

在这里，我使用双色调三角形（和圆形）来显示橙色点和蓝色点的相互比较。双色三角形后面的小写字母“y”表示沿 y 轴比较三角形，小写“x”表示沿 x 轴比较。

例如，要查找深蓝色线的长度，您可以看到比较三角形以查找两者之间的最大值。比较的属性是 x 属性。三角形之间的最大 x 值为 210。

同样的事情的另一种说法是：
通过从直线最远侧的最近点减去直线最近侧的最远点来找到适合橙色线和蓝色线的新线的长度。

找到这些线可以提供有关重叠区域的完整信息。

一旦你有了这个，找到重叠的百分比就很简单了：

但是等等，如果橙色矩形不与蓝色矩形重叠，那么您将有问题：

在这个示例中，我们的重叠区域的值为 -850，这是不对的。更糟糕的是，如果检测不与任一维度重叠（x 轴或 y 轴均不重叠），那么您仍然会得到正数，因为两个维度均为负数。这就是为什么您将 Max(0, ...) * Max(0, ...) 视为解决方案的一部分；它确保如果任何重叠为负数，您将从函数中得到 0。

与我们的符号系统保持一致的最终公式：

值得注意的是，可能不需要使用 max(0, ...) 函数。您可能想知道某物是否沿其某个维度而不是所有维度重叠；如果您使用 max 那么您将删除该信息。因此，请考虑如何处理不重叠的边界框。通常，max 函数很好用，但值得了解它在做什么。

最后，请注意，由于此比较仅涉及线性测量，因此可以缩放到任意尺寸或任意重叠的四边形。

总结一下：

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)

Answer 3

我最近也遇到了这个问题并应用了 Yves 的答案，但不知何故导致了错误的区域大小，所以我重写了它。

假设有两个矩形 A 和 B，找出它们重叠的程度，如果重叠，则返回面积大小：

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

Answer 4

只需修复之前的答案，使比率介于 0 和 1 之间（使用 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

输出将是：

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

Answer 5

假设矩形必须平行于 x 和 y 轴，因为这似乎是前面的评论和答案的情况。

我还不能发表评论，但我想指出，前面的两个答案似乎都忽略了一侧矩形完全位于另一个矩形一侧的情况。如果我错了，请纠正我。

考虑这种情况

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

在这种情况下，我们看到对于交集，高度必须为 bTop - bBottom 因为 b 的垂直部分完全包含在 a 中代码>.

我们只需要添加更多情况，如下所示：（如果将顶部和底部视为与右侧和左侧相同，则可以缩短代码，这样您就不需要将条件块复制两次，但这应该可以。）

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

Answer 6

这是 C# 中的一个工作函数：

    public double calculateOverlapPercentage(Rectangle A, Rectangle B)
    {
        double result = 0.0;
        //trivial cases
        if (!A.IntersectsWith(B)) return 0.0; 
        if (A.X == B.X && A.Y == B.Y && A.Width == B.Width && A.Height == B.Height) return 100.0;


        //# overlap between A and B
        double SA = A.Width * A.Height;
        double SB = B.Width * B.Height;
        double SI = Math.Max(0,  Math.Min(A.Right, B.Right) - Math.Max(A.Left, B.Left)) *
                    Math.Max(0, Math.Min(A.Bottom, B.Bottom) - Math.Max(A.Top, B.Top));
        double SU = SA + SB - SI;
        result = SI / SU; //ratio
        result *= 100.0; //percentage
        return result;
    }

Answer 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

Answer 8

@User3025064 是正确的，并且是最简单的解决方案，但是，必须首先检查不相交的矩形的排他性，例如矩形 A 和 A 。 B（在 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

Answer 9

@user3025064 的答案是正确答案。接受的答案无意中翻转了内部 MAX 和 MIN 调用。
如果我们使用给出的公式 MAX(0,x) 而不是 ABS(x)，我们也不需要首先检查它们是否相交。如果它们不相交，MAX(0,x) 返回零，这使得相交区域为 0（即不相交）。

我建议 @Yves Daoust 修正他的答案，因为它是任何搜索该问题的人都会弹出的公认答案。再次，这是正确的交集公式：

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

其余如常。并集：

SU = SA + SB - SI

和比率：

SI/SU