Cách nhanh hơn để kiểm tra hình chữ nhật giao nhau?

Question

Trừ từ Rect-lớp học của tôi:

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

    ... 
} 

Tôi có một phương pháp để kiểm tra xem hai giao cắt dễ phân biệt (không có ý định chơi chữ):

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)))); 
} 

Kiểm tra trường hợp:

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 

Các lớp học hoạt động tốt.

Điều tôi đang tự hỏi là liệu có cách nào khác - có lẽ nhanh hơn - cách kiểm tra xem các hình chữ nhật có giao nhau hay không. Tôi có thể tối ưu hóa nó theo một cách nào đó không?

Answer 1

Tôi có xu hướng lưu trữ hình chữ nhật là min x, min y, max x và max y. Sau đó, chồng chéo xảy ra khi

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

Và nếu họ chồng chéo lên nhau, ngã tư được xác định bởi

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); 

Một số dịch vụ chăm sóc cần được thực hiện tuỳ thuộc vào việc hay không bạn xem xét chúng được chồng chéo nếu họ có ranh giới tương tự . Tôi đã sử dụng sự bất bình đẳng nghiêm ngặt có nghĩa là ranh giới chồng chéo không được tính là chồng chéo. Cho rằng bạn đang sử dụng số nguyên (và do đó các ranh giới có chiều rộng là 1), tôi sẽ giả định rằng bạn muốn xem xét các ranh giới trùng lặp như một chồng chéo. Tôi sẽ làm điều gì đó như:

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