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

Question

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

测试一个角落是否在另一个角落几乎有效。如果矩形形成十字形，则失败。

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

Answer 1

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

简而言之:

• 如果您能找到一条分隔两个对象的线，则两个对象不会相交。例如对象/对象的所有点都在线的不同侧。

有趣的是，只需检查两个矩形的所有边就足够了。如果矩形不重叠，其中一条边将作为分离轴。

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

现在根据矩形 B 的边测试矩形 A 的所有点，反之亦然。如果您找到一条分离边，则对象不相交(前提是 B 中的所有其他点都位于要测试的边的另一侧 - 参见下图)。如果您发现没有分隔边，则要么是矩形相交，要么是一个矩形包含在另一个矩形中。

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

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