检测两个矩形交叉的算法？

我正在寻找一种算法来检测两个矩形是否相交(一个是任意角度,另一个只有垂直/水平线).

测试一个角落是否在另一个ALMOST中.如果矩形形成十字形状,则失败.

避免使用线条的斜率似乎是一个好主意,这需要垂直线条的特殊情况.

1> Nils Pipenbr..：

---

标准方法是进行分离轴测试(对其进行谷歌搜索).

简而言之:

如果可以找到分隔两个对象的直线,则两个对象不相交.例如,物体/物体的所有点都在线的不同侧.

有趣的是,只需检查两个矩形的所有边缘就足够了.如果矩形不重叠,则其中一个边缘将是分离轴.

在2D中,您可以在不使用斜坡的情况下执 边缘简单地定义为两个顶点之间的差异,例如

  edge = v(n) - v(n-1)

旋转90°可以使其垂直.在2D中,这很简单:

  rotated.x = -unrotated.y
  rotated.y =  unrotated.x

所以不涉及三角学或斜坡.也不需要将向量归一化为单位长度.

如果您想测试点是否在线的一侧或另一侧,您可以使用点积.标志会告诉你你在哪一边:

  // rotated: your rotated edge
  // v(n-1) any point from the edge.
  // testpoint: the point you want to find out which side it's on.

  side = sign (rotated.x * (testpoint.x - v(n-1).x) + 
               rotated.y * (testpoint.y - v(n-1).y);

现在测试矩形A的所有点对着矩形B的边缘,反之亦然.如果找到一个分离边缘,则对象不相交(假设B中的所有其他点位于要测试的边缘的另一侧 - 请参见下图).如果没有找到分离边,则矩形相交或另一个包含矩形.

该测试适用于任何凸多边形btw ..

修正:要识别分离边缘,仅测试一个矩形的所有点对另一个边缘的每个边缘是不够的.候选边E(下面)将被识别为分离边,因为A中的所有点都在E的同一半平面中.但是,它不是分离边,因为B的顶点Vb1和Vb2也在半平面上.如果不是这种情况,那只会是一个分离的边缘 http://www.iassess.com/collision.png

---

Skizz,检查所有八个边缘.如果对象不与八个边中的一个相交*将*将它们分开.你为什么不张贴一张显示你案件的图片？我可以告诉你轴...

---

此算法不适用于所有情况.可以将第二个矩形旋转45度到第一个矩形并沿对角线偏移,以便它完成上述相交测试但不相交.

---

我的错误,它确实应对了这种情况.

---

图像已经死了(2012年11月)

---

我在想象这个时遇到了很多麻烦,所以我重新创建了我认为被引用的图像看起来像的东西.http://imgur.com/bNwrzsv

2> m_pGladiator..：

---

基本上看下面的图片:

如果两个盒子碰撞,则线A和B将重叠.

请注意,这必须在X轴和Y轴上完成,并且两者都需要重叠以使矩形发生碰撞.

gamasutra.com上有一篇很好的文章回答了这个问题(图片来自文章).我5年前做过类似的算法,我必须找到我的代码片段,稍后再发布

修正:分离轴定理指出,如果存在分离轴(即,如图所示的投影不重叠的那个),则两个凸形状不重叠.所以"存在分离轴"=>"无重叠".这不是双重含义,因此您无法得出相反的结论.

---

x和y投影重叠是不够的:例如矩形[(0,0),(0,3),(3,3),(3,0)]和[(2,5), (5,2),(7,4),(4,7)].

---

@floater:我会说这不仅*错误,而且*也*误导,这更糟糕.

---

这个答案没有错,但这是误导.确实如此:如果两个盒子碰撞,线A和B将重叠.但同样正确的是:如果线A和B重叠,则两个方框可能会或可能不会发生碰撞

---

我同意Gö的@Joel.这种方法错过了一大堆矩形不重叠的情况,但它们的投影半径在x和y都有.