CODEWITHSUNDEEP
java
bos
bos

Reputation: 6555

Faster way to check intersected rectangles?

Except from 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 method to check if two Rects intersects (no pun intended):

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

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 fine.

What I'm wondering is if there is another - perhaps faster - way to check if the rectangles are intersecting. Can I optimize it in some way?

Upvotes: 7

Views: 6351

Answers (1)

Matt Esch
Matt Esch

Reputation: 22966

I tend to store 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 defined by

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 care should be taken depending on whether or not you consider them to be overlapping if they have the same boundary. I've used strict inequalities meaning that overlapping boundaries do not count as an overlap. Given that you are using integers (and thus the boundaries have a width of 1) I will assume that you do want to consider overlapping boundaries as an overlap. 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;
    }
}

Upvotes: 8

Related Questions