Algorithm to detect intersection of two rectangles

问题:

I\'m looking for an algorithm to detect if two rectangles intersect (one at an arbitrary angle, the other with only vertical/horizontal lines).

Testing if a corner of one is in the other ALMOST works. It fails if the rectangles form a cross-like shape.

It seems like a good idea to avoid using slopes of the lines, which would require special cases for vertical lines.

回答1:

The standard method would be to do the separating axis test (do a google search on that).

In short:

• Two objects don\'t intersect if you can find a line that separates the two objects. e.g. the objects / all points of an object are on different sides of the line.

The fun thing is, that it\'s sufficient to just check all edges of the two rectangles. If the rectangles don\'t overlap one of the edges will be the separating axis.

In 2D you can do this without using slopes. An edge is simply defined as the difference between two vertices, e.g.

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

You can get a perpendicular to this by rotating it by 90°. In 2D this is easy as:

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

So no trigonometry or slopes involved. Normalizing the vector to unit-length is not required either.

If you want to test if a point is on one or another side of the line you can just use the dot-product. the sign will tell you which side you\'re on:

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

Now test all points of rectangle A against the edges of rectangle B and vice versa. If you find a separating edge the objects don\'t intersect (providing all other points in B are on the other side of the edge being tested for - see drawing below). If you find no separating edge either the rectangles are intersecting or one rectangle is contained in the other.

The test works with any convex polygons btw..

Amendment: To identify a separating edge, it is not enough to test all points of one rectangle against each edge of the other. The candidate-edge E (below) would as such be identified as a separating edge, as all points in A are in the same half-plane of E. However, it isn\'t a separating edge because the vertices Vb1 and Vb2 of B are also in that half-plane. It would only have been a separating edge if that had not been the case http://www.iassess.com/collision.png

回答2:

Basically look at the following picture:

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

If the two boxes collide, the lines A and B will overlap.

Note that this will have to be done on both the X and the Y axis, and both need to overlap for the rectangles to collide.

There is a good article in gamasutra.com which answers the question (the picture is from the article). I did similar algorithm 5 years ago and I have to find my code snippet to post it here later

Amendment: The Separating Axis Theorem states that two convex shapes do not overlap if a separating axis exists (i.e. one where the projections as shown do not overlap). So \"A separating axis exists\" => \"No overlap\". This is not a bi-implication so you cannot conclude the converse.

回答3:

In Cocoa you could easily detect whether the selectedArea rect intersects your rotated NSView\'s frame rect. You don\'t even need to calculate polygons, normals an such. Just add these methods to your NSView subclass. For instance, the user selects an area on the NSView\'s superview, then you call the method DoesThisRectSelectMe passing the selectedArea rect. The API convertRect: will do that job. The same trick works when you click on the NSView to select it. In that case simply override the hitTest method as below. The API convertPoint: will do that job ;-)

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

回答4:

m_pGladiator\'s answer is right and I prefer to it. Separating axis test is simplest and standard method to detect rectangle overlap. A line for which the projection intervals do not overlap we call a separating axis. Nils Pipenbrinck\'s solution is too general. It use dot product to check whether one shape is totally on the one side of the edge of the other. This solution is actually could induce to n-edge convex polygons. However, it is not optmized for two rectangles.

the critical point of m_pGladiator\'s answer is that we should check two rectangles\' projection on both axises (x and y). If two projections are overlapped, then we could say these two rectangles are overlapped. So the comments above to m_pGladiator\'s answer are wrong.

for the simple situation, if two rectangles are not rotated, we present a rectangle with structure:

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

we name rectangle A, B with 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

if any one of the two rectangles are rotated, It may needs some efforts to determine the projection of them on x and y axises. Define struct RotatedRect as following:

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

the difference is how the width\' is now a little different: widthA\' for rectA: Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle) widthB\' for 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

Could refer to a GDC(Game Development Conference 2007) PPT www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt

回答5:

Check to see if any of the lines from one rectangle intersect any of the lines from the other. Naive line segment intersection is easy to code up.

If you need more speed, there are advanced algorithms for line segment intersection (sweep-line). See http://en.wikipedia.org/wiki/Line_segment_intersection

回答6:

One solution is to use something called a No Fit Polygon. This polygon is calculated from the two polygons (conceptually by sliding one around the other) and it defines the area for which the polygons overlap given their relative offset. Once you have this NFP then you simply have to do an inclusion test with a point given by the relative offset of the two polygons. This inclusion test is quick and easy but you do have to create the NFP first.

Have a search for No Fit Polygon on the web and see if you can find an algorithm for convex polygons (it gets MUCH more complex if you have concave polygons). If you can\'t find anything then email me at howard dot J dot may gmail dot com

回答7:

Here is what I think will take care of all possible cases. Do the following tests.

1. Check any of the vertices of rectangle 1 reside inside rectangle 2 and vice versa. Anytime you find a vertex that resides inside the other rectangle you can conclude that they intersect and stop the search. THis will take care of one rectangle residing completely inside the other.
2. If the above test is inconclusive find the intersecting points of each line of 1 rectangle with each line of the other rectangle. Once a point of intersection is found check if it resides between inside the imaginary rectangle created by the corresponding 4 points. When ever such a point is found conclude that they intersect and stop the search.

If the above 2 tests return false then these 2 rectangles do not overlap.

回答8:

If you\'re using Java, all implementations of the Shape interface have an intersects method that take a rectangle.

回答9:

Well, the brute force method is to walk the edges of the horizontal rectangle and check each point along the edge to see if it falls on or in the other rectangle.

The mathematical answer is to form equations describing each edge of both rectangles. Now you can simply find if any of the four lines from rectangle A intersect any of the lines of rectangle B, which should be a simple (fast) linear equation solver.

-Adam

回答10:

You could find the intersection of each side of the angled rectangle with each side of the axis-aligned one. Do this by finding the equation of the infinite line on which each side lies (i.e. v1 + t(v2-v1) and v\'1 + t\'(v\'2-v\'1) basically), finding the point at which the lines meet by solving for t when those two equations are equal (if they\'re parallel, you can test for that) and then testing whether that point lies on the line segment between the two vertices, i.e. is it true that 0 <= t <= 1 and 0 <= t\' <= 1.

However, this doesn\'t cover the case when one rectangle completely covers the other. That you can cover by testing whether all four points of either rectangle lie inside the other rectangle.

回答11:

This is what I would do, for the 3D version of this problem:

Model the 2 rectangles as planes described by equation P1 and P2, then write P1=P2 and derive from that the line of intersection equation, which won\'t exist if the planes are parallel (no intersection), or are in the same plane, in which case you get 0=0. In that case you will need to employ a 2D rectangle intersection algorithm.

Then I would see if that line, which is in the plane of both rectangles, passes through both rectangles. If it does, then you have an intersection of 2 rectangles, otherwise you don\'t (or shouldn\'t, I might have missed a corner case in my head).

To find if a line passes through a rectangle in the same plane, I would find the 2 points of intersection of the line and the sides of the rectangle (modelling them using line equations), and then make sure the points of intersections are with in range.

That is the mathematical descriptions, unfortunately I have no code to do the above.

回答12:

Another way to do the test which is slightly faster than using the separating axis test, is to use the winding numbers algorithm (on quadrants only - not angle-summation which is horrifically slow) on each vertex of either rectangle (arbitrarily chosen). If any of the vertices have a non-zero winding number, the two rectangles overlap.

This algorithm is somewhat more long-winded than the separating axis test, but is faster because it only require a half-plane test if edges are crossing two quadrants (as opposed to up to 32 tests using the separating axis method)

The algorithm has the further advantage that it can be used to test overlap of any polygon (convex or concave). As far as I know, the algorithm only works in 2D space.

回答13:

Either I am missing something else why make this so complicated?

if (x1,y1) and (X1,Y1) are corners of the rectangles, then to find intersection do:

    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\");}

回答14:

I implemented it like this:

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

The matrix mB is any affine transform matrix that converts points in the B space to points in the A space. This includes simple rotation and translation, rotation plus scaling, and full affine warps, but not perspective warps.

It may not be as optimal as possible. Speed was not a huge concern. However it seems to work ok for me.

回答15:

Here is a matlab implementation of the accepted answer:

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

回答16:

This is the conventional method, go line by line and check whether the lines are intersecting. This is the code in 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

the function InterX can be downloaded from: https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function

回答17:

I have a simplier method of my own, if we have 2 rectangles:

R1 = (min_x1, max_x1, min_y1, max_y1)

R2 = (min_x2, max_x2, min_y2, max_y2)

They overlap if and only if:

Overlap = (max_x1 > min_x2) and (max_x2 > min_x1) and (max_y1 > min_y2) and (max_y2 > min_y1)

You can do it for 3D boxes too, actually it works for any number of dimensions.

回答18:

Enough has been said in other answers, so I\'ll just add pseudocode one-liner:

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