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

如果您使用的是 Java，则 ShapeInterface 的所有实现都有一个采用矩形的 有交集方法。

蛮力方法是遍历水平矩形的边缘并检查沿边缘的每个点，看看它是落在另一个矩形上还是在另一个矩形里。

数学上的答案是形成描述两个矩形的每个边的方程。现在你可以简单地找出，如果任何四条线从矩形 A 相交的任何线的矩形 B，这应该是一个简单(快速)线性方程式解决方案。

亚当

检查来自一个矩形的任何直线是否与来自另一个矩形的任何直线相交。单纯的线段交会很容易编码。

如果你需要更快的速度，有高级的线段交会算法(扫描线)

您可以找到角矩形的每一边与轴对齐的矩形的每一边的交集。通过找到每一边所在的无限长线的方程(即 v1 + t (v2-v1)和 v1 + t’(v2-v’1)) ，通过求解这两个方程相等时的 t (如果它们是平行的，你可以测试这一点)来找到这两条线相交的点，然后测试这一点是否位于两个顶点之间的线段，即0 < = t < = 1和0 < = t’< = 1是真的吗。

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

基本上看下面的图片:

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

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

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

修正 : 分离轴定理指出，如果有一个分离轴存在，则两个凸形 不要重叠(即所示的投影重叠的一个)。所以“一个分离轴存在”= > “没有重叠”。这不是双重含义，所以你不能得出相反的结论。

对于这个问题的 3D版本，我会这样做:

将两个矩形建模为方程 P1和 P2所描述的平面，然后写出 P1 = P2并由此导出交线方程，如果平面是平行的(没有交线) ，或者在同一平面内，则交线方程不存在，在这种情况下，得到0 = 0。在这种情况下，您将需要采用一个2D 矩形交算法。

然后我会看到那条线，在两个矩形的平面上，是否都穿过了两个矩形。如果是这样，那么你就得到了2个矩形的交集，否则你就没有(或者不应该有，我可能在我的脑海中遗漏了一个边框)。

为了找出一条直线是否在同一个平面上通过一个矩形，我会找出直线和矩形边的两个交点(使用线方程对它们进行建模) ，然后确保交点在一定范围内。

这是数学描述，不幸的是，我没有代码来做以上。

标准的方法是做 分离轴试验分离轴试验(在谷歌上搜索一下)。

简而言之:

• 如果你能找到一条分隔两个对象的线，那么两个对象就不会相交。例如，物体/物体的所有点都在直线的不同侧面。

有趣的是，仅仅检查两个矩形的所有边就足够了。如果矩形没有重叠，其中一条边就是分隔轴。

在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.iassess.com/collision.png

一个解决方案是使用一个叫做不适合多边形的东西。这个多边形是从两个多边形中计算出来的(概念上是通过将一个多边形滑动到另一个多边形上) ，它定义了多边形重叠的区域，并给出了它们的相对偏移量。一旦你有了这个 NFP，那么你只需要做一个包含测试，用两个多边形的相对偏移量给出一个点。这个包含测试快速而简单，但是您必须首先创建 NFP。

在网上搜索“不适合多边形”，看看你能否找到一个凸多边形的算法(如果你有凹多边形，它会变得更加复杂)。如果你找不到任何东西，请发邮件到 Howard. J. may gmail. com

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

这个算法比分离轴测试稍微长一些，但是更快，因为它只需要一个半平面测试，如果边跨越两个象限(相对于使用分离轴方法的多达32个测试)

该算法的进一步优点是可以用来检测 任何多边形(凸或凹)的重叠。据我所知，这个算法只能在二维空间中运行。

角斗士的回答是正确的，我更喜欢它。 分离轴测试 是检测矩形重叠最简单和标准的方法。投影间隔不重叠的线称为 分离轴。尼尔斯•皮彭布林克(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 RoatedRect:

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: Math.sqrt(rectB.width*rectB.width + rectB.height*rectB.height) * Math.cos(rectB.angle)的宽度 B’

    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

在 Cocoa 中，你可以很容易地检测到 selectedArea rect 是否与你旋转的 NSView 的帧 rect 相交。 您甚至不需要计算多边形，只需将这些方法添加到您的 NSView 子类中。 例如，用户在 NSView 的超视图中选择一个区域，然后通过 selectedArea rect 调用 DoesThisRectSelectMe 方法。API ConvertRect: 将完成这项工作。当你点击 NSView 来选择它的时候，同样的技巧也起作用了。在这种情况下，只需像下面这样重写 hitTest 方法。API 转换点: 将执行该任务; -)

- (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;
}

要么是我错过了什么，为什么把事情搞得这么复杂？

如果(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");}

我是这样实施的:

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 空间中的点的任意仿射变换矩阵。这包括简单的旋转和平移、旋转加缩放和完全仿射扭曲，但不包括透视扭曲。

这可能不是最佳选择。速度并不是一个大问题。不过看起来对我来说还不错。

以下是我认为可以解决所有可能问题的方法。 做以下测试。

1. 检查矩形1的任何顶点位于矩形2内，反之亦然。任何时候你发现一个顶点居住在另一个矩形，你可以得出结论，他们相交和停止搜索。这将照顾一个矩形完全居住在另一个。
2. 如果上面的测试是不确定的，找出1个矩形的每一行与另一个矩形的每一行的交点。一旦找到一个交点，检查它是否位于由相应的4个点创建的虚拟矩形之间。每当发现这样一个点，就得出结论，它们相交并停止搜索。

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

下面是 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);

这是传统的方法，一行一行地检查线是否相交。这是 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

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

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 盒子这样做，实际上它适用于任何数量的尺寸。

在其他答案中已经说得够多了，所以我只需要添加伪代码一行程序:

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

关于 分离轴试验分离轴试验的 接受的答案非常有启发性，但是我仍然觉得应用它并不是微不足道的。我将分享我认为的伪代码，“优化”第一与 边界圆测试边界圆测试边界圆测试(见 另一个答案) ，以防它可能帮助其他人。我考虑了两个大小相同的矩形 A 和 B (但是考虑一般情况很简单)。

1边界圆测试:

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

计算速度比分离轴测试快得多。您只需要在两个圆圈碰撞的情况下考虑分离轴测试。

2分离轴试验

主要思想是:

• 考虑一个矩形，沿着它的顶点 V (i)循环。

• 计算矢量 Si + 1: V (i + 1)-V (i)。

• 用 Si + 1: Ni = (- Si + 1计算矢量 Ni。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给你中找到代码。

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

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