CODEWITHSUNDEEP
pythoncomputational-geometry
user13541811
user13541811

Reputation:

Calculating the area covered by at least one of three rectangles

I have a problem where I would need to calculate the area covered by at least one of three rectangles.

I've defined a function calculate as follows (apologies for the redundant variables it was for clarity):

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)

However, this seems to be not working. What am I missing in the formula? area12, area13 and area23 are the areas of the intersecting triangles denoted by the last two digits in the end e.g area12 is the area of intersection for rec1 and rec2.

For the input ((x1, y1) denotes the left upper corner and (x2,y2) right lower corner)

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

I should get an output of 12, but I get 13 and simply adding +1 to the return value doesn't work in other test cases.

Upvotes: 1

Views: 536

Answers (1)

user1196549
user1196549

Reputation:

What you are looking for is the area of the union of the rectangles.

In the case of two rectangles, this area is the sum of the individual areas minus the area of the intersection. It is interesting to note that the intersection is also a rectangle (or empty). If we denote the intersection by & and the union by |, we have

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

To generalize to three rectangles, we can imagine that the above union is made of two positive rectangles and a negative one. Hence

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).

Then to find the area of the intersection of two rectangles it suffices to consider the rightmost of the two left sides and the leftmost of the two rights sides. If they are crossed, the intersection is empty. Otherwise their distance is the width of the intersection. A similar reasoning gives you the height.

Upvotes: 1

Related Questions