Déterminez si deux rectangles se chevauchent ?

Question

J'essaie d'écrire un programme C++ qui prend les entrées suivantes de l'utilisateur pour construire des rectangles (entre 2 et 5) : hauteur, largeur, x-pos, y-pos. Tous ces rectangles seront parallèles aux axes x et y, c'est-à-dire que tous leurs bords auront une pente de 0 ou infinie.

J'ai essayé de mettre en œuvre ce qui est mentionné dans le document este mais je n'ai pas beaucoup de chance.

Mon implémentation actuelle fait ce qui suit :

// Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1
// point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on...
// Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2

// rotated edge of point a, rect 1
int rot_x, rot_y;
rot_x = -arrRect1[3];
rot_y = arrRect1[2];
// point on rotated edge
int pnt_x, pnt_y;
pnt_x = arrRect1[2]; 
pnt_y = arrRect1[3];
// test point, a from rect 2
int tst_x, tst_y;
tst_x = arrRect2[0];
tst_y = arrRect2[1];

int value;
value = (rot_x * (tst_x - pnt_x)) + (rot_y * (tst_y - pnt_y));
cout << "Value: " << value;  

Cependant, je ne suis pas tout à fait sûr si (a) j'ai implémenté correctement l'algorithme dont j'ai fait le lien, ou si j'ai fait exactement comment interpréter ceci ?

Des suggestions ?

Answer 1

if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
     RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top ) 

ou, en utilisant des coordonnées cartésiennes

(X1 étant la coordonnée gauche, X2 la coordonnée droite, en augmentant de gauche à droite et Y1 étant la coordonnée supérieure, et Y2 étant la coordonnée inférieure, en augmentant de bas en haut -- si ce n'est pas le cas de votre système de coordonnées [par exemple, la plupart des ordinateurs ont la direction Y inversée], swap les comparaisons ci-dessous ) ...

if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
    RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1) 

Disons que vous avez Rect A, et Rect B. La preuve est faite par contradiction. L'une des quatre conditions suivantes garantit que aucun chevauchement ne peut exister :

• Cond1. Si l'arête gauche de A est à droite de l'arête droite de B, - alors A est totalement à droite de B
• Cond2. Si l'arête droite de A est à gauche de l'arête gauche de B, - alors A est totalement à gauche de B
• Cond3. Si l'arête supérieure de A est en dessous de l'arête inférieure de B, - alors A est totalement sous B
• Cond4. Si l'arête inférieure de A est au-dessus de l'arête supérieure de B, - alors A est totalement au-dessus de B

La condition pour le non-chevauchement est donc

NON-Overlap => Cond1 Or Cond2 Or Cond3 Or Cond4

Par conséquent, une condition suffisante pour le chevauchement est l'inverse.

Overlap => NOT (Cond1 Or Cond2 Or Cond3 Or Cond4)

La loi de Morgan dit
Not (A or B or C or D) est la même chose que Not A And Not B And Not C And Not D
donc en utilisant De Morgan, on a

Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4

Ceci est équivalent à :

• Bord gauche de A à gauche du bord droit de B, [ RectA.Left < RectB.Right ], et
• Le bord droit de A à droite du bord gauche de B, [ RectA.Right > RectB.Left ], et
• Le haut de A au-dessus du bas de B, [ RectA.Top > RectB.Bottom ], et
• Le bas de A en dessous du haut de B [ RectA.Bottom < RectB.Top ]

Note 1 : Il est assez évident que ce même principe peut être étendu à un nombre quelconque de dimensions.
Note 2 : Il devrait également être assez évident de compter les chevauchements d'un seul pixel, en changeant la valeur de l'option < et/ou le > sur cette frontière à une <= ou un >= .
Note 3 : Cette réponse, lorsqu'elle utilise les coordonnées cartésiennes (X, Y) est basée sur les coordonnées cartésiennes algébriques standard (x augmente de gauche à droite, et Y augmente de bas en haut). Évidemment, lorsqu'un système informatique pourrait mécaniser les coordonnées cartésiennes différemment, (par exemple, en augmentant Y de haut en bas, ou X de droite à gauche), la syntaxe devra être ajustée en conséquence/

Answer 2

struct rect
{
    int x;
    int y;
    int width;
    int height;
};

bool valueInRange(int value, int min, int max)
{ return (value >= min) && (value <= max); }

bool rectOverlap(rect A, rect B)
{
    bool xOverlap = valueInRange(A.x, B.x, B.x + B.width) ||
                    valueInRange(B.x, A.x, A.x + A.width);

    bool yOverlap = valueInRange(A.y, B.y, B.y + B.height) ||
                    valueInRange(B.y, A.y, A.y + A.height);

    return xOverlap && yOverlap;
}

Answer 3

struct Rect
{
    Rect(int x1, int x2, int y1, int y2)
    : x1(x1), x2(x2), y1(y1), y2(y2)
    {
        assert(x1 < x2);
        assert(y1 < y2);
    }

    int x1, x2, y1, y2;
};

bool
overlap(const Rect &r1, const Rect &r2)
{
    // The rectangles don't overlap if
    // one rectangle's minimum in some dimension 
    // is greater than the other's maximum in
    // that dimension.

    bool noOverlap = r1.x1 > r2.x2 ||
                     r2.x1 > r1.x2 ||
                     r1.y1 > r2.y2 ||
                     r2.y1 > r1.y2;

    return !noOverlap;
}

Answer 4

Il est plus facile de vérifier si un rectangle est complètement à l'extérieur de l'autre, donc si c'est soit

sur la gauche...

(r1.x + r1.width < r2.x)

ou sur la droite...

(r1.x > r2.x + r2.width)

ou sur le dessus...

(r1.y + r1.height < r2.y)

ou sur le fond...

(r1.y > r2.y + r2.height)

du second rectangle, il ne peut pas entrer en collision avec lui. Ainsi, pour obtenir une fonction qui renvoie un booléen indiquant si les rectangles entrent en collision, il suffit de combiner les conditions par des OU logiques et de nier le résultat :

function checkOverlap(r1, r2) : Boolean
{ 
    return !(r1.x + r1.width < r2.x || r1.y + r1.height < r2.y || r1.x > r2.x + r2.width || r1.y > r2.y + r2.height);
}

Pour obtenir déjà un résultat positif en touchant seulement, on peut changer les "<" et ">" par "<=" et ">=".

Answer 5

Voici comment cela se passe dans l'API Java :

public boolean intersects(Rectangle r) {
    int tw = this.width;
    int th = this.height;
    int rw = r.width;
    int rh = r.height;
    if (rw <= 0 || rh <= 0 || tw <= 0 || th <= 0) {
        return false;
    }
    int tx = this.x;
    int ty = this.y;
    int rx = r.x;
    int ry = r.y;
    rw += rx;
    rh += ry;
    tw += tx;
    th += ty;
    //      overflow || intersect
    return ((rw < rx || rw > tx) &&
            (rh < ry || rh > ty) &&
            (tw < tx || tw > rx) &&
            (th < ty || th > ry));
}