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

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

现在测试矩形 A 的所有点对矩形 B 的边缘，反之亦然。如果您发现一个分离边缘，则对象不相交（假设 B 中的所有其他点都在被测试边缘的另一侧 - 参见下图）。如果没有发现分隔边，则矩形相交或一个矩形包含在另一个矩形中。

顺便说一句，该测试适用于任何凸多边形。

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

Answer 2

基本上看下图：

如果两个框碰撞，线 A 和 B 将重叠。

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

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

修正：分离轴定理指出，如果存在分离轴（即所示投影不重叠的位置），则两个凸形不重叠。所以“存在分离轴”=>“没有重叠”。这不是双重含义，因此您无法得出相反的结论。

Answer 3

在 Cocoa 中，您可以轻松检测 selectedArea 矩形是否与旋转的 NSView 的框架矩形相交。您甚至不需要计算多边形、法线等。只需将这些方法添加到您的 NSView 子类中。例如，用户在 NSView 的 superview 上选择一个区域，然后调用方法 DoesThisRectSelectMe 传递 selectedArea rect。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;
}

Answer 4

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 轴上的投影。定义 struct RotatedRect 如下：

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

不同之处在于 width' 现在有点不同： rectA 的 widthA' ： rectB 的 widthB Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle) ' ：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

Answer 5

检查一个矩形的任何线条是否与另一个矩形的任何线条相交。朴素的线段交点很容易编码。

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

Answer 6

一种解决方案是使用一种称为 No Fit Polygon 的东西。这个多边形是根据两个多边形计算出来的（概念上是通过一个围绕另一个滑动），它定义了多边形在给定相对偏移的情况下重叠的区域。一旦你有了这个 NFP，那么你只需要用两个多边形的相对偏移量给出的点进行包含测试。此包含测试既快速又简单，但您必须先创建 NFP。

在网络上搜索 No Fit Polygon，看看是否可以找到凸多边形的算法（如果您有凹多边形，它会变得更加复杂）。如果您找不到任何东西，请发送电子邮件至 howard dot J dot may gmail dot com

Answer 7

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

1. 检查矩形 1 的任何顶点是否位于矩形 2 内，反之亦然。每当您找到位于另一个矩形内的顶点时，您都​​可以得出结论，它们相交并停止搜索。这将处理一个完全位于另一个矩形内的矩形。
2. 如果上述测试没有结果，则找出 1 个矩形的每条线与另一个矩形的每条线的交点。一旦找到一个交点，检查它是否位于由相应的 4 个点创建的假想矩形之间。一旦找到这样的点，就可以断定它们相交并停止搜索。

如果上述 2 个测试返回 false，则这 2 个矩形不重叠。

Answer 8

关于分离轴测试的公认答案非常有启发性，但我仍然觉得应用它并非易事。我将分享我认为的伪代码，首先使用边界圆测试“优化” （请参阅​​this other answer），以防它可能对其他人有所帮助。我考虑了两个大小相同的矩形 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 中的代码。

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

Answer 9

如果您使用的是 Java，Shape 接口的所有实现都有一个采用矩形的intersects方法。

Answer 10

好吧，蛮力法是走水平矩形的边缘，检查边缘的每个点，看它是落在另一个矩形上还是落在另一个矩形上。

数学答案是形成描述两个矩形的每个边缘的方程。现在您可以简单地查找矩形 A 的四条线中的任何一条是否与矩形 B 的任何一条线相交，这应该是一个简单（快速）的线性方程求解器。

-亚当

Answer 11

您可以找到倾斜矩形的每一边与轴对齐矩形的每一边的交点。通过找到每一边所在的无限线的方程来做到这一点（即基本上是 v1 + t(v2-v1) 和 v'1 + t'(v'2-v'1)），找到当这两个方程相等时，线通过求解 t 相交（如果它们平行，您可以测试），然后测试该点是否位于两个顶点之间的线段上，即 0 <= t 是否正确<= 1 和 0 <= t' <= 1。

但是，这不包括一个矩形完全覆盖另一个矩形的情况。您可以通过测试任一矩形的所有四个点是否都位于另一个矩形内来覆盖。

Answer 12

对于这个问题的3D版本，这就是我要做的：

将 2 个矩形建模为方程 P1 和 P2 描述的平面，然后写出 P1=P2 并从中推导出相交线方程，如果平面平行（不相交）或在同一平面内，则不存在该方程，在这种情况下，你得到 0=0。在这种情况下，您将需要使用 2D 矩形相交算法。

然后我会查看位于两个矩形平面内的那条线是否穿过两个矩形。如果是这样，那么你有 2 个矩形的交集，否则你没有（或者不应该，我可能已经错过了一个角落案例）。

要查找一条线是否通过同一平面中的矩形，我会找到线的 2 个交点和矩形的边（使用线方程对它们进行建模），然后确保交点在范围。

那是数学描述，不幸的是我没有代码来做上面的事情。

Answer 13

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

该算法比分离轴测试更冗长，但更快，因为它只需要在边缘穿过两个象限时进行半平面测试（与使用分离轴方法的多达 32 个测试相反）

该算法的另一个优点是它可以用于测试任何多边形（凸面或凹面）的重叠。据我所知，该算法仅适用于二维空间。

Answer 14

要么我错过了其他东西，为什么要让它如此复杂？

如果 (x1,y1) 和 (X1,Y1) 是矩形的角，那么要找到交点：

    xIntersect = false;
    yIntersect = false;
    if (!(Math.min(x1, x2, x3, x4) > Math.max(X1, X2, X3, X4) || Math.max(x1, x2, x3, x4) < Math.min(X1, X2, X3, X4))) xIntersect = true;
    if (!(Math.min(y1, y2, y3, y4) > Math.max(Y1, Y2, Y3, Y4) || Math.max(y1, y2, y3, y4) < Math.min(Y1, Y2, Y3, Y4))) yIntersect = true;
    if (xIntersect && yIntersect) {alert("Intersect");}

Answer 15

我是这样实现的：

bool rectCollision(const CGRect &boundsA, const Matrix3x3 &mB, const CGRect &boundsB)
{
    float Axmin = boundsA.origin.x;
    float Axmax = Axmin + boundsA.size.width;
    float Aymin = boundsA.origin.y;
    float Aymax = Aymin + boundsA.size.height;

    float Bxmin = boundsB.origin.x;
    float Bxmax = Bxmin + boundsB.size.width;
    float Bymin = boundsB.origin.y;
    float Bymax = Bymin + boundsB.size.height;

    // find location of B corners in A space
    float B0x = mB(0,0) * Bxmin + mB(0,1) * Bymin + mB(0,2);
    float B0y = mB(1,0) * Bxmin + mB(1,1) * Bymin + mB(1,2);

    float B1x = mB(0,0) * Bxmax + mB(0,1) * Bymin + mB(0,2);
    float B1y = mB(1,0) * Bxmax + mB(1,1) * Bymin + mB(1,2);

    float B2x = mB(0,0) * Bxmin + mB(0,1) * Bymax + mB(0,2);
    float B2y = mB(1,0) * Bxmin + mB(1,1) * Bymax + mB(1,2);

    float B3x = mB(0,0) * Bxmax + mB(0,1) * Bymax + mB(0,2);
    float B3y = mB(1,0) * Bxmax + mB(1,1) * Bymax + mB(1,2);

    if(B0x<Axmin && B1x<Axmin && B2x<Axmin && B3x<Axmin)
        return false;
    if(B0x>Axmax && B1x>Axmax && B2x>Axmax && B3x>Axmax)
        return false;
    if(B0y<Aymin && B1y<Aymin && B2y<Aymin && B3y<Aymin)
        return false;
    if(B0y>Aymax && B1y>Aymax && B2y>Aymax && B3y>Aymax)
        return false;

    float det = mB(0,0)*mB(1,1) - mB(0,1)*mB(1,0);
    float dx = mB(1,2)*mB(0,1) - mB(0,2)*mB(1,1);
    float dy = mB(0,2)*mB(1,0) - mB(1,2)*mB(0,0);

    // find location of A corners in B space
    float A0x = (mB(1,1) * Axmin - mB(0,1) * Aymin + dx)/det;
    float A0y = (-mB(1,0) * Axmin + mB(0,0) * Aymin + dy)/det;

    float A1x = (mB(1,1) * Axmax - mB(0,1) * Aymin + dx)/det;
    float A1y = (-mB(1,0) * Axmax + mB(0,0) * Aymin + dy)/det;

    float A2x = (mB(1,1) * Axmin - mB(0,1) * Aymax + dx)/det;
    float A2y = (-mB(1,0) * Axmin + mB(0,0) * Aymax + dy)/det;

    float A3x = (mB(1,1) * Axmax - mB(0,1) * Aymax + dx)/det;
    float A3y = (-mB(1,0) * Axmax + mB(0,0) * Aymax + dy)/det;

    if(A0x<Bxmin && A1x<Bxmin && A2x<Bxmin && A3x<Bxmin)
        return false;
    if(A0x>Bxmax && A1x>Bxmax && A2x>Bxmax && A3x>Bxmax)
        return false;
    if(A0y<Bymin && A1y<Bymin && A2y<Bymin && A3y<Bymin)
        return false;
    if(A0y>Bymax && A1y>Bymax && A2y>Bymax && A3y>Bymax)
        return false;

    return true;
}

矩阵 mB 是将 B 空间中的点转换为 A 空间中的点的任何仿射变换矩阵。这包括简单的旋转和平移、旋转加缩放和完全仿射扭曲，但不包括透视扭曲。

它可能不是尽可能最佳的。速度不是一个大问题。但是，它似乎对我来说还可以。

Answer 16

这是已接受答案的 matlab 实现：

function olap_flag = ol(A,B,sub)

%A and B should be 4 x 2 matrices containing the xy coordinates of the corners in clockwise order

if nargin == 2
  olap_flag = ol(A,B,1) && ol(B,A,1);
  return;
end

urdl = diff(A([1:4 1],:));
s = sum(urdl .* A, 2);
sdiff = B * urdl' - repmat(s,[1 4]);

olap_flag = ~any(max(sdiff)<0);

Answer 17

这是常规方法，逐行检查并检查线是否相交。这是 MATLAB 中的代码。

C1 = [0, 0];    % Centre of rectangle 1 (x,y)
C2 = [1, 1];    % Centre of rectangle 2 (x,y)
W1 = 5; W2 = 3; % Widths of rectangles 1 and 2
H1 = 2; H2 = 3; % Heights of rectangles 1 and 2
% Define the corner points of the rectangles using the above
R1 = [C1(1) + [W1; W1; -W1; -W1]/2, C1(2) + [H1; -H1; -H1; H1]/2];
R2 = [C2(1) + [W2; W2; -W2; -W2]/2, C2(2) + [H2; -H2; -H2; H2]/2];

R1 = [R1 ; R1(1,:)] ;
R2 = [R2 ; R2(1,:)] ;

plot(R1(:,1),R1(:,2),'r')
hold on
plot(R2(:,1),R2(:,2),'b')


%% lines of Rectangles 
L1 = [R1(1:end-1,:) R1(2:end,:)] ;
L2 = [R2(1:end-1,:) R2(2:end,:)] ;
%% GEt intersection points
P = zeros(2,[]) ;
count = 0 ;
for i = 1:4
    line1 = reshape(L1(i,:),2,2) ;
    for j = 1:4
        line2 = reshape(L2(j,:),2,2) ;
        point = InterX(line1,line2) ;
        if ~isempty(point)
            count = count+1 ;
            P(:,count) = point ;
        end
    end
end
%%
if ~isempty(P)
    fprintf('Given rectangles intersect at %d points:\n',size(P,2))
    plot(P(1,:),P(2,:),'*k')
end

可以从以下位置下载函数 InterX：https ://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function

Answer 18

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

R1 = (min_x1, max_x1, min_y1, max_y1)

R2 = (min_x2, max_x2, min_y2, max_y2)

它们重叠当且仅当：

重叠 = (max_x1 > min_x2) 和 (max_x2 > min_x1) 和 (max_y1 > min_y2) 和 (max_y2 > min_y1)

你也可以为 3D 盒子做这件事，实际上它适用于任意数量的维度。

Answer 19

在其他答案中已经说得够多了，所以我只添加伪代码单行：

!(a.left > b.right || b.left > a.right || a.top > b.bottom || b.top > a.bottom);

Answer 20

检查两个矩形的所有顶点的质心是否位于其中一个矩形内。