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

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，反之亦然。如果你找到一个离边缘的目的不相交的(提供的所有其他分在B的另一侧的边缘正在测试-看画下文)。如果你找不到离边缘无论是矩形交叉或一个矩形是包含在其他。

测试适用于任何凸面顺便说一下..

修正案: 为确定分离的边缘，这是不够的试验的所有要点的一个矩形针对每个边缘。候选边E(下文)将这样被确定为分离的边缘，因为所有的点是在同样的半的飞机的E.然而，它不是一个分离的边缘，因为顶点Vb1和Vb2B还在于半的飞机。它只会已经分离边缘如果没有的情况下 http://www.iassess.com/collision.png

Answer 2

基本上看下图：

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

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

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

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

Answer 3

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的widthA'：Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle) widthB'表示rectB：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（游戏开发大会2007）PPT www.realtimecollisiondetection.net/pubs/ GDC07_Ericson_Physics_Tutorial_SAT.ppt

Answer 4

在Cocoa中，您可以轻松检测selectedArea rect是否与旋转的NSView的frame rect相交。 你甚至不需要计算多边形，法线等。只需将这些方法添加到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 5

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

如果您需要更高的速度，则有用于线段交叉（扫描线）的高级算法。请参见 http://en.wikipedia.org/wiki/Line_segment_intersection

Answer 6

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

在网络上搜索“无拟合多边形”并查看是否可以找到凸多边形的算法（如果您有凹多边形，它会变得更复杂）。如果你找不到任何东西，那么请给我发电子邮件：Howard dot J dot may gmail dot com

Answer 7

我认为这将照顾所有可能的情况。 做以下测试。

1. 检查矩形1的任何顶点是否位于矩形2内，反之亦然。无论何时找到位于另一个矩形内的顶点，您都可以断定它们相交并停止搜索。这将照顾一个完全位于另一个内部的矩形。
2. 如果上述测试不确定，则找到1个矩形的每一行与另一个矩形的每一行的交叉点。一旦找到交叉点，检查它是否位于由相应的4个点创建的虚构矩形内。当发现这样一个点时，他们会相交并停止搜索。

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

Answer 8

如果你正在使用Java，那么Shape接口的所有实现都有一个相交方法，它采用矩形。

Answer 9

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

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

- 亚当

Answer 10

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

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

Answer 11

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

将2个矩形建模为等式P1和P2描述的平面，然后写出P1 = P2并从中得出交叉线方程，如果平面是平行的（没有交叉点），或者在同一平面，在这种情况下你会得到0 = 0。在这种情况下，您将需要使用2D矩形交叉算法。

然后我会看到在两个矩形的平面中的那条线是否通过两个矩形。如果确实如此，那么你有一个2个矩形的交叉点，否则你不会（或者不应该，我可能错过了我脑袋里的角落）。

要查找一条线是否通过同一平面中的一个矩形，我会找到该线与矩形边的2个交点（使用线方程建模），然后确定交点的点在范围内。

这是数学描述，遗憾的是我没有代码可以执行上述操作。

Answer 12

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

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

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

Answer 13

要么我错过了其他的原因，为什么要这么复杂？

如果（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 14

我实现了这样：

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 15

以下是接受答案的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 16

这是传统方法，逐行检查并检查线是否相交。这是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功能：

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

R1 =（min_x1，max_x1，min_y1，max_y1）

R2 =（min_x2，max_x2，min_y2，max_y2）

当且仅当：

时，它们重叠

重叠=（max_x1 <！> gt; min_x2）和（max_x2 <！> gt; min_x1）和（max_y1 <！> gt; min_y2）和（max_y2 <！> gt; min_y1）

你也可以用于3D盒子，实际上它适用于任何数量的尺寸。

在其他答案中已经说过了，所以我只想添加伪代码：

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

Answer 17

Answer 18

Answer 19

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

R1 =（min_x1，max_x1，min_y1，max_y1）

R2 =（min_x2，max_x2，min_y2，max_y2）

当且仅当：

时，它们重叠

重叠=（max_x1 <！> gt; min_x2）和（max_x2 <！> gt; min_x1）和（max_y1 <！> gt; min_y2）和（max_y2 <！> gt; min_y1）

你也可以用于3D盒子，实际上它适用于任何数量的尺寸。

Answer 20

在其他答案中已经说过了，所以我只想添加伪代码：

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

Answer 21

在其他答案中已经说过了，所以我只想添加伪代码：

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

Answer 22

Answer 23