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

Question

我正在寻找一种算法，用于检测两个矩形是否相交（一个在任意角度，另一个只有垂直/水平线）。

测试一个矩形的角落是否在另一个矩形内几乎可行。如果矩形呈十字型，则该方法会失败。

避免使用线段斜率似乎是个好主意，因为这需要针对垂直线进行特殊处理。

- user20493

---

你打算用什么语言来实现这个？因为在Java中有内置的类可以让你做到这一点。 - Martijn

我认为图形API和大多数GUI库（如Swing）都已经实现了这个功能。 - l_39217_l

可能会出现重叠但没有任何矩形的角落在其中的情况。 - Florian Bösch

我已经为此创建了一个C#实现; 请参见这里。 - Sebastian Krysmanski

这个问题与https://dev59.com/C3VC5IYBdhLWcg3wZwTj几乎相同。尽管如此，这是在寻找特别适用于C++的解决方案。被接受的答案也非常简单和直接。 - Silver Gonzales

Answer 1

通常的方法是进行分离轴测试（在谷歌上搜索此内容）。

简而言之：

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

有趣的是，只需检查两个矩形的所有边缘即可。如果矩形不重叠，则其中一个边缘将成为分离轴。

在二维情况下，可以在不使用斜率的情况下完成这项工作。边缘仅定义为两个顶点之间的差异，例如：

  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中的所有其他点都在正在测试的边缘的另一侧-请参阅下面的图示）。如果您找不到分离的边缘，则矩形相交或一个矩形包含另一个矩形。

顺带一提，该测试适用于任何凸多边形。

更正：为了确定一个分离的边缘，仅测试一个矩形的所有点是否与另一个矩形的每条边相交是不够的。候选边缘E（如下图所示）将被识别为分离的边缘，因为所有A中的点都在E的同一半平面中。但是，它不是一个分离的边缘，因为B的顶点Vb1和Vb2也在该半平面中。只有在那种情况下，它才是一个分离的边缘。 http://www.iassess.com/collision.png

- Nils

---

这个算法并不适用于所有情况。有可能将第二个矩形旋转45度放置在第一个矩形旁边，沿对角线偏移，以满足上述交集测试但不相交。 - Skizz

Skizz，请检查所有八个边缘。如果物体没有相交其中的一个边缘，它们将会被分开。为什么不发布一张显示您情况的图片？我可以给你展示坐标轴。 - Nils Pipenbrinck

我的错误，它确实处理了那个条件。 - Skizz

该图片现已失效（2012年11月）。 - John Dvorak

我对这个内容的可视化感到困难，因此我重新创建了我认为所引用图像的样子。http://imgur.com/bNwrzsv - Rjdlee

Answer 2

基本上看一下以下图片：

如果这两个矩形重叠，线段A和B将会重叠。

需要注意的是，在X轴和Y轴上都需要进行重叠判断，只有当两个矩形在X轴和Y轴上都有重叠时才算碰撞。

gamasutra.com 上有一篇很好的文章回答了这个问题（该图片来自该文章）。 5年前我做过类似的算法，我必须找到我的代码片段以后在这里发布。

修正：分离轴定理表明，如果存在一条分离轴（即它们的投影不重叠），则两个凸形状不会重叠。 因此，“存在分离轴”=>“没有重叠”。 这不是一个双向蕴含，因此您不能得出逆命题。

- m_pGladiator

---

显然，两个正方形（0,0,1,1）和（0,3,1,4）不重叠，但它们在x轴上的投影完全重叠。这两个测试都是必要的，结合起来就足够了。 - MSalters

x和y的投影重叠并不足够：以矩形[(0,0)，(0,3)，(3,3)，(3,0)]和[(2,5)，(5,2)，(7,4)，(4,7)]为例。 - Joel in Gö

我同意 Gö 中的 @Joel。这种方法忽略了许多矩形不重叠的情况，但是它们在 x 和 y 的投影半径中却重叠。 - Scottie T

这个答案并没有错，但是有误导性。 确实： 如果两个盒子碰撞，线条A和B将重叠。但也同样正确的是： 如果线条A和B重叠，这两个盒子可能会碰撞也可能不会。 - matt burns

我认为这不仅是错误的，而且具有误导性，后者甚至更糟。 - BlueRaja - Danny Pflughoeft

Answer 3

在Cocoa中，您可以轻松检测所选区域的矩形是否与旋转后的NSView框架矩形相交。您甚至不需要计算多边形、法线等等。只需将这些方法添加到您的NSView子类中即可。例如，用户在NSView的superview上选择一个区域，然后调用DoesThisRectSelectMe方法并传递所选区域矩形。API convertRect: 将完成此工作。当您单击NSView以选择它时，同样的技巧也适用。在这种情况下，只需按如下所示覆盖hitTest方法。API convertPoint: 将完成此工作;-)

- (BOOL)DoesThisRectSelectMe:(NSRect)selectedArea
{
    NSRect localArea = [self convertRect:selectedArea fromView:self.superview];

    return NSIntersectsRect(localArea, self.bounds);
}


- (NSView *)hitTest:(NSPoint)aPoint
{
    NSPoint localPoint = [self convertPoint:aPoint fromView:self.superview];
    return NSPointInRect(localPoint, self.bounds) ? self : nil;
}

- Leonardo

---

那段代码只适用于与屏幕正方形相同的矩形。这是一个微不足道的情况。假设我们正在处理的矩形不是与屏幕或彼此成90度角的矩形。 - Duncan C

根据我的检查和应用经验，该代码适用于任何旋转矩形，无论旋转角度如何。 - Leonardo

这并没有描述算法，它只是提到了一个已经使用它的库。 - Ben Voigt

Answer 4

有关分离轴测试的被接受的答案很有启发性，但我仍然觉得它不容易应用。我将分享我想到的伪代码，首先使用包围圆测试（请参见此其他答案）进行“优化”，以防可能有助于其他人。 我考虑了大小相同的两个矩形A和B（但是考虑一般情况很简单）。

1 包围圆测试：

    function isRectangleACollidingWithRectangleB:
      if d > 2 * R:
         return False
      ...

计算速度比分离轴测试快得多。只有在两个圆相交的情况下才需要考虑分离轴测试。

2.分离轴测试

主要思路如下：

- 考虑一个矩形，循环遍历其顶点V(i)。 - 计算向量Si+1: V(i+1) - V(i)。 - 使用Si+1计算向量Ni: Ni = (-Si+1.y, Si+1.x)。该向量为图像中的蓝色。从V(i)到其他顶点的向量与Ni的点积的符号将定义分离轴（品红虚线）。 - 计算向量Si-1: V(i-1) - V(i)。Si-1与Ni的点积的符号将定义第一个矩形相对于分离轴的位置。在图像示例中，它们朝不同方向走，因此符号为负。 - 针对第二个矩形的所有顶点j进行循环，并计算向量Sij = V(j) - V(i)。 - 如果对于任何顶点V(j)，向量Sij与Ni的点积的符号与向量Si-1与Ni的点积的符号相同，这意味着顶点V(i)和V(j)都在品红虚线的同侧，因此顶点V(i)没有分离轴。因此，我们可以跳过顶点V(i)，并重复下一个顶点V(i+1)的操作。但是首先我们需要更新Si-1 = - Si+1。当我们到达最后一个顶点（i = 4）时，如果没有找到分离轴，则重复另一个矩形的操作。如果仍然找不到分离轴，则说明两个矩形相交。 - 如果对于给定的顶点V(i)和所有顶点V(j)，向量Sij与Ni的点积的符号与向量Si-1与Ni的点积的符号不同（如图中所示），则意味着已经找到了分离轴，矩形不会相交。

伪代码如下：

    function isRectangleACollidingWithRectangleB:
      ...
      #Consider first rectangle A:
      Si-1 = Vertex_A[4] - Vertex_A[1]
      for i in Vertex_A:
         Si+1 = Vertex_A[i+1] - Vertex_A[i]
         Ni = [- Si+1.y, Si+1.x ]
         sgn_i = sign( dot_product(Si-1, Ni) ) #sgn_i is the sign of rectangle A with respect the separating axis

         for j in Vertex_B:
            sij = Vertex_B[j] - Vertex_A[i]
            sgn_j = sign( dot_product(sij, Ni) ) #sgnj is the sign of vertex j of square B with respect the separating axis
            if sgn_i * sgn_j > 0: #i.e., we have the same sign
                break #Vertex i does not define separating axis
            else:
                if j == 4: #we have reached the last vertex so vertex i defines the separating axis
                   return False
        
        Si-1 = - Si+1

      #Repeat for rectangle B
      ...

      #If we do not find any separating axis
      return True 

你可以在Python中找到代码在这里。

注意：这个答案中还建议在使用分离轴测试之前尝试优化，检查一个矩形的顶点是否在另一个矩形内作为碰撞的充分条件。然而，在我的实验中，我发现这个中间步骤实际上效率更低。

- Puco4

Answer 5

m_pGladiator的答案是正确的，我更喜欢它。"分离轴测试"是检测矩形重叠的最简单和标准方法。对于投影间隔不重叠的线，我们称之为"分离轴"。Nils Pipenbrinck的解决方案太笼统了。它使用"点积"来检查一个形状是否完全在另一个形状的边缘的一侧。实际上，这个解决方案可能会导致n边凸多边形。然而，它并没有针对两个矩形进行优化。

m_pGladiator答案的关键点是我们应该检查两个矩形在两个轴（x和y）上的投影。如果两个投影重叠，那么我们可以说这两个矩形重叠。因此，上面对m_pGladiator答案的评论是错误的。

对于简单的情况，如果两个矩形没有旋转，我们可以用结构体表示一个矩形：

struct Rect {
    x, // the center in x axis
    y, // the center in y axis
    width,
    height
}

我们把矩形A、B分别称为rectA和rectB。

    if Math.abs(rectA.x - rectB.x) < (Math.abs(rectA.width + rectB.width) / 2) 
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(rectA.height + rectB.height) / 2))
    then
        // A and B collide
    end if

如果两个矩形中的任意一个旋转了，就需要一些努力来确定它们在x和y轴上的投影。定义如下的结构体RotatedRect：

struct RotatedRect : Rect {
    double angle; // the rotating angle oriented to its center
}

区别在于宽度'现在有些不同： rectA的宽度A'：Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle) rectB的宽度B'：Math.sqrt(rectB.width*rectB.width + rectB.height*rectB.height) * Math.cos(rectB.angle)

    if Math.abs(rectA.x - rectB.x) < (Math.abs(widthA' + widthB') / 2) 
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(heightA' + heightB') / 2))
    then
        // A and B collide
    end if

这可能是与游戏开发相关的GDC（Game Development Conference 2007）PPT。您可以通过www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt链接获取。

- tristan

---

为什么在“Math.abs(rectA.width + rectB.width)”中需要使用Math.abs()来处理负宽度？ - AlexWien

分离轴不一定是罗盘方向，它可以有任何角度。 - Ben Voigt

非旋转矩形rectA（x = 0，y = 0，width = 1，height = 1）和rectB（x = 2，y = 0，width = 100，height = 1）不相交，但您的方法却显示它们相交。我做错了什么吗？ - Kagami Sascha Rosylight

这个答案也是错误的。如果 x 轴和 y 轴上的两个投影重叠，这并不意味着矩形重叠。例如，请参见：https://imgur.com/a/HyorpQc - Puco4

Answer 6

检查一个矩形的任意一条线段是否与另一个矩形的任意一条线段相交。朴素的线段相交算法易于编写。

如果需要更快的速度，可以使用高级算法进行线段相交（扫描线）。请参阅http://en.wikipedia.org/wiki/Line_segment_intersection

- lbrandy

---

小心！不要忘记一个矩形完全包含另一个矩形的情况。 - Pitarou

Answer 7

一种解决方案是使用称为“不适合多边形”的东西。该多边形是从两个多边形计算出来的（概念上通过将一个多边形滑动到另一个多边形上），它定义了两个多边形相对偏移时重叠部分的区域。一旦您获得了此NFP，那么您只需使用由两个多边形的相对偏移给出的点进行包含测试即可。这种包含测试快速且简单，但您必须先创建NFP。

在网络上搜索“不适合多边形”，看看是否可以找到凸多边形的算法（如果有凹多边形，则会变得更加复杂）。如果找不到任何内容，请发送电子邮件至 howard dot J dot may gmail dot com。

- Howard May

Answer 8

我认为以下方法可以处理所有可能的情况。执行以下测试。

1. 检查矩形1的任何顶点是否位于矩形2内部，反之亦然。每当您发现一个顶点位于另一个矩形内部时，可以得出它们相交并停止搜索。这将处理一个矩形完全位于另一个矩形内部的情况。
2. 如果上述测试无法确定，请找到矩形1的每条线与另一个矩形的每条线的相交点。一旦找到交点，请检查它是否位于由相应的4个点创建的虚拟矩形内部。每当找到这样的点时，得出它们相交并停止搜索。

如果以上两个测试都返回false，则这两个矩形不重叠。

- John Smith

Answer 9

我有自己更简单的方法，如果我们有两个矩形：

R1 =（min_x1，max_x1，min_y1，max_y1）

R2 =（min_x2，max_x2，min_y2，max_y2）

它们重叠当且仅当：

Overlap =（max_x1 > min_x2）and（max_x2 > min_x1）and（max_y1 > min_y2）and（max_y2 > min_y1）

你也可以用这种方法来判断3D盒子，实际上它适用于任意维度。

- BitFarmer

Answer 10

另一种比使用分离轴测试稍微快一些的测试方法是在每个矩形（任意选择）的每个顶点上使用绕数算法（仅限象限 - 不是角度总和，后者速度极慢）。如果任何一个顶点具有非零绕数，则两个矩形重叠。

这种算法比分离轴测试略显冗长，但更快，因为它只需要半平面测试，如果边缘穿过两个象限（而不是使用分离轴方法最多需要32次测试）。

该算法进一步的优势是可以用于测试任何多边形（凸多边形或凹多边形）的重叠。据我所知，该算法仅适用于2D空间。

- Mads

---

我可能错了，但那个只是检查一个矩形的顶点是否在另一个矩形内部吗？如果是这样，那就不够了，因为矩形可以重叠而没有任何顶点在内部。 - sinelaw

他们能用矩形吗？怎么做呢？在我看来，为了让两个矩形相交，至少一个矩形的顶点必须位于另一个矩形上。 - Duncan C

@DuncanC：是的，它们可以。反例是一个十字形，甚至在原问题中也列出了它。 - Ben Voigt

@BenVoigt 这是一个非常古老的帖子，但你绝对是正确的。 - Duncan C