兩個矩形之間的差異（XOR），如矩形？

我正在尋找一種簡單的方法來計算兩個矩形之間的差異。我的意思是屬於其中一個矩形的所有點，但不是兩個（所以它就像XOR）。兩個矩形之間的差異（XOR），如矩形？

在這種情況下，矩形是軸對齊的，所以只會有直角。我相信差異區域可以表示爲0-4個矩形（如果兩個矩形相同，則爲0，如果只是一個邊緣不同，則爲1，一般情況下爲4），我想將差異區域作爲列表的矩形。

你也可以把它想象成當一個實心矩形被移動/調整大小時必須更新的屏幕區域。

示例：加倍矩形「a」的寬度 - 我想添加區域（R）。

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

相交矩形（a和b） - 我要通過在矩形T，L，R和B（其他的分區可能的）給定的區域，但不包括X：

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

我想更喜歡Python解決方案/庫，但任何強大的算法會有所幫助。

來源

2011-02-28 jdm

分割問題下來到每個軸的基礎。您的矩形可以根據每個軸上的跨度來定義 - 在矩形開始或結束的每個軸上查找有趣的點，然後用這些術語定義結果。這將爲您提供6個不同區域的矩形，您可以輕鬆地將它們組合到您已經說明的四個矩形區域，或者如果需要，可以消除退化的零區域矩形。

這裏是一個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; 
    } 
}

來源

2011-03-01 14:29:31 ryanm