logo标签列表

两个矩形重叠的面积是多少？

algorithmmathgeometrybounding-box
61

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

我想要确定它们是否重叠以及它们重叠的程度。我想知道它们是否是相同的矩形，或者只是存在一些微小的差异。因此，我需要计算它们的面积是否相似，例如是否相似95%？

请帮助我计算它们重叠的百分比。

参见：计算AABB的IoU - Martin Thoma
这张图片提供了测试用例。到目前为止，我只确定了这8个案例。矩形B相对于矩形A可以在右上方、右下方、左上方、左下方。它们也可以相交或不相交。所有其他情况（如A和B的两条边有一个公共段，A和B的两个顶点重叠）都是上述情况的特例，其中两个坐标（如A.bottom和B.top）不是严格大于，而是大于或等于。 - Newton fan 01
我重新考虑了这个问题，并发现总共有36种情况。解释在这里：https://www.ultraimg.com/image/Ooyk。在此之前，像矩形B完全位于矩形A内（或矩形A完全位于矩形A内）的情况没有被包括在内。现在它们也被计算在内了。 - Newton fan 01
9个回答
86

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

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％)。

1
哇，这正是我想要的，谢谢！我之前没有正确地考虑它。引入联合概念是我所缺失的。谢谢！ - Patrick Collins
1
给出一个数值示例。 - user1196549
@YvesDaoust 我不得不为了自己的使用而翻译这些未记录的变量，所以我想分享一下我得到的内容。对于类BoundingBox，其中UpRt是一个点，LowLt也是一个点，方程（未编译）为Area = Max(0, Max(this.UpRt.x, other.UpRt.x) - Min(this.LowLt.x, other.LowLt.x)) * Max(0, Max(this.UpRt.y, other.UpRt.y) - Min(this.LowLt.y, other.LowLt.y)); 我没有尝试编译、运行或测试它，因为我不需要面积，只需要判断两个是否重叠，所以我在自己的代码中实际使用的更加高效。 - philologon
28
如果他标明变量是什么，那会好很多。 - Louis Hong
10
对于其他人，变量假定A是矩形A，B是矩形B；X是X维度，Y是Y维度；1是(顶部或左侧)点，而2是(底部或右侧)点。因此：XA2是矩形A右边的X值；XB2是矩形B右边的X值；XA1是矩形A左边的X值；XB1是矩形B左边的X值；YA2是矩形A底部的Y值；YB2是矩形B底部的Y值；YA1是矩形A顶部的Y值；YB1是矩形B顶部的Y值。最后，SI是交集区域的面积。 - Dan Nissenbaum
显示剩余3条评论
51
虽然接受的答案是正确的，但我认为值得探索一下这个答案，以使答案的基本原理完全明显。这是一个太常见的算法，不能有不完整（或更糟糕的是，有争议的）答案。此外，只是粗略地浏览给定的公式，你可能会错过算法的美和可扩展性，以及被做出的隐含决定。
我们将逐步建立起直观的公式：
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) 表示右下角

如图所示:

Example Rectangle

我用三角形表示左上角，用圆圈表示右下角，以避免使用类似 x1, x2 这样的语法。

两个重叠的矩形可能会像这样:

Two Rectangles

注意要找到它们的重叠区域，需要寻找橙色和蓝色相交的地方:

Rectangle Overlap

一旦您认识到这一点，就很容易发现，覆盖区域是通过找到这两条暗线并将其相乘得到的:

Defining Overlap

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

在这里，我使用了双调三角形（和圆形）来表示橙色和蓝色点的比较。在两个双音符音符后面的小写字母 'y' 表示三角形沿 y 轴进行比较，小写字母 'x' 表示它们沿 x 轴进行比较。

Finding Overlap

例如，要找到暗蓝色线的长度，您可以看到三角形是通过比较寻找两个三角形之间的最大值来进行比较的。进行比较的属性是 x 属性。两个三角形之间的最大 x 值为 210。

还有一种说法:

适配于两条直线的新线段的长度是从该线段上最近的一侧的最远点减去与另一条线段距离最近的一侧的最近点。

Showing Overlap

找到这些线会提供关于重叠区域的完整信息。

计算公式演示

一旦你有了这个，计算重叠百分比就很容易：

查找重叠百分比

但是，如果橙色矩形与蓝色矩形没有重叠，那么你会遇到问题：

最后注意事项：错误的例子

对于这个例子，您将为重叠区域得到-850，这肯定不对。更糟糕的是，如果检测不与任何维度重叠（不在x轴或y轴上），则仍将获得正数，因为两个维度都是负数。这就是为什么您在解决方案中看到Max(0, ...) * Max(0, ...)的原因；它确保如果任何重叠是负数，则从函数中返回0。

符号体系保持不变的最终公式：

公式

值得注意的是，使用max(0, ...)函数可能并不是必要的。您可能想知道某个物体是否沿着其维度重叠而不是所有维度;如果使用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)
感谢您的详细解释。如果边界框在另一个边界框内部怎么办？ - sam
2
@prb 拿这个方程式：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))，将其转化为数字，使得所有橙色三角形都比蓝色三角形大（但小于蓝色圆形），并且所有橙色圆形都比蓝色圆形小（但大于蓝色三角形）。请报告您的发现。 - Connor
有没有办法我们可以对多个边界框执行此操作？ - sam
@prb 要扩大矩形数量，增加每个形状比较的颜色数量。例如，如果有第三个绿色矩形，则可以查找 max(0, min(orange.circle.x, blue.circle.x, green.circle.x) - max(...。 - Connor
1
多好的解决方案！ - Luan Pham
9

我最近也遇到了这个问题，并尝试使用 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
6

使用Python来修正以前的答案，使比率在0和1之间：

    # (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
1
注意：此答案使用NumPy。 - rayryeng
@Alessio B 如果一个矩形在另一个矩形内部，该怎么办？ - sam
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
3

这是一个有效的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;
    }
2
[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
2

@User3025064是正确的，也是最简单的解决方案，但首先必须检查不相交的矩形的排他性，例如对于矩形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
1
@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
1
你确定吗？根据你的建议，我已经更新了正确的答案，但有30个人建议Yves是正确的答案，所以我希望你能再次检查你的假设。谢谢。 - Patrick Collins
尝试这个反例：两个并排的矩形不重叠，因此 XA1<XA2<XB1<XB2。根据Yves的说法，交集的宽度为： w = Max(0, Max(XA2, XB2) - Min(XA1, XB1)) = XB2-XA1，这是一个大矩形，包含了两个矩形之间的间隙。 在固定的公式中， w = Max(0, Min(XA2, XB2) - Max(XA1, XB1)) = Max(0, XA2-XB1) = 0，因为 XA2<XB1，所以 XA2-XB1<0。 w=0 表示没有交集。 - Hazem
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接