java - 检查相交矩形的更快方法？

Question

除了我的 Rect 类:

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

  ...
}

我有一个方法来检查两个 Rects 是否相交(没有双关语意):

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

测试用例:

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

类(class)运行良好。

我想知道是否有另一种——也许更快——的方法来检查矩形是否相交。我可以通过某种方式对其进行优化吗？

Answer 1

我倾向于将矩形存储为最小 x、最小 y、最大 x 和最大 y。然后发生重叠

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

如果它们重叠，交点定义为

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

如果它们具有相同的边界，则应根据您是否认为它们重叠而采取一些措施。我使用了严格的不等式，这意味着重叠边界不算作重叠。鉴于您使用的是整数(因此边界的宽度为 1)，我假设您确实希望将重叠边界视为重叠。我会做类似的事情:

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