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

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (85)

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

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

这似乎是一个好主意,以避免使用斜线的线,这将需要特殊情况下的垂直线。

提问于
用户回答回答于

标准的方法是做分离轴测试

简而言之:

  • 如果可以找到分隔两个对象的线,则两个对象不会相交。例如物体/物体的所有点位于线的不同侧。

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

在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中所有其他点位于被测边缘的另一边 - 请参阅下图)。如果找不到分离边,则矩形相交或一个矩形包含在另一个矩形中。

用户回答回答于

基本上看下面的图片:

http://www.gamasutra.com/features/20000330/bobic_08.gif

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

请注意,这将必须在X和Y轴上完成,并且两个矩形都需要重叠才能碰撞。

gamasutra.com有一篇很好的文章回答了这个问题(图片来自文章)。

扫码关注云+社区