muse - algorithms book

área total de rectángulos que se cruzan

Question

Necesito un algoritmo para resolver este problema: dados 2 rectángulos que se intersecan o se superponen en cualquier esquina, ¿cómo puedo determinar el área total para los dos rectángulos sin el área superpuesta (intersección)? El significado del área de intersección debe calcularse una vez, ya sea con el primer rectángulo o con el segundo.

Answer 1

Aquí está la solución completa para este algoritmo usando 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 2

Eso es fácil. Primero calcula las coordenadas de la intersección, que también es un rectángulo.

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

Luego, si la intersección no está vacía ( left < right && bottom < top ), r1.area + r2.area - intersection.area del área común de dos rectángulos: r1.area + r2.area - intersection.area .

PD:

1. Supuesto 1: los rectángulos están alineados por los ejes de coordenadas, que suele ser el caso.
2. Supuesto 2: el eje y aquí aumenta hacia arriba, por ejemplo, en una aplicación de gráficos, el eje y aumenta hacia abajo, es posible que deba usar:

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

Answer 3

Las coordenadas de la intersección son correctas si el origen (0,0) se coloca en la parte inferior izquierda del sistema de referencia.

En el procesamiento de imágenes, donde el origen (0,0) se coloca generalmente en la parte superior izquierda del sistema de referencia, las coordenadas inferior y superior de la intersección serían:

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

Answer 4

Perdón por llegar tarde a la fiesta. No sé si estás buscando un lenguaje específico: pero en iOS es bastante fácil:

Intersección de vectores

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

Le daría CGrect que se superpone con dos rects dados. Si no se intersecan se devolvería CGRectIsNull .

Espero que esto ayude al menos a alguien. Feliz codificacion

Answer 5

Una solución de la versión Swift con análisis y resultados de prueba 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

Answer 6

Vi que esta pregunta no fue respondida, así que escribí un pequeño programa en java para probar la ecuación que @VicJordan y @NikitaRybak han mencionado en las respuestas anteriores. Espero que esto ayude.

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