A faster way to check for intersecting rectangles?

Question

Except for my Rect class:

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

I have a way to check if two Rects (no pun intended) intersect:

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

Test case:

 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 

The class works great.

I am wondering if there is another - perhaps a faster way to check if the rectangles intersect. Can I somehow optimize it?

Answer 1

I try to store the rectangles as min x, min y, max x and max y. Then overlap occurs when

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

And if they overlap, the intersection is determined

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

Some caution should be taken depending on whether you consider them overlapping if they have the same boundary. I used strict inequalities, which means that overlapping borders are not considered overlapping. Given that you use integers (and therefore borders have a width of 1), I assume that you want to consider overlapping borders as overlapping. I would do something like:

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