area totale di rettangoli intersecanti

Question

Ho bisogno di un algoritmo per risolvere questo problema: Dato 2 rettangoli che si intersecano o si sovrappongono in qualsiasi angolo, come faccio a determinare l'area totale per i due rettangoli senza l'area (intersezione) sovrapposta? Significa che l'area di intersezione deve essere calcolata una volta, sia con il primo rettangolo, sia con la seconda.

Answer 1

È facile. Prima calcolare le coordinate dell'intersezione, che è anche un rettangolo.

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

Quindi, se intersezione non è vuota (left < right && bottom < top), sottrarre dall'area comune dei due rettangoli: r1.area + r2.area - intersection.area.

PS:

1. Assunzione 1: rettangoli sono allineati dagli assi delle coordinate, che è normalmente il caso.
2. Ipotesi 2: all'asse y qui aumenta verso l'alto, ad esempio, in un'applicazione grafica, l'asse y aumenta verso il basso, può essere necessario utilizzare:

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

Answer 2

Le coordinate di intersezione sono correggi se l'origine (0,0) è posizionata in basso a sinistra del sistema di riferimento.

In elaborazione delle immagini, in cui l'origine (0,0) è di solito posto in alto a sinistra del sistema di riferimento, la parte inferiore e superiore coordinate di intersezione sarebbe:

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

Answer 3

Ecco soluzione completa per questo algoritmo utilizzando 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

Mi dispiace venire alla festa in ritardo. Non so se siete alla ricerca lingua specifica: Ma su iOS sua piuttosto facile:

CGRectIntersection

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

darebbe CGRect che è overlappring dai dati due rettangoli. se non si intersecano sarebbe restituire CGRectIsNull.

spero che questo aiuti almeno qualcuno. Codifica felice

Answer 5

Ho visto che questa domanda non ha avuto risposta, quindi ho scritto un piccolo programma Java per provare l'equazione che @VicJordan e @NikitaRybak hanno parlato nelle risposte precedenti. Spero che questo ti aiuti.

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

Una soluzione in versione Swift con analisi e risultati del test 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