On peut voir deux rectangles qui sont verts tant qu’ils ne sont pas en collision mais deviennent rouge dès qu’ils se croisent.

Principe de cette détection :

On prend le rectangle de gauche. On imagine que chacun de ses bords est prolongé, formant donc une droite (voir image ci-dessous)

Maintenant, au lieu de chercher à savoir quand il y a collision entre les deux rectangles, on va chercher à savoir quand il n’y a PAS collision.

Pour cela, il suffit de réaliser quatre tests :
– Si le deuxième rectangle est complètement à gauche de la ligne brune
– Si le deuxième rectangle est complètement à droite de la ligne noire
– Si le deuxième rectangle est complètement au dessus de la ligne violette
– Si le deuxième rectangle est complètement en dessous de la ligne bleue

Si l’une de ces conditions est vérifiée, alors il n’y a pas collision.

Comment décrire ça sous une formule mathématique ?

Respectivement, chaque condition se calcule de cette façon :
(rect1 = rectangle à gauche et rect2 = rectangle à droite)
– rect2.x + rect2.largeur <= rect1.x
– rect2.x >= rect1.x + rect1.largeur
– rect2.y + rect2.hauteur <= rect1.y
– rect2.y >= rect1.y + rect1.hauteur

En décrivant ces 4 conditions dans un code (Java dans notre cas) et en y ajoutant une interface graphique représentant les deux rectangles, on obtient l’animation en haut de cette page.

Toutefois, ceci ne s’applique que dans le cas où nos deux rectangles sont bien alignés avec les axes. En effet, s’ils ne l’étaient pas, le principe même de cette détection deviendrait obsolète.

Pour remédier à ce problème, il ne faut plus envisager les rectangles comme simplement des rectangles, mais plutôt comme des polygones avec 4 points formant l’équivalent d’un rectangle incliné.

On s’intéresse non plus à des collisions entre rectangles, mais à des collisions entre polygones, ce qui devient tout de suite un poil plus complexe.

On voit donc sur cette animation deux polygones à 4 côtés qui deviennent rouge lorsqu’ils entrent en collision et sinon sont verts. Ce ne sont pas des rectangles inclinés, mais le principe mathématique mis en place derrière cette simulation fonctionne dans tous les cas de polygones, même pas besoin de se limiter à 4 côtés.

Voici le principe mathématique derrière cette collision :

On découpe le calcul en 3 étapes : tout d’abord on cherche à détecter des collisions entre deux segments, puis entre un segment et un polygone, et enfin entre deux polygones.

Segment – Segment :
On décrit tout d’abord le segment sous forme d’une droite (J par exemple) définie par un point d’origine (O) et un vecteur directeur (OC), d’équation J = O + t * OC. Tous les points appartenant à cette droite peuvent être obtenus en faisant varier t.

On considère maintenant une autre droite dont les points pourraient être décris sous cette équation : J = A + u * AB.

On va cherche le point d’intersection de ces deux droites, ce qui reviendrait à résoudre ce système :
J = O + t * OC
J = A + u * AB

Soit, (O + t * OC) = (A + u * AB).

Nous sommes dans un plan, donc on peut comparer une à une les coordonnées suivant x et suivant y, soit :
Ox + t * OCx = Ax + u * ABx
Oy + t * OCy = Ay + u * ABy

En isolant, on obtient
t = – (Ox * ABy – Ax * ABy – ABx * Oy + ABx * Ay) / (OCx * ABy – OCy * ABx)
u = – (-OCx * Oy + OCx * Ay + OCy * Ox – OCy * Ax) / (OCx * ABy – OCy * ABx)

Si le dénominateur (qui est donc le même pour t et pour u, soit (OCx * ABy – OCy * ABx) s’annule, alors les droites sont parallèles donc forcément il n’y aura pas de point de collision.

Au contraire, si ce dernier ne s’annule pas, alors il y a bien un point commun aux deux droites.

Toutefois, on veut savoir si les segments sont en collision, pas les droites. Pour régler ce problème, c’est très simple : on vérifie que t et u soient compris entre 0 et 1 puisque cela signifie que l’on ne sera pas au delà du segment (*1) mais qu’il ne sera pas non plus dans le sens inverse (*0).

On a donc notre réponse : si 0 <= t <= 1 et 0 <= u <= 1, alors il y a collision entre les segments.

TECHNIQUE PLUS SIMPLE A COMPRENDRE :

On commence par calculer le coefficient directeur des deux droites prolongeant les deux segments.
Soit S1 et S2 les deux segments décrits respectivement par les points P1(x1 ; y1) et P2(x2 ; y2) ainsi que P3(x3 ; y3) et P4(x4 ; y4).
a1 = (y2 – y1) / (x2 – x1)
a2 = (y4 – y3) / (x4 – x3)

On cherche ensuite les constantes b1 et b2 pour pouvoir décrire ces droites sous la forme d’une équation du type : y = ax + b.

En transformant cette équation, on obtient b = y – ax. On connaît dans les deux cas y, a et x donc il est très simple de trouver b.
b1 = y1 – a1 * x1
b2 = y3 – a2 * x3

On peut maintenant passer à la détermination de l’intersection :

Si a1 = a2, alors les deux droites sont parallèles et ne se croisent simplement pas.
Sinon, on calcule les coordonnées du point d’intersection qui existe forcément.

Pour trouver ces coordonnées, on résout là aussi un système : on veut que les deux équations de droite soient validées par ce même point.
Soit : a1 * x_intersection + b1 = a2 * x_intersection + b2
On connaît toutes les variables sauf x_intersection, donc le calcul est simple.
a1 * x_intersection – a2 * x_intersection = b2 – b1
x_intersection * (a1 – a2) = b2 – b1
x_intersection = (b2 – b1) / (a1 – a2)

Comme le point d’intersection appartient forcément aux deux droites, on peut trouver son ordonnée en se servant de l’équation de droite que l’on veut.
y_intersection = a1 * x_intersection + b1 = a2 * x_intersection + b2

Dernière partie : pour savoir si le point de coordonnées (x_intersection ; y_intersection) appartient bien aux deux segments et pas juste aux deux droites, on se base sur un principe simple : il faut que x_intersection soit compris entre les x des deux points du premiers segment ainsi que ceux du deuxième segment, et il faut que y_intersection soit compris entre les y des deux points du premier et du deuxième segment.

Si c’est le cas, alors il y a bien intersection. Sinon, non.

On passe maintenant à la collision entre un polygone et un segment.

Polygone – Segment
La base est posée, donc le reste devient très simple, pour vérifier si un polygone est en collision avec un segment, on vérifie que chacun des côtés du polygones (qui est donc un segment) est en collision avec le segment donnée.
On utilise donc les calculs de la collision entre deux segments en adaptant les coordonnées avec celles des côtés du polygone. Si pour l’un de ces côtés il y a collision, alors le polygone est en collision avec le segment.

Polygone – Polygone
De nouveau, on se sert de ce que l’on a réalisé avant. On récupère les différents segments des deux polygones et on les compare avec la fonction de collision entre deux segments.