Общая площадь пересекающихся прямоугольников

Ответ 1

Это легко. Сначала вычислите координаты пересечения, которое также является прямоугольником.

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

Тогда, если пересечение не пусто (left < right && bottom < top), вычтите его из общей области двух прямоугольников: r1.area + r2.area - intersection.area.

PS:

• Предположения 1: прямоугольники выравниваются по осям координат, что обычно имеет место.
• Успения 2: ось y возрастает вверх, например, в графическом приложении, ось y увеличивается вниз, вам может потребоваться использовать:

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

Ответ 2

Вот полное решение для этого алгоритма с использованием 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;
} 

Ответ 3

Я видел, что на этот вопрос не ответил, поэтому я написал небольшую программу java, чтобы попробовать уравнение, о котором говорили @VicJordan и @NikitaRybak в предыдущих ответах. Надеюсь, это поможет.

/**
 * 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 right - left and bottom - top.
 * These lenght 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;
}

Ответ 4

Координаты пересечения правильны, если начало координат (0,0) расположено в левом нижнем углу системы отсчета.

При обработке изображений, где начало координат (0,0) обычно помещается в верхнем левом углу системы отсчета, координаты внизу и вершины пересечения будут:

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

Ответ 5

Решение Swift-версии с анализом и результатами теста LeetCode.

/**
 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

Ответ 6

Извините, что приехал на вечеринку поздно. Я не знаю, изучаете ли вы язык: Но на iOS его довольно легко:

CGRectIntersection

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

Это даст вам CGrect, который перекрывается двумя заданными прямоугольниками. если они не пересекаются, возвращает CGRectIsNull.

надеюсь, что это поможет хотя бы кому-то. Счастливое кодирование