algorithm - 两个矩形重叠多少？

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

虽然给出的公认答案是正确的，但我认为值得以一种使答案的基本原理完全显而易见的方式探索这个答案。这是一种太常见的算法，无法给出不完整（或更糟糕，有争议）的答案。此外，只看一眼给定的公式，您可能会错过算法的美感和可扩展性，以及正在做出的隐含决策。

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

• (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。

我们只需要添加更多的情况如下：（如果将top和bottom视为左右相同的东西，可以缩短代码，这样您就不需要复制两次条件块，但应该这样做。）

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

@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

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

这是 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 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