Szybszy sposób na sprawdzenie przecinających się prostokątów?

Question

wyjątkiem od mojego Rect klasy:

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

    ... 
} 

Mam metodę, aby sprawdzić, czy dwóch rects przecina (gra słów nie przeznaczonych): przypadek

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

testu:

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 

klasa działa dobrze.

Zastanawiam się, czy istnieje inny - być może szybszy - sposób sprawdzenia, czy prostokąty przecinają się. Czy mogę ją w jakiś sposób zoptymalizować?

Answer 1

Mam tendencję do przechowywania prostokątów jako min x, min y, max x i max y. Następnie nakładanie występuje, gdy

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

A jeśli one pokrywają się, przecięcie jest zdefiniowany przez

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

Niektóre Należy zachować ostrożność w zależności od tego, czy uważają je za kumulację, jeśli mają taką samą granicę . Użyłem ścisłych nierówności, co oznacza, że ​​nakładające się granice nie są traktowane jako nakładanie się. Biorąc pod uwagę, że używasz liczb całkowitych (a zatem granice mają szerokość 1), zakładam, że chcesz uwzględnić zachodzące na siebie granice jako nakładanie się. Zrobiłbym coś takiego:

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