Algorithme pour détecter l'intersection de deux rectangles?

regardez essentiellement l'image suivante:

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

si les deux boîtes entrent en collision, les lignes A et B se chevauchent.

noter que cela devra être fait à la fois sur l'axe X et l'axe Y, et les deux doivent se chevaucher pour que les rectangles entrent en collision.

il y a un bon article dans gamasutra.com qui répond à la question (la photo est tirée de l'article). J'ai fait un algorithme similaire il y a 5 ans et je dois trouver mon code snippet pour le poster ici plus tard

amendement : le théorème de L'axe de séparation stipule que deux formes convexes ne se chevauchent pas si un axe de séparation existe (c.-à-d. Un où les projections comme indiqué ne se chevauchent pas ). Donc "un axe de séparation existe" => "Pas de chevauchement". Ce n'est pas une double implication, donc vous ne pouvez pas conclure l'inverse.

dans Cocoa, vous pouvez facilement détecter si le selectedarea rect coupe le cadre de votre NSView rect. Vous n'avez même pas besoin de calculer les polygones, les normaux un tel. Il suffit d'ajouter ces méthodes à votre sous-classe NSView. Par exemple, l'utilisateur sélectionne une zone sur la superview de NSView, puis vous appelez la méthode DoesThisRectSelectMe en passant la selectedarea rect. L'API convertRect: fera ce travail. La même astuce fonctionne lorsque vous cliquez sur NSView pour la sélectionner. Dans ce cas, tout simplement remplacer la méthode hitTest comme ci-dessous. L'API convertPoint: va le faire ;-)

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

la réponse de m_pGladiator est juste et je la préfère. la Séparation de test de l'axe est la plus simple et la méthode standard pour détecter rectangle de chevauchement. Une ligne pour laquelle les intervalles de projection ne se chevauchent pas nous appelons un axe de séparation . La solution de Nils Pipenbrinck est trop générale. produit scalaire pour vérifier si une forme est totalement sur l'un des côtés de la bordure de l'autre. Cette solution est en fait pourrait induire à n-bord de polygones convexes. Cependant, il n'est pas optmized pour deux rectangles.

le point critique de la réponse de m_pGladiator est qu'il faut vérifier la projection de deux rectangles sur les deux axes (x et y). Si deux projections se chevauchent, on peut dire que ces deux rectangles se chevauchent. Les commentaires ci-dessus à la réponse de m_pGladiator sont donc erronés.

pour la situation simple, si deux rectangles ne sont pas tournés, nous présentons un rectangle avec structure:

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

nous appelons rectangle a, b avec 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

si l'un des deux rectangles est pivoté, Il faudra peut-être faire des efforts pour déterminer leur projection sur les axes x et Y. Définissez struct RotatedRect comme suit:

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

la différence est comment la largeur" est maintenant un peu différent: widthA 'for rectA: Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle) widthB 'pour 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

pourrait se référer à un GDC(Game Development Conference 2007) PPT www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt

Vérifier pour voir si l'une des lignes d'un rectangle se coupent l'une des lignes de l'autre. L'intersection de segments de ligne naïve est facile à coder.

si vous avez besoin de plus de vitesse, il y a des algorithmes avancés pour l'intersection de segments de ligne (balayage-ligne). Voir http://en.wikipedia.org/wiki/Line_segment_intersection

une solution consiste à utiliser un polygone qui ne convient pas. Ce polygone est calculé à partir des deux polygones (en faisant glisser l'un autour de l'autre) et il définit la zone pour laquelle les polygones se chevauchent étant donné leur décalage relatif. Une fois que vous avez ce NFP, vous devez simplement faire un test d'inclusion avec un point donné par le décalage relatif des deux polygones. Ce test d'inclusion est rapide et facile, mais vous devez d'abord créer le NFP.

ont un cherchez le polygone no Fit sur le web et voyez si vous pouvez trouver un algorithme pour les polygones convexes (il devient beaucoup plus complexe si vous avez des polygones concaves). Si vous ne trouvez rien, alors envoyez-moi un courriel à howard dot j dot may gmail dot com

voici ce que je pense va s'occuper de tous les cas possibles. Faites les tests suivants.

1. cochez l'un des sommets du rectangle 1 qui se trouve à l'intérieur du rectangle 2 et vice versa. Chaque fois que vous trouvez un vertex qui réside à l'intérieur de l'autre rectangle, vous pouvez conclure qu'ils se croisent et arrêter la recherche. Cela prendra soin d'un rectangle résidant complètement à l'intérieur de l'autre.
2. si l'essai ci-dessus n'est pas concluant, trouver le points d'intersection de chaque ligne de 1 rectangle avec chaque ligne de l'autre rectangle. Une fois qu'un point d'intersection est trouvé, Vérifiez s'il réside entre l'intérieur du rectangle imaginaire créé par les 4 points correspondants. Quand jamais un tel point est trouvé en conclure qu'ils se croisent et arrêter la recherche.

si les 2 tests ci-dessus renvoient false, alors ces 2 rectangles ne se chevauchent pas.

si vous utilisez Java, toutes les implémentations de L'interface Shape ont une méthode intersectes qui prend un rectangle.

bien, la méthode de la force brute consiste à parcourir les bords du rectangle horizontal et à vérifier chaque point le long du bord pour voir s'il tombe sur ou dans l'autre rectangle.

la réponse mathématique est de former des équations décrivant chaque bord des deux rectangles. Maintenant vous pouvez simplement trouver si l'une des quatre lignes du rectangle a croisent l'une des lignes du rectangle B, qui devrait être un simple (rapide) solution d'équation linéaire.

- Adam

vous pouvez trouver l'intersection de chaque côté du rectangle en angle avec chaque côté du rectangle aligné sur l'axe. Faites ceci en trouvant l'équation de la ligne infinie sur laquelle se trouve chaque côté (i.e. v1 + t(v2-v1) et v'1 + t'(v'2-v'1) fondamentalement), en trouvant le point auquel les lignes se rencontrent en résolvant pour t quand ces deux équations sont égales (si elles sont parallèles, vous pouvez tester pour cela) et ensuite en testant si ce point se trouve sur le segment de ligne entre les deux sommets, c'est-à-dire est-il vrai que 0 <= t <= 1 et 0 <= t <= 1.

cependant, cela ne couvre pas le cas où un rectangle couvre complètement l'autre. Que vous pouvez couvrir en testant si les quatre points de rectangle se trouvent à l'intérieur de l'autre rectangle.

C'est ce que je ferais, pour la 3D version de ce problème:

modéliser les 2 rectangles comme des plans décrits par l'équation P1 et P2, puis écrire P1=P2 et dériver de cela la ligne d'équation d'intersection, qui n'existera pas si les plans sont parallèles (pas d'intersection), ou sont dans le même plan, dans ce cas vous obtenez 0=0. Dans ce cas, vous aurez besoin d'employer un rectangle 2D algorithme d'intersection.

Puis Je verrait si cette ligne, qui est dans le plan des deux rectangles, passe à travers les deux rectangles. Si elle le fait, alors vous avez une intersection de 2 rectangles, sinon vous ne le faites pas (ou ne devriez pas, je pourrais avoir manqué une caisse de coin dans ma tête).

pour trouver si une ligne passe à travers un rectangle dans le même plan, je trouverais les 2 points d'intersection de la ligne et les côtés du rectangle (les modéliser en utilisant des équations de ligne), et puis s'assurer les points de les intersections sont à portée.

qui est la description mathématique, malheureusement je n'ai pas de code pour faire ce qui précède.

une autre façon de faire le test qui est légèrement plus rapide que l'utilisation du test de l'axe de séparation, est d'utiliser l'algorithme des nombres d'enroulement (sur les quadrants seulement - pas angle-sommation qui est horriblement lente) sur chaque vertex de l'un ou l'autre rectangle (choisi arbitrairement). Si l'un des sommets a un nombre d'enroulement non nul, les deux rectangles se chevauchent.

cet algorithme est un peu plus long que le test de l'axe de séparation, mais il est plus rapide parce qu'il n'est nécessaire d'effectuer un essai à demi-plan que si les bords croisent deux quadrants (par opposition à un maximum de 32 essais utilisant la méthode de l'axe de séparation)

L'algorithme a l'avantage qu'il peut être utilisé pour tester le chevauchement de tout polygone (convexe ou concave). Autant que je sache, l'algorithme ne fonctionne que dans l'espace 2D.

soit je manque quelque chose d'autre pourquoi rendre cela si compliqué?

si (x1, y1) et (X1, Y1) sont des coins des rectangles, alors pour trouver l'intersection faire:

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

Je l'ai mis en œuvre comme ceci:

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

la matrice mB est toute matrice transformante affine qui convertit des points dans l'Espace B en points dans l'espace A. Cela comprend la rotation simple et la traduction, la rotation plus l'échelle, et les crampes affines complètes, mais pas les crampes en perspective.

C'est peut-être pas aussi optimale que possible. La vitesse n'était pas une préoccupation majeure. Cependant, il semble fonctionner pour moi.

Voici une implémentation matlab de la réponse acceptée:

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

c'est la méthode conventionnelle, aller ligne par ligne et vérifier si les lignes se croisent. Voici le code en 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

la fonction InterX peut être téléchargée à partir de: https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function

j'ai ma propre méthode plus simple, si nous avons 2 rectangles:

R1 = (min_x1, max_x1, min_y1, max_y1)

R2 = (min_x2, max_x2, min_y2, max_y2)

elles se chevauchent si et seulement si:

vous pouvez le faire pour les boîtes 3D aussi, en fait il fonctionne pour un certain nombre de dimensions.

cela a été dit dans D'autres réponses, donc je vais juste ajouter le pseudocode one-liner:

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