Check the overlapping area of two rectangles (tricky)


  • 5
    L

    I guess the most tricky part of this problem is to check whether two rectangles have an overlapping if so how to calculate it.

    So here is my "verbose" solution in Java. Hope it is self-explanatory.

    /**
     * Calculate the overlapping area of two rectangles.
     */
    public int overlapArea(int A, int B, int C, int D,
         			        int E, int F, int G, int H) {
    	/* Check if there is indeed an overlap.
         * e.g.  E >= C  i.e. the most left point of the rectangle (EFGH) is 
         *       on the right side of the most right point of the rectangle (ABCD),
         *       therefore there is no overlapping.
         */
    	if ( (E>=C) || (F>= D) || (A>=G) || (B >= H) )
    		return 0;
    
    	/* bottom left point of the overlapping area. */
    	int bl_x = Math.max(A, E);
    	int bl_y = Math.max(B, F);
    
    	/* top right point of the overlapping area. */
    	int tr_x = Math.min(C, G);
    	int tr_y = Math.min(D, H);
    	
    	return (tr_x - bl_x) * (tr_y - bl_y);
    }
    
    /**
     * Calculate the area of a single rectangle.
     */
    public int computeArea(int A, int B, int C, int D) {
    	return (C-A) * (D-B);
    }
    
    /**
     * Find the total area covered by two rectilinear rectangles in a 2D plane.
     * Each rectangle is defined by its bottom left corner and top right corner.
     */
    public int computeArea(int A, int B, int C, int D,
    					   int E, int F, int G, int H) {
    	// The addition of area of the two rectangles minus the overlapping area.
    	return computeArea(A, B, C, D) + computeArea(E, F, G, H) - 
    		   overlapArea(A, B, C, D, E, F, G, H);
    }

  • 0

    "bl" and "tr" aren't quite self-explanatory... (I know what the values are but I still don't know what your names mean)


  • 0
    L

    Thanks for pointing that out. I've added more comments in the code. Hope it is clearer now.


  • 0

    Aaah, yes, bottom-left and top-right makes sense. Thanks. I think the main reason I didn't get it was that I wasn't thinking of two corners. I was thinking of independent left, right, top and bottom. That's why I couldn't make the connection.


  • 0
    W

    Quite clean solution. Mine is a convoluted one!


  • 0
    W
     class Solution:
        def computeArea(self, A, B, C, D, E, F, G, H):
            SA=abs((C-A)*(D-B))
            SB=abs((G-E)*(H-F))
            if E>=C or A>=G or B>=H or F>=D:
                return SA+SB
            else:
                x1=min(G,C)
                x2=max(A,E)
                y1=min(D,H)
                y2=max(B,F)
                return SA+SB-abs((x1-x2)*(y1-y2))
    

  • 0
    W
    class Solution:
        def computeArea(self, A, B, C, D, E, F, G, H):
            SA=abs((C-A)*(D-B))
            SB=abs((G-E)*(H-F))
            if E>=C or A>=G or B>=H or F>=D:
                return SA+SB
            else:
                x1=min(G,C)
                x2=max(A,E)
                y1=min(D,H)
                y2=max(B,F)
                return SA+SB-abs((x1-x2)*(y1-y2))
    

  • 0
    L

    Good summary.


  • 1
    L

    Here I would like to add some additional explanation to the idea of checking whether two rectangles have an overlap.

                (C, D)              (G, H)
        |-------|           |--------|
        |       |           |        |
        |-------|           |--------|
    (A, B)                (E, F)
    

    As illustrated above, the four points that represent the two rectangles,
    actually delimit all the borders of each rectangle as well.

    We can say that E is the most left coordinate of rectangle(E, F, G, H)
    and C is the most right coordinate of rectangle(A, B, C, D).

    If E >= C, i.e. the most left coordinate of rectangle(E, F, G, H)
    is on the right side of rectangle(A, B, C, D),
    then we can be sure that there is no overlap between the two rectangles.

    This condition is sufficient but not necessary to conclude the non-overlapping property of two rectangles.

    Following the same idea, we could derive the other 3 conditions, as they are symmetrical.


  • 0
    N

    Or sort the points along the x-axis and y-axis.

    int overlappingArea(int A, int B, int C, int D, int E, int F, int G, int H) {

        if(E>=C || F>=D || A>G || B>H)
            return 0;
        
        int x_axis[4] = {A,C,E,G};
        int y_axis[4] = {B,D,F,H};
        sort(x_axis,x_axis+4);
        sort(y_axis,y_axis+4);
        
        return (x_axis[2] - x_axis[1]) * (y_axis[2] - y_axis[1]);
    

    }


  • 0
    W

    For the sake of completeness, the 'if' condition should have A>=G and B>=H, since there would be no overlap if they are equal. It would still be handled later since difference will be 0, so product will be zero. But better to handle it before and say that there is no overlap at all.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.