¿Diferencia (XOR) entre dos rectángulos, como rectángulos?

Estoy buscando una manera simple de calcular la diferencia entre dos rectángulos. Me refiero a todos los puntos que pertenecen a uno de los rectángulos, pero no a ambos (por lo que es como XOR).¿Diferencia (XOR) entre dos rectángulos, como rectángulos?

Los rectángulos están alineados con el eje en este caso, por lo que solo habrá ángulos rectos. Creo que la región de diferencia se puede expresar en 0-4 rectángulos (0 si ambos rectángulos son iguales, 1 si solo un borde es diferente, 4 en el caso general), y me gustaría obtener la región de diferencia como una lista de rectángulos.

También puede considerarlo como las áreas de la pantalla que deben actualizarse cuando se mueve/cambia el tamaño de un rectángulo sólido.

Ejemplos: Doblando el ancho del rectángulo "a" - Quiero la región agregada (R).

+----+----+ 
| a | R | 
| | | 
+----+----+

rectángulos de intersección (A y b) - Quiero que el área dada por T, L, R y B en rectángulos (otra partición posible), pero excluyendo X:

+------------+ a 
|  T  | 
|·····+------+-----+ b 
| L | X | R | 
|  |  |  | 
+-----+------+·····| 
     | B  | 
     +------------+

que había prefiera una solución/biblioteca de Python, pero cualquier algoritmo robusto sería útil.

Fuente

2011-02-28 jdm

Dividir el problema hacia abajo en función de cada eje. Sus rectángulos se pueden definir en términos de sus tramos en cada eje: encuentre los puntos interesantes en cada eje donde comienza o termina un rectángulo y luego defina los resultados en esos términos. Esto le dará 6 rectángulos de áreas de diferencia, puede combinarlos fácilmente hasta los cuatro que ha ilustrado o eliminar rectángulos de área cero degenerados si es necesario.

Aquí es una implementación de Java:

public class Rect 
{ 
    private float minX, maxX, minY, maxY; 

    public Rect(float minX, float maxX, float minY, float maxY) 
    { 
     this.minX = minX; 
     this.maxX = maxX; 
     this.minY = minY; 
     this.maxY = maxY; 
    } 

    /** 
    * Finds the difference between two intersecting rectangles 
    * 
    * @param r 
    * @param s 
    * @return An array of rectangle areas that are covered by either r or s, but 
    *   not both 
    */ 
    public static Rect[] diff(Rect r, Rect s) 
    { 
     float a = Math.min(r.minX, s.minX); 
     float b = Math.max(r.minX, s.minX); 
     float c = Math.min(r.maxX, s.maxX); 
     float d = Math.max(r.maxX, s.maxX); 

     float e = Math.min(r.minY, s.minY); 
     float f = Math.max(r.minY, s.minY); 
     float g = Math.min(r.maxY, s.maxY); 
     float h = Math.max(r.maxY, s.maxY); 

     // X = intersection, 0-7 = possible difference areas 
     // h +-+-+-+ 
     // . |5|6|7| 
     // g +-+-+-+ 
     // . |3|X|4| 
     // f +-+-+-+ 
     // . |0|1|2| 
     // e +-+-+-+ 
     // . a b c d 

     Rect[] result = new Rect[ 6 ]; 

     // we'll always have rectangles 1, 3, 4 and 6 
     result[ 0 ] = new Rect(b, c, e, f); 
     result[ 1 ] = new Rect(a, b, f, g); 
     result[ 2 ] = new Rect(c, d, f, g); 
     result[ 3 ] = new Rect(b, c, g, h); 

     // decide which corners 
     if(r.minX == a && r.minY == e || s.minX == a && s.minY == e) 
     { // corners 0 and 7 
      result[ 4 ] = new Rect(a, b, e, f); 
      result[ 5 ] = new Rect(c, d, g, h); 
     } 
     else 
     { // corners 2 and 5 
      result[ 4 ] = new Rect(c, d, e, f); 
      result[ 5 ] = new Rect(a, b, g, h); 
     } 

     return result; 
    } 
}

Fuente

2011-03-01 14:29:31 ryanm