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

Question

Мне нужен алгоритм для решения этой проблемы: Учитывая, что два прямоугольника пересекаются или пересекаются вместе в любом углу, как определить общую площадь для двух прямоугольников без перекрывающейся области (пересечения)? Значение площади пересечения должно быть рассчитано один раз, либо с первым прямоугольником, либо со вторым.

Answer 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. Предположение 1: прямоугольниками выровнены по осям координат, то это обычно бывает.
2. Предположение 2: ось у здесь растет вверх, например, в графическом приложении, ось у увеличивается вниз, возможно, потребуется использовать:

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

CGRectIntersection

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

Это даст вам CGRect, что overlappring по данным два прямоугольников. , если они не пересекаются, вернется CGRectIsNull.

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

Answer 5

Я видел, что на этот вопрос не ответил, поэтому я написал небольшую программу 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'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; 
} 

Answer 6

Решение для быстрой версии с анализом и результатами теста 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