计算三个矩形中至少一个所覆盖的面积

Question

我有一个问题，我需要计算三个矩形中至少一个矩形所覆盖的面积。

我定义了一个函数 calculate 如下（为清楚起见，对冗余变量表示歉意）：

def calculate(rec1, rec2, rec3):
    if rec1 == rec2 == rec3:
        return abs((rec1[1]-rec1[3])) * abs(rec1[0]-rec1[2])
    else:        
        area1 = abs((rec1[1]-rec1[3])) * abs(rec1[0]-rec1[2])
        area2 = abs((rec2[1]-rec2[3])) * abs(rec2[0]-rec2[2])
        area3 = abs((rec3[1]-rec3[3])) * abs(rec3[0]-rec3[2])
 
        xmin1, ymin1, xmax1, ymax1 = rec1[0], rec1[3], rec1[2], rec1[1]
        xmin2, ymin2, xmax2, ymax2 = rec2[0], rec2[3], rec2[2], rec2[1]
        xmin3, ymin3, xmax3, ymax3 = rec3[0], rec3[3], rec3[2], rec3[1]
 
        area12 = (min(xmax1, xmax2) - max(xmin1, xmin2)) * (min(ymax1, ymax2) - max(ymin1, ymin2))
        area13 = (min(xmax1, xmax3) - max(xmin1, xmin3)) * (min(ymax1, ymax3) - max(ymin1, ymin3))
        area23 = (min(xmax2, xmax3) - max(xmin2, xmin3)) * (min(ymax2, ymax3) - max(ymin2, ymin3))
        
        return (area1 + area2 + area3) - (area12 + area13 + area23)

但是，这似乎不起作用。我在公式中缺少什么？ area12、area13 和 area23 是最后两位数字表示的相交三角形的面积，例如 area12 是 rec1 的相交面积和 rec2.

对于输入（(x1,y1)表示左上角，(x2,y2)表示右下角）

(2,-1,3,-3),
(0,2,3,0),
(-3,0,1,-1)

我应该得到 12 的输出，但我得到 13 并且简单地将 +1 添加到 return 值在其他测试用例中不起作用。

Answer 1

您要查找的是矩形并集的面积。

在两个矩形的情况下，这个面积是各个面积的总和减去交集的面积。有趣的是，交点也是一个矩形（或空心）。如果我们用 & 表示交集，用 | 表示并集，我们有

Area(A | B) = Area(A) + Area(B) - Area(A & B).

概括为三个矩形，我们可以想象上面的并集是由两个正矩形和一个负矩形组成的。因此

Area(A | B | C) = Area((A | B) | C)
 = Area(A) + Area(C) - Area(A & C) + Area(B) + Area(C) - Area(B & C) - Area(A & B) - Area(C) + Area(A & B & C)
 = Area(A) + Area(B) + Area(C) - Area(B & C) - Area(C & A) - Area(A & B) + Area(A & B & C).

那么求两个矩形的交集面积只要考虑左边两条边的最右边和右边两条边的最左边即可。如果它们交叉，则交叉点为空。否则它们的距离就是交叉点的宽度。类似的推理给你身高。

计算三个矩形中至少一个所覆盖的面积

Calculating the area covered by at least one of three rectangles

python

computational-geometry