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

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

  ...
}

我有一种方法可以检查两个矩形是否相交（无意冒犯）：

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

这个类运行良好。

我想知道是否有另一种 - 或许更快的 - 方法来检查矩形是否相交。我能否以某种方式进行优化？

- bos

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

- Matt Esch