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

Je recherche un algorithme pour détecter si deux rectangles se croisent (l'un à un angle arbitraire, l'autre avec uniquement des lignes verticales / horizontales).

Tester si un coin de l'un est dans l'autre fonctionne PRESQUE. Il échoue si les rectangles forment une forme en forme de croix.

Cela semble être une bonne idée d'éviter d'utiliser les pentes des lignes, ce qui nécessiterait des cas particuliers pour les lignes verticales.

La méthode standard serait de faire le test de l'axe de séparation (faire une recherche Google à ce sujet).

En bref:

• Deux objets ne se croisent pas si vous pouvez trouver une ligne qui sépare les deux objets. Par exemple, les objets / tous les points d'un objet se trouvent sur des côtés différents de la ligne.

Ce qui est amusant, c'est qu'il suffit de vérifier tous les bords des deux rectangles. Si les rectangles ne se chevauchent pas, l'un des bords sera l'axe de séparation.

En 2D, vous pouvez le faire sans utiliser de pentes. Une arête est simplement définie comme la différence entre deux sommets, par exemple

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

Vous pouvez obtenir une perpendiculaire à celle-ci en la tournant de 90 °. En 2D, c'est facile car:

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

Donc pas de trigonométrie ou de pentes impliquées. La normalisation du vecteur à la longueur unitaire n'est pas non plus nécessaire.

Si vous voulez tester si un point est sur un côté ou un autre de la ligne, vous pouvez simplement utiliser le produit scalaire. le panneau vous indiquera de quel côté vous êtes:

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

Maintenant, testez tous les points du rectangle A contre les bords du rectangle B et vice versa. Si vous trouvez une arête de séparation, les objets ne se coupent pas (à condition que tous les autres points de B soient de l'autre côté de l'arête testée - voir le dessin ci-dessous). Si vous ne trouvez pas d'arête de séparation, les rectangles se croisent ou un rectangle est contenu dans l'autre.

Le test fonctionne avec tous les polygones convexes btw.

Amendement: Pour identifier une arête de séparation, il ne suffit pas de tester tous les points d'un rectangle contre chaque bord de l'autre. L'arête candidate E (ci-dessous) serait en tant que telle identifiée comme une arête de séparation, car tous les points de A sont dans le même demi-plan de E. Cependant, ce n'est pas une arête de séparation car les sommets Vb1 et Vb2 de B sont également dans ce demi-plan. Cela n'aurait été qu'un bord de séparation si cela n'avait pas été le cas http://www.iassess.com/collision.png

Regardez essentiellement l'image suivante:

Si les deux boîtes entrent en collision, les lignes A et B se chevaucheront.

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

Il y a un bon article sur 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 extrait de code 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 s'il existe un axe de séparation (c'est-à-dire un où les projections illustrées ne se chevauchent pas ). Donc "Un axe de séparation existe" => "Aucun chevauchement". Ce n'est pas une double implication, vous ne pouvez donc pas conclure l'inverse.

La réponse de m_pGladiator est juste et je la préfère. Le test d'axe de séparation est la méthode la plus simple et standard pour détecter le chevauchement de rectangle. 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. Il utilise un produit scalaire pour vérifier si une forme est totalement d'un côté du bord de l'autre. Cette solution pourrait en fait induire des polygones convexes à n arêtes. Cependant, il n'est pas optimisé pour deux rectangles.

le point critique de la réponse de m_pGladiator est que nous devrions vérifier la projection de deux rectangles sur les deux axes (x et y). Si deux projections se chevauchent, alors nous pourrions dire que ces deux rectangles se chevauchent. Donc les commentaires ci-dessus à la réponse de m_pGladiator sont faux.

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

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

on nomme le 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 tourné, il faudra peut-être quelques efforts pour en déterminer la projection sur les axes x et y. Définissez la structure RotatedRect comme suit:

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

la différence est que la largeur 'est maintenant un peu différente: widthA' pour 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 faire référence à un PPT GDC (Game Development Conference 2007) www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt

Dans Cocoa, vous pouvez facilement détecter si le droit selectedArea coupe le rectangle de votre NSView pivoté. Vous n'avez même pas besoin de calculer des polygones, des normales comme ça. Ajoutez simplement ces méthodes à votre sous-classe NSView. Par exemple, l'utilisateur sélectionne une zone sur la supervision de NSView, puis vous appelez la méthode DoesThisRectSelectMe en passant le rect selectedArea. L'API convertRect: fera ce travail. La même astuce fonctionne lorsque vous cliquez sur NSView pour le sélectionner. Dans ce cas, remplacez simplement la méthode hitTest comme ci-dessous. L'API convertPoint: fera ce travail ;-)

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

Vérifiez si l'une des lignes d'un rectangle coupe l'une des lignes de l'autre. L'intersection de segment de ligne naïve est facile à coder.

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

Une solution consiste à utiliser quelque chose appelé un polygone sans ajustement. Ce polygone est calculé à partir des deux polygones (conceptuellement en glissant l'un autour de l'autre) et il définit la zone pour laquelle les polygones se chevauchent compte tenu de leur décalage relatif. Une fois que vous avez ce NFP, il vous suffit de faire un test d'inclusion avec un point donné par le décalage relatif des deux polygones. Ce test d'inclusion est simple et rapide, mais vous devez d'abord créer le NFP.

Recherchez No Fit Polygon sur le Web et voyez si vous pouvez trouver un algorithme pour les polygones convexes (cela devient BEAUCOUP plus complexe si vous avez des polygones concaves). Si vous ne trouvez rien, envoyez-moi un e-mail à 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. Vérifiez que l'un des sommets du rectangle 1 se trouve à l'intérieur du rectangle 2 et vice versa. Chaque fois que vous trouvez un sommet 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 le test ci-dessus n'est pas concluant, trouvez les points d'intersection de chaque ligne d'un 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. Chaque fois qu'un tel point est trouvé, concluez qu'il se croise et arrêtez la recherche.

Si les 2 tests ci-dessus retournent faux, ces 2 rectangles ne se chevauchent pas.

Si vous utilisez Java, toutes les implémentations de l'interface Shape ont une méthode intersects qui prend un rectangle.

Eh 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. Vous pouvez maintenant simplement trouver si l'une des quatre lignes du rectangle A coupe l'une des lignes du rectangle B, ce qui devrait être un simple (rapide) solveur d'équations linéaires.

-Adam

Vous pouvez trouver l'intersection de chaque côté du rectangle incliné avec chaque côté de celui aligné sur l'axe. Pour ce faire, trouvez l'équation de la ligne infinie sur laquelle se trouve chaque côté (c'est-à-dire v1 + t (v2-v1) et v'1 + t '(v'2-v'1) fondamentalement), en trouvant le point où le les lignes se rencontrent en résolvant pour t lorsque ces deux équations sont égales (si elles sont parallèles, vous pouvez tester cela) puis 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 lorsqu'un rectangle recouvre complètement l'autre. Que vous pouvez couvrir en testant si les quatre points de l'un ou l'autre rectangle se trouvent à l'intérieur de l'autre rectangle.

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

Modélisez les 2 rectangles comme des plans décrits par les équations P1 et P2, puis écrivez P1 = P2 et dérivez de là 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, auquel cas vous obtenez 0 = 0. Dans ce cas, vous devrez utiliser un algorithme d'intersection rectangle 2D.

Ensuite, je verrais si cette ligne, qui est dans le plan des deux rectangles, passe par les deux rectangles. Si c'est le cas, alors vous avez une intersection de 2 rectangles, sinon vous ne le faites pas (ou ne devriez pas, j'aurais peut-être manqué un cas d'angle 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 (en les modélisant à l'aide d'équations de ligne), puis je m'assurerais que les points d'intersections sont avec dans gamme.

Ce sont les descriptions mathématiques, 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 d'utiliser le test de l'axe de séparation, consiste à utiliser l'algorithme des nombres d'enroulement (sur les quadrants uniquement - pas la sommation des angles qui est horriblement lente) sur chaque sommet de l'un ou l'autre rectangle (choisi arbitrairement). Si l'un des sommets a un nombre d'enroulement différent de zéro, 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 car il ne nécessite un test de demi-plan que si les arêtes traversent deux quadrants (par opposition à jusqu'à 32 tests utilisant la méthode de l'axe de séparation)

L'algorithme présente l'avantage supplémentaire de pouvoir être utilisé pour tester le chevauchement de n'importe quel polygone (convexe ou concave). Autant que je sache, l'algorithme ne fonctionne que dans l'espace 2D.

Soit il me 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, faites:

    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 implémenté 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 de transformation affine qui convertit des points dans l'espace B en points dans l'espace A. Cela inclut la rotation et la translation simples, la rotation plus la mise à l'échelle et les déformations affines complètes, mais pas les déformations en perspective.

Ce n'est peut-être pas aussi optimal que possible. La vitesse n'était pas une grande préoccupation. Cependant, cela semble fonctionner correctement 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, allez ligne par ligne et vérifiez si les lignes se croisent. C'est le code dans 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 sur: 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)

Ils se chevauchent si et seulement si:

Chevauchement = (max_x1> min_x2) et (max_x2> min_x1) et (max_y1> min_y2) et (max_y2> min_y1)

Vous pouvez également le faire pour les boîtes 3D, en fait cela fonctionne pour n'importe quel nombre de dimensions.

On en a assez dit dans les autres réponses, je vais donc simplement ajouter un pseudocode one-liner:

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