L'algorithme AABB (pour les détecteurs de collision)

Bonjour à tous, et merci d'avance pour votre aide :p

Il se trouve que je dois coder un détecteur de collision en Javascript. En effet, je construit des graphes en SVG (mode vectoriel), et lorsque je clique sur un point du graphe, une infobulle s'affiche avec des informations complémentaires sur le point (l'infobulle s'affiche grâce au javascript, bien sûr :D ).
Et donc, mon problème est que quand je clique sur 2 points côte à côte, les infobulles se chevauchent... J'aimerais que ma fonction detecteurDeCollision(); me permette de décaller les infobulles vers le haut ou le bas, afin qu'elles ne se touchent pas..

Cependant, je ne sais pas comment faire un tel code.. mais en cherchant sur le net, j'ai cru comprendre qu'il fallait utiliser l'algorithme AABB...

Quelqu'un peut-il m'expliquer cet algorithme ? (et s'il sait résoudre mon problème, le faire en passant :lol: )

Merci beaucoup !!!

En fait, AABB, c'est pour Axis Aligned Bounding Box, ça n'est pas un algorithme mais une structure englobante relativement utile pour (pré)tester des intersections facilement.

Généralement, on représente une boite par deux points : min et max qui sont les extrémités haut gauche et bas droite de ta boite (tu peux prendre une autre convention ça ne pose pas de problème).

Ensuite, pour tester l'intersection, la méthode la plus simple (et sans doute l'une des plus efficace) est d'effectuer des cas.

Ainsi, si tu as deux boites B1 et B2 tester l'intersection se fait de la manière suivante :
Code:

1 2 3 4 5 6 SI B1.max.x < B2.min.x ALORS RENVOYER Faux ; (B1 est trop à gauche de B2) SINON SI B2.max.x < B1.min.x ALORS RENVOYER Faux ; (B2 est trop à gauche de B1) ...
Ca devient vite très compliqué (parce qu'il y a enormément de cas). Une autre solution consiste à tester l'appartenance des points extrêmes d'une boite dans l'autre.

Les quatre points d'une boite (disons B1) sont donnés par :

P1 := (min.x , min.y )
P2 := (max.x , min.y )
P3 := (max.x , max.y )
P4 := (min.x , max.y )

Tester lintersection entre deux boîtes devient alors :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Intersection( B1 , B2 ) P1 := B1.min P2 := (B1.max.x , B1.min.y ) P3 := B1.max P4 := (B1.min.x , B1.max.y ) POUR Pi dans (P1,P2,P3,P4) FAIRE SI Appartient( B2 , Pi ) ALORS RENVOYER VRAI FIN SI FIN POUR RENVOYER FAUX
La fonction appartient est aussi relativement simple :
Code:

1 2 3 4 5 6 7 8 9 Appartient( B , P ) SI B.min.x < P.x < B.max.x ET B.min.y < P.y < B.max.y ALORS RENVOYER VRAI FIN SI RENVOYER FAUX
Ensuite, une fois que tu as ceci, tu as peut-être besoin de calculer plus, notamment, s'il y a une intersection, il faudrait savoir de combien. Ce que tu peux faire, c'est dès qu'il y a une intersection, tu stockes le point qui est dans l'autre boite, et tu calcules les distances avec les cotés, Ensuite il suffit de déplacer ta boite par cette distance pour qu'elle ne se chevauchent plus.

Mais cela peut vite poser des problèmes lorsque tu as plus de deux infos bulles (lorsque tu vas en déplacer une, tu vas peut-être la faire se chevaucher avec une autre boite, en la redéplaçant elle risque se chevaucher encore ce qui peut conduire à une boucle infinie), la solution de facilité consiste à n'afficher que deux infos bulles, simple et efficace. Une autre solution, consiste à choisir de déplacer toujours dans le même sens (tu déplace toujours à gauche en commençant par la boite la plus à droite), autre solution, tu prends la médiane de tes boites sur l'axe le plus grand (l'axe le plus grand t'es donné par la plus grande distance entre les boites les plus éloignés sur l'axe considéré), une fois la médiane, tu déplaces tes boites suivant cette médiane, c'est un peu plus compliqué mais ça évite de déplacer tout à droite, ça déplace en fonction de la médiane (ce qui aère le tout). Dernière solution, tu déplaces par rapport à la dernière boite crée (celle où tu as cliqué pour la dernière fois).

Merci beaucoup pour ta réponse claire :p