两个矩形重叠多少？

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

交叉的公式将是

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

那么工会将会是 S=SA+SB-SI

最后,比例将是SI / S.

Answer 3

虽然接受的答案是正确的,但我认为值得探索这个答案的方式将使答案的理由完全明显.这种算法太常见,不具备不完整(或更糟,有争议)的答案.此外,只要仔细瞥一眼给定的公式,您就可能会错过算法的美感和可扩展性,以及正在做出的隐含决策.

首先,考虑一种定义二维框的方法是:

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

这可能看起来像:

我指的是左上角有一个三角形,右下角有一个圆圈.这是为了避免像x1, x2这个例子那样的不透明语法.

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

请注意,要查找重叠,您需要查找橙色和蓝色碰撞的位置:

一旦你意识到这一点,很明显重叠是找到并乘以这两条黑暗线条的结果:

每条线的长度是我们希望比较的线之间的圆点的最小值,减去三角形点的最大值.

在这里,我使用双色调的形状来表明橙色和蓝色都进行了比较.形状后面的小写字母表示沿该轴比较三角形.

例如,在上一个图像的顶部公式中,您可以看到橙色和蓝色三角形进行比较,以查找两者之间的最大值.比较的属性是x属性.橙色和蓝色三角形之间的最大x值为210.

说同样事情的另一种方法是:通过从最近侧的最远点减去线的最长边上的最近点,可以找到可以适合我们比较的两条线的线的长度.线.

查找这些线条可提供重叠区域的完整信息.

一旦你有了这个,找到重叠的百分比是微不足道的:

但是等一下,如果橙色矩形与蓝色矩形不重叠,那么你将遇到问题:

在这个例子中,我们的重叠区域得到-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)

Answer 4

我最近遇到了这个问题并应用了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 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

只修复以前的答案,使比率介于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