CODEWITHSUNDEEP
algorithm
al_khater
al_khater

Reputation: 369

total area of intersecting rectangles

I need an algorithm to solve this problem: Given 2 rectangles intersecting or overlapping together in any corner, how do I determine the total area for the two rectangles without the overlapped (intersection) area? Meaning the area of intersection has to be calculated once, either with the first rectangle, or with second one.

Upvotes: 36

Views: 51857

Answers (6)

George
George

Reputation: 3619

A Swift-version solution with analysis and LeetCode test results.

/**
 Calculate the area of intersection of two given rectilinear rectangles.

 - Author:
 Cong Liu <congliu0704 at gmail dot com>

 - Returns:
 The area of intersection of two given rectilinear rectangles.

 - Parameters:
 - K: The x coordinate of the lower left point of rectangle A
 - L: The y coordinate of the lower left point of rectangle A
 - M: The x coordinate of the upper right point of rectangle A
 - N: The y coordinate of the upper right point of rectangle A
 - P: The x coordinate of the lower left point of rectangle B
 - Q: The y coordinate of the lower left point of rectangle B
 - R: The x coordinate of the upper right point of rectangle B
 - S: The y coordinate of the upper right point of rectangle B

 - Assumptions:
 All the eight given coordinates (K, L, M, N, P, Q, R and S) are integers
 within the range [-2147483648...2147483647], that is, Int32-compatible.
 K < M, L < N, P < R, Q < S

 - Analysis:
 The area of intersected is dyIntersected * dxIntersected.

 To find out dyIntersected, consider how y coordinates of two rectangles relate
 to each other, by moving rectangle A from above rectangle B down.

 Case 1: when N >  L >= S >  Q, dyIntersected = 0
 Case 2: when N >= S >  L >= Q, dyIntersected = S - L
 Case 3: when S >  N >  L >= Q, dyIntersected = N - L
 Case 4: when S >= N >= Q >  L, dyIntersected = N - Q
 Case 5: when N >  S >  Q >  L, dyIntersected = S - Q
 Cases 2 and 3 can be merged as Case B:
         when           L >= Q, dyIntersected = min(N, S) - L
 Cases 4 and 5 can be merged as Case C:
         when           Q >  L, dyIntersected = min(N, S) - Q
 Cases B and C can be merged as Case D:
         when      S >  L     , dyIntersected = min(N, S) - max(L, Q)

 Likewise, x coordinates of two rectangles relate similarly to each other:
 Case 1: when R >  P >= M >  K, dxIntersected = 0
 Case 2: when      M >  P     , dxIntersected = min(R, M) - max(P, K)

 - Submission Date:
 Sat 20 Jan 2018 CST at 23:28 pm

 - Performance:
 https://leetcode.com/problems/rectangle-area/description/
 Status: Accepted
 3081 / 3081 test cases passed.
 Runtime: 78 ms
 */
class Solution {
  public static func computeArea(_ K: Int, _ L: Int, _ M: Int, _ N: Int, _ P: Int, _ Q: Int, _ R: Int, _ S: Int) -> Int {
    let areaA : Int = Int((M - K) * (N - L))
    let areaB : Int = Int((R - P) * (S - Q))
    var xIntersection : Int = 0
    var yIntersection : Int = 0
    var areaIntersection : Int = 0

    if ((min(M, R) - max(K, P)) > 0) {
      xIntersection = Int(min(M, R) - max(K, P))
    }

    if ((min(N, S) - max(L, Q)) > 0) {
      yIntersection = Int(min(N, S) - max(L, Q))
    }

    if ((xIntersection == 0) || (yIntersection == 0)) {
      areaIntersection = 0
    } else {
      areaIntersection = Int(xIntersection * yIntersection)
    }

    return (areaA + areaB - areaIntersection)
  }
}

// A simple test
Solution.computeArea(-4, 1, 2, 6, 0, -1, 4, 3) // returns 42

Upvotes: 1

Nikita Rybak
Nikita Rybak

Reputation: 68006

That's easy. First compute coordinates of intersection, which is also a rectangle.

left = max(r1.left, r2.left)
right = min(r1.right, r2.right)
bottom = max(r1.bottom, r2.bottom)
top = min(r1.top, r2.top)

Then, if intersection is not empty (left < right && bottom < top), subtract it from the common area of two rectangles: r1.area + r2.area - intersection.area.

PS:

  1. Assumption 1: rectangles are aligned by the coordinate axes, that's usually the case.
  2. Assumption 2: y axis here increases upwards, for example, in a graphics application, the y axis increases downwards, you may need to use:

bottom = min(r1.bottom, r2.bottom) top = max(r1.top, r2.top)

Upvotes: 85

Daniel Persson
Daniel Persson

Reputation: 602

I saw this question wasn't answered so I wrote a small java program to try the equation out that @VicJordan and @NikitaRybak has talked about in previous answers. Hope this helps.

/**
 * This function tries to see how much of the smallest rectangle intersects 
 * the with the larger one. In this case we call the rectangles a and b and we 
 * give them both two points x1,y1 and x2, y2.
 * 
 * First we check for the rightmost left coordinate. Then the leftmost right 
 * coordinate and so on. When we have iLeft,iRight,iTop,iBottom we try to get the 
 * intersection points lenght's right - left and bottom - top.
 * These lenght's we multiply to get the intersection area.
 *
 * Lastly we return the result of what we get when we add the two areas 
 * and remove the intersection area.
 * 
 * @param xa1       left x coordinate   A
 * @param ya1       top y coordinate    A
 * @param xa2       right x coordinate  A
 * @param ya2       bottom y coordinate A
 * @param xb1       left x coordinate   B
 * @param yb1       top y coordinate    B
 * @param xb2       right x coordinate  B
 * @param yb2       bottom y coordinate B
 * @return          Total area without the extra intersection area.
 */

public static float mostlyIntersects(float xa1, float ya1, float xa2, float ya2, float xb1, float yb1, float xb2, float yb2) {
    float iLeft = Math.max(xa1, xb1);
    float iRight = Math.min(xa2, xb2);
    float iTop = Math.max(ya1, yb1);
    float iBottom = Math.min(ya2, yb2);

    float si = Math.max(0, iRight - iLeft) * Math.max(0, iBottom - iTop);
    float sa = (xa2 - xa1) * (ya2 - ya1);
    float sb = (xb2 - xb1) * (yb2 - yb1);

    return sa + sb - si;
}

Upvotes: 5

Alok C
Alok C

Reputation: 2857

Sorry to come to the party late. I dont know if you are looking language specific : But on iOS its pretty easy :

CGRectIntersection

https://developer.apple.com/library/ios/documentation/GraphicsImaging/Reference/CGGeometry/#//apple_ref/c/func/CGRectIntersection

It would give you CGrect that is overlappring by given two rects. if they are not intersecting is would return CGRectIsNull.

hope this help at least someone. Happy coding

Upvotes: 0

Vikasdeep Singh
Vikasdeep Singh

Reputation: 21766

Here is complete solution for this algorithm using Java:

public static int solution(int K, int L, int M, int N, int P, int Q, int R,
        int S) {
    int left = Math.max(K, P);
    int right = Math.min(M, R);
    int bottom = Math.max(L, Q);
    int top = Math.min(N, S);

    if (left < right && bottom < top) {
        int interSection = (right - left) * (top - bottom);
        int unionArea = ((M - K) * (N - L)) + ((R - P) * (S - Q))
                - interSection;
        return unionArea;
    }
    return 0;
}

Upvotes: 14

doncon
doncon

Reputation: 31

The coordinates of intersection are correct if the origin (0,0) is placed at the bottom-left of the reference system.

In image processing, where the origin (0,0) is usually placed at the top-left of the reference system, the coordinates bottom and top of intersection would be:

bottom = min(r1.bottom, r2.bottom)
top = max(r1.top, r2.top)

Upvotes: 3

Related Questions