Discussion :

[Arnaud F.]

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.

[pseudocode]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
      +------+
      |      |
+-----+-+    |
|     | |    |
|    2+-+----+
|       |
+-------+
1

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

[Arnaud F.]

C'est bien ça

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

[Invité]

(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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Arnaud F.]

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

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Ca fonctionne à merveille

[pseudocode]

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 java :

Sélectionner tout - Visualiser dans une fenêtre à part

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;