algorithm检测两个矩形的交集?

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

testing一个angular落是否在其他几乎所有的工作。 如果矩形形成十字形状,则失败。

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

标准的方法是做分离轴testing (做一个谷歌search)。

简而言之:

  • 如果可以find分隔两个对象的一条线,则两个对象不会相交。 例如物体/物体的所有点都在线的不同侧。

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

在2D中,你可以不使用斜坡。 边被简单地定义为两个顶点之间的差异,例如

edge = v(n) - v(n-1) 

通过旋转90°可以得到与此垂直的线。 在2D中,这很容易:

  rotated.x = -unrotated.y rotated.y = unrotated.x 

所以没有涉及三angular或斜坡。 将vector规范化为单位长度也不是必需的。

如果你想testing一个点是否在线的另一边,你可以使用点积。 标志会告诉你你在哪一边:

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

现在testing矩形A的所有点对矩形B的边缘,反之亦然。 如果find分离边缘,则物体不会相交(如果B中的所有其他点位于正在testing边缘的另一边 – 请参见下图)。 如果找不到分离边,则矩形相交或一个矩形包含在另一个矩形中。

testing适用于任何凸多边形btw ..

修正:为了确定一个分离的边缘,仅仅对一个矩形的所有点对另一个的边缘进行testing是不够的。 因为A中的所有点都在E的相同半平面中,所以候选边E(下面)将被识别为分离边。然而,它不是分离边,因为B的顶点Vb1和Vb2也在那个半平面上。 这只会是一个分裂的边缘,如果没有的话http://www.iassess.com/collision.png

基本上看下面的图片:

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

如果两个箱子碰撞,线路A和B将重叠。

请注意,这将不得不在X轴和Y轴上完成,并且都需要重叠的矩形碰撞。

gamasutra.com有一篇很好的文章回答了这个问题(图片来自文章)。 5年前,我做了类似的algorithm,我必须find我的代码片段,稍后再发布

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

在Cocoa中,您可以轻松检测到selectedArea矩形是否与旋转的NSView的框架矩形相交。 你甚至不需要计算多边形,法线等。 只需将这些方法添加到您的NSView子类。 例如,用户在NSView的超级视图上select一个区域,然后调用传递selectedArea rect的方法DoesThisRectSelectMe。 API convertRect:将完成这项工作。 当你点击NSView来select它时,同样的技巧就可以工作。 在这种情况下,简单地重写下面的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; } 

m_pGladiator的答案是正确的,我更喜欢它。 分离轴testing是检测矩形重叠的最简单和标准的方法。 投影间隔不重叠的线称为分离轴 。 尼尔斯·皮彭布林克的解决scheme太笼统了。 它使用点积来检查一个形状是否完全在另一个边的一边。 这个解决scheme实际上可能会导致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 } 

不同的是宽度'现在有点不同:widthA'为rectA: 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)

  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 http://www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt

检查一个矩形中的任何一条线是否与另一条线相交。 天真的线段交集很容易编码。

如果您需要更快的速度,则有用于线段相交(扫描线)的高级algorithm。 见http://en.wikipedia.org/wiki/Line_segment_intersection

一种解决scheme是使用称为无适合多边形的东西。 这个多边形是从两个多边形(概念上是通过滑动一个在另一个的周围)计算出来的,它定义了多边形在其相对偏移下重叠的区域。 一旦你有了这个NFP,那么你只需要做一个包含testing,这个testing的两个多边形的相对偏移量给出了一个点。 这个包含testing是快速和容易的,但你必须首先创buildNFP。

在Web上searchNo Fit Polygon,查看是否可以find凸多边形的algorithm(如果您有凹多边形,它会变得更加复杂)。 如果你找不到任何东西,请给我发电子邮件在霍华德点J可能gmail点com

这是我认为会照顾所有可能的情况。 做下面的testing。

  1. 检查矩形1的任何顶点位于矩形2内,反之亦然。 任何时候,如果find位于另一个矩形内的顶点,就可以断定它们相交并停止search。 这将会照顾一个完全在另一个中的矩形。
  2. 如果上述testing不确定,则找出一个矩形的每一行与另一个矩形的每一行的相交点。 一旦find交点,检查它是否位于由相应的4点创build的虚构矩形内。 当发现这样的一个点时,他们相交并停止search。

如果上述2个testing返回false,那么这两个矩形不重叠。

如果使用Java,则Shape接口的所有实现都有一个矩形的相交方法。

您可以findangular度矩形的每一边与轴alignment的每一边的交点。 通过find每一边所在的无限长线的方程(基本上是v1 + t(v2-v1)和v'1 + t'(v'2-v'1))来find这个点,find当这两个方程相等时(如果它们是平行的,你可以testing这个),然后testing这个点是否位于两个顶点之间的线段上,也就是0 <= t <= 1且0 <= t'<= 1。

但是,这不包括一个矩形完全覆盖另一个矩形的情况。 您可以通过testing是否矩形的所有四个点位于另一个矩形内来进行覆盖。

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

将两个矩形build模为由方程P1和P2描述的平面,然后写入P1 = P2,并从中得出如果平面平行(不交叉)时不存在的交线方程,或者处于同一平面内,在这种情况下,你得到0 = 0。 在这种情况下,您将需要使用二维矩形交集algorithm。

然后,我会看看是否在两个矩形的平面中的这条线穿过两个矩形。 如果是这样,那么你有一个2矩形的交集,否则你不(或不应该,我可能错过了我的头一个angular落的情况下)。

要find一条直线穿过同一平面上的一个矩形,我会find直线和矩形两边的交点(用线方程build模),然后确定交点与范围。

这是math描述,不幸的是我没有代码去做以上的事情。

另一种比使用分离轴testing稍微快一些的testing方法是在每个矩形(任意select的)的每个顶点上使用缠绕数algorithm(仅在象限上, 而不是angular度累加,这是非常慢的)。 如果任何一个顶点的匝数不为零,则两个矩形重叠。

这个algorithm比分离轴testing稍微长一点,但是速度更快,因为如果边缘跨过两个象限,它只需要半平面testing(相对于使用分离轴方法的多达32个testing)

该algorithm还具有可用于testing任何多边形(凸面或凹面)重叠的优点。 据我所知,该algorithm只适用于二维空间。

要么我错过了其他的东西,为什么这么复杂呢?

如果(x1,y1)和(X1,Y1)是矩形的angular点,则find交点:

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

matrixmB是任何仿射变换matrix,其将B空间中的点转换成A空间中的点。 这包括简单的旋转和平移,旋转加缩放,以及完整的仿射经纱,但不包括透视扭曲。

它可能不是最佳的。 速度不是一个大问题。 但是它似乎对我来说工作正常。

下面是接受的答案的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的function可以从以下url下载: https ://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab = function

我有一个简单的方法,如果我们有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盒子做,实际上它适用于任何维度。

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

math答案是形成描述两个矩形的每个边的方程。 现在,您可以简单地find矩形A的四条线中的任何一条是否与矩形B的任何一条线相交,这应该是简单的(快速)线性方程求解器。

-亚当