Détecter l'intersection entre deux rectangles

Bonjour,

je souhaiterais savoir quel est l'algorithme à appliquer le plus efficace pour déterminer si deux rectangles s'intersectent ?

Je dispose du point inférieur gauche ainsi que la dimension de ce dernier...

Merci à qui peut me fournir un élément de piste.

Je suppose que les rectangles sont alignés par rapport aux axes... :P

Code:

---

1 2 3 4 5 6 7 8

+------+ | | +-----+-+ | | | | | | 2+-+----+ | | +-------+ 1

---

(x1 < x2 < x1+largeur1) ET (y1 < y2 < y1+hauteur1)

C'est bien ça :)

[edit] Je teste demain et vous tiens au courant .

:merci:

Citation:

---

Envoyé par pseudocode

(x1 < x2 < x1+largeur1) ET (y1 < y2 < y1+hauteur1)

---

Euh, ca ne va marcher *que* dans ce cas précis, ca...

Dans celui là, ca n'ira pas...

Code:

---

1 2 3 4 5 6 7 8

+-------+ | | | +-+----+ | | | | +-----+-+ 1 | | 2+-+----+

---

Une méthode générale c'est de calculer (dans ton système d'axes)

maxgauche=max(x1,x2)
mindroit=min(x1+largeur1,x2+largeur2)
maxbas=max(y1,y2)
minhaut=min(y1+hauteur1,y2+hauteur2)

tes rectangles ont une intersection si

maxgauche<mindroit
ET
maxbas<minhaut

Pour gagner un peu de temps, dans la pratique, tu vas sans doute tester la première partie de la condition avant d'évaluer les termes de la seconde.

Francois

Citation:

---

Envoyé par fcharton

Euh, ca ne va marcher *que* dans ce cas précis, ca...

Dans celui là, ca n'ira pas...

Code:

---

1 2 3 4 5 6 7 8

+-------+ | | | +-+----+ | | | | +-----+-+ 1 | | 2+-+----+

---

Une méthode générale c'est de calculer (dans ton système d'axes)

maxgauche=max(x1,x2)
mindroit=min(x1+largeur1,x2+largeur2)
maxbas=max(y1,y2)
minhaut=min(y1+hauteur1,y2+hauteur2)

tes rectangles ont une intersection si

maxgauche<mindroit
ET
maxbas<minhaut

Pour gagner un peu de temps, dans la pratique, tu vas sans doute tester la première partie de la condition avant d'évaluer les termes de la seconde.

Francois

---

:applo:


Ca fonctionne à merveille :)

:merci:

Citation:

---

Envoyé par fcharton

Euh, ca ne va marcher *que* dans ce cas précis, ca...

---

Oui, effectivement. Je voulais juste avoir confirmation que les rectangles étaient alignés sur les axes (AABB = Axis-Aligned Bounding Box).

Auquel cas, l'algo habituel consiste à projeter les bounding-box sur les axes et tester si les segments se recouvrent (ca marche en dimension 2, 3, ...):

Code:

---

1 2 3 4 5 6 7 8

// recouvrement axe horizontal boolean hoverlap = (x1<x2+w2) && (x2<x1+w1);   // recouvrement axe vertical boolean voverlap = (y1<y2+h2) && (y2<y1+h1);   // recouvrement final boolean overlap = hoverlap && voverlap;

---