更快速地检查相交的矩形？

除了我的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; } ... } 

我有一个方法来检查两个Rects是否相交（没有双关语）：

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

测试用例：

 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

我倾向于将矩形存储为min x，min y，max x和max 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; } }