檢查相交矩形的更快方法？

Question

除非從我的矩形類：

public class Rect { 
    public int x; 
    public int y; 
    public int w; 
    public int h; 

    public Rect(int x, int y, int w, int h) { 
    this.x = x; 
    this.y = y; 
    this.w = w; 
    this.h = h; 
    } 

    ... 
} 

我有一個方法檢查兩個Rects相交（沒有雙關語意）：

public boolean intersect(Rect r) { 
    return (((r.x >= this.x) && (r.x < (this.x + this.w))) || ((this.x >= r.x) && (this.x < (r.x + r.w)))) && 
    (((r.y >= this.y) && (r.y < (this.y + this.h))) || ((this.y >= r.y) && (this.y < (r.y + r.h)))); 
} 

測試用例：

r1 = (x, y, w, h) = (0, 0, 15, 20) center: (x, y) = (7, 10) 
r2 = (x, y, w, h) = (10, 11, 42, 15) center: (x, y) = (31, 18) 
r1 Intersect r2: true 

的課程正常工作。

我想知道的是，如果有另一個 - 也許更快 - 檢查矩形是否相交。我能以某種方式優化它嗎？

Answer 1

我傾向於將矩形存儲爲min x，min y，max x和max y。然後會發生重疊時

r1.maxX > r2.minX && 
r1.minX < r2.maxX && 
r1.maxY > r2.minY && 
r1.minY < r2.maxY 

如果它們重疊，交叉是由

r3.minX = max(r1.minX, r2.minX); 
r3.minY = max(r1.minY, r2.minY); 
r3.maxX = min(r1.maxX, r2.maxX); 
r3.maxY = min(r1.maxY, r2.maxY); 

一些護理應該取決於你是否認爲如果他們有相同的邊界他們被重疊採取定義。我使用了嚴格的不等式，這意味着重疊的邊界不會被視爲重疊。考慮到你正在使用整數（因此邊界的寬度爲1），我會假設你確實想把重疊邊界看作是重疊。我會這樣做：

public class Rect { 
    public int minX; 
    public int minY; 
    public int maxX; 
    public int maxY; 

    public Rect() {} 

    public Rect(int x, int y, int w, int h) { 
     this.minX = x; 
     this.minY = y; 
     this.maxX = x + w -1; 
     this.maxY = y + h -1; 
    } 

    public boolean Intersect(Rect r) { 
     return this.maxX >= r.minX && 
       this.minX <= r.maxX && 
       this.maxY >= r.minY && 
       this.minY <= r.maxY;    
    } 

    public Rect GetIntersection(Rect r) { 
     Rect i = new Rect(); 
     if (this.Intersect(r)) { 
      i.minX = Math.max(this.minX, r.minX); 
      i.minY = Math.max(this.minY, r.minY); 
      i.maxX = Math.min(this.maxX, r.maxX); 
      i.maxY = Math.min(this.maxY, r.maxY); 
     } 
     return i;  
    } 

    public int GetWidth() { 
     return this.maxX - this.minX + 1; 
    } 

    public int GetHeight() { 
     return this.maxY - this.minY + 1; 
    } 

    public void SetPosition(int x, int y) { 
     int w = this.GetWidth(); 
     int h= this.GetHeight(); 
     this.minX = x; 
     this.minY = y; 
     this.maxX = x + w -1; 
     this.maxY = y + h -1; 
    } 
}