¿Forma más rápida de revisar rectángulos intersecados?

Question

A excepción de mi Rect de clase:

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

    ... 
} 

que tienen un método para comprobar si dos intersecciones rectas (sin doble sentido): caso

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

prueba:

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 

El la clase funciona bien

Lo que me pregunto es si hay otra forma, quizás más rápida, de comprobar si los rectángulos se cruzan. ¿Puedo optimizarlo de alguna manera?

Answer 1

Tiendo a almacenar rectángulos como min x, min y, max x y max y. Entonces permanente se produce cuando

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

Y si se superponen, la intersección se define por

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

Algunos se debe tener cuidado en función de si o no se tiene en cuenta que sean solapados si tienen el mismo límite . Utilicé estrictas desigualdades, lo que significa que los límites superpuestos no cuentan como una superposición. Dado que está utilizando números enteros (y, por lo tanto, los límites tienen un ancho de 1), supondré que desea considerar la superposición de límites como una superposición. Haría algo como:

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