Théorie des collisions : Formes complexes

Sans reprendre la définition exacte d'un polygone (que vous trouverez en lien à la fin de ce paragraphe), nous allons définir ce qu'est un polygone convexe.
Pour cela, nous allons d'abord présenter les polygones non convexes :

Les polygones sont en rouge. Si on regarde les trois polygones de gauche, on peut constater qu'à chaque fois, au moins une diagonale est hors du polygone. Les diagonales sont en bleu. Je rappelle que les diagonales d'un polygone sont des segments qui relient deux sommets quelconques du polygone, mais qui ne sont pas des côtés.

La quatrième figure est un cas tordu : un polygone croisé, c'est-à-dire qu'il y a intersection entre au moins deux de ses côtés. Nous allons vite oublier ce quatrième cas.

Les polygones ci-dessus sont donc convexes. Ils ne sont pas croisés, et il n'existe pas de diagonales à l'extérieur.

Pour en savoir plus sur les polygones, et leur classification, consultez Wikipédia.

Un polygone non convexe peut être transformé en un ensemble de polygones convexes. Si on regarde la figure ci-dessus sur les polygones non convexes, j'ai ajouté des traits verts qui découpent les polygones en plusieurs triangles. Comme chaque triangle est convexe, on transforme ainsi le polygone non convexe en plusieurs polygones convexes.

Vérifier si un point est dans ce polygone non convexe reviendra à vérifier s'il est dans l'un des triangles qui le composent.

Un algorithme pour transformer le polygone non convexe en triangles peut être le suivant :

1. On parcourt les points du polygone non convexe ;
2. Pour un point i, on considère son voisin précédent et son voisin suivant. Si le triangle formé par ces trois points est dans le polygone, alors on ajoute le triangle à la liste, et on considère le polygone non convexe restant comme étant le même polygone auquel on retire le sommet i (on relie donc i-1 et i+1) ;
3. etc.

C'est un algorithme glouton, et le polygone restant finit par être un triangle.

On peut tester l'appartenance du triangle en regardant si l'angle du point i est aigu ou obtus par rapport au sens de parcours.

Pour cette méthode, nous considérons un polygone convexe (s'il n'est pas convexe, regardez ci-dessus comment faire pour le décomposer en plusieurs polygones convexes).

Voici de nouveau mes polygones convexes. Cette fois j'ai rajouté des flèches. En effet, je vais parcourir mes points dans l'ordre, comme si je partais d'un point, et que j'avançais en voiture sur le tour de mon polygone. L'idée est de choisir le bon sens de façon à ce que l'intérieur du polygone soit à gauche.

Voici l'idée :

Il va donc falloir, pour chaque côté orienté, voir si le point testé est à gauche ou non. S'il est, ne serait ce qu'une fois, à droite, alors le point n'est pas à l'intérieur.

Il ne reste plus qu'a savoir si un point est à gauche ou pas. Sur la figure ci-dessus, il y a un segment [AB]. On va de A vers B. Le Point P est-il à gauche ?

Mathématiquement, un simple calcul de déterminant suffit.
Nous avons les points A, B, P.
Soit D le vecteur AB :

Soit T le vecteur AP :

Soit d le déterminant de D,T. Le déterminant se calcule simplement ainsi (règle du gamma) :

Pour le code, nous considérons le polygone comme un tableau de points, de taille nbp. Soit les structures suivantes :

struct Point
{
  float x,y;
};

struct Vecteur
{
  float x,y;
};

Nous obtenons une fonction de collision comme ceci :

bool Collision(Point tab[],int nbp,Point P)
{
  int i;
  for(i=0;i<nbp;i++)
  {
     Point A = tab[i];
     Point B;
     if (i==nbp-1)  // si c'est le dernier point, on relie au premier
         B = tab[0];
     else           // sinon on relie au suivant.
         B = tab[i+1];
     Vecteur D,T;
     D.x = B.x - A.x;
     D.y = B.y - A.y;
     T.x = P.x - A.x;
     T.y = P.y - A.y;
     float d = D.x*T.y - D.y*T.x;
     if (d<0)
        return false;  // un point à droite et on arrête tout.
  }
  return true;  // si on sort du for, c'est qu'aucun point n'est à gauche, donc c'est bon.
}

À vous de voir si vous voulez qu'un point sur AB soit considéré comme dedans ou dehors, en mettant if (d<0) ou if (d<=0). Cependant, ça reste un cas limite.

Pour cet algo, nous allons chercher un point I qui sera en dehors du polygone.
Comment être sûr qu'un point est en dehors ? Il suffit de le prendre très loin.
Par exemple, on peut poser I(100000,0).

Nous partons du principe que notre polygone est sagement dans notre monde, et, notre monde étant par exemple compris entre -1000 et +1000, nous sommes sûr que le point I(100000,0) est hors du monde, et hors du polygone.

Regardons le schéma ci-dessus. Des polygones, et des segments verts dont une extrémité est un des points P, Q, R, S, T, et l'autre extrémité est… loin ! (Le point I lointain.)

Voici la règle :

Vérifions tout ça avec les exemples ci-dessus :

• pour P, on coupe une fois : 1 est impair, P est à l'intérieur ;
• pour Q, idem ;
• pour R, on coupe deux fois. 2 est pair, on est à l'extérieur ;
• pour S, on coupe 5 fois, impair, on est dedans ;
• pour T, on coupe 4 fois, pair, on est dehors.

Cet algo revient donc à savoir combien de fois on coupe, donc il se base sur un algo d'intersection de segments.

Un segment est inscrit dans une droite. Nous allons donc considérer l'équation paramétrique d'une droite. Ceci est vu, me semble-t-il, à la fin du lycée.

Une droite est définie par un point d'origine O, et un vecteur directeur : kitxmlcodeinlinelatexdvp\vec{D}finkitxmlcodeinlinelatexdvp
En faisant varier t, on obtient tous les points de la droite.

Si on s'intéresse à un segment [AB], posons astucieusement :

Nous aurons donc les règles suivantes :

• si t = 0, alors P(t) = A ;
• si t= 1, alors P(t) = B ;
• si t appartient au segment [0..1] alors P(t) appartient au segment [AB], sinon, il n'est pas sur le segment.

Nous cherchons l'intersection de 2 segments [AB] et [IP]. Soit J, le point d'intersection. Nous cherchons donc :

Où t et u seront les paramètres du point J sur chacune des deux droites (AB) et (IP).
Ce qui nous donne :

Posons :

Posons :

Nous travaillons dans le plan, donc chaque point et chaque vecteur a une coordonnée x,y.
Ceci nous permet de poser le système suivant :

Nous résolvons le système pour trouver t et u. Nous obtenons :

Si le dénominateur (qui est le même pour t et u) s'annule, cela veut dire que les droites (AB) et (IJ) sont parallèles : donc J n'existe pas (ou alors l'intersection est l'ensemble de la droite).

Sinon, cela veut dire qu'il existe un point J, intersection des droites (AB) et (IJ). Mais nous, nous cherchons l'intersection des segments.
Il faut donc regarder si 0 <= t < 1 et 0 <= u < 1. Dans ce cas seulement, l'intersection se produit au niveau des segments.

Nous considèrerons qu'un point est sur le segment si t (ou u) vaut 0, mais pas s'il vaut 1. En effet, au niveau des sommets du polygone, si nous ne voulons considérer qu'un seul point d'intersection, nous dirons qu'il est sur un seul des segments, celui de paramètre 0.

Nous nous appuierons sur la fonction d'intersection de segments suivante :

int intersectsegment(Point A,Point B,Point I,Point P)
{
   Vecteur D,E;
   D.x = B.x - A.x;
   D.y = B.y - A.y;
   E.x = P.x - I.x;
   E.y = P.y - I.y;
   double denom = D.x*E.y - D.y*E.x;
   if (denom==0)
       return -1;   // erreur, cas limite
   t = - (A.x*E.y-I.x*E.y-E.x*A.y+E.x*I.y) / denom;
   if (t<0 || t>=1)
      return 0;
   u = - (-D.x*A.y+D.x*I.y+D.y*A.x-D.y*I.x) / denom;
   if (u<0 || u>=1)
      return 0;
   return 1;
}

Vous pouvez constater que je retourne 0 si les segments ne se touchent pas, 1 s'ils se touchent, et -1 dans les cas limites. Nous en aurons besoin pour la suite.

Nous en arrivons à la fonction de collision. Nous allons prendre un point I au hasard, mais loin. Puis nous allons calculer le nombre d'intersections avec chacun des segments. Si nous avons un nombre impair d'intersections, alors le point sera dedans, sinon dehors.
Nous ajoutons que si on tombe sur un cas limite (une droite parallèle à un des côtés), nous choisirons à nouveau un autre I.

bool Collision(Point tab[],int nbp,Point P)
{
  int i;
  Point I;
  I.x = 10000 + rand()%100;   // 10000 + un nombre aléatoire entre 0 et 99
  I.y = 10000 + rand()%100;
  int nbintersections = 0;
  for(i=0;i<nbp;i++)
  {
     Point A = tab[i];
     Point B;
     if (i==nbp-1)  // si c'est le dernier point, on relie au premier
         B = tab[0];
     else           // sinon on relie au suivant.
         B = tab[i+1];
     int iseg = intersectsegment(A,B,I,P);
     if (iseg == -1)
         return Collision(tab,nbp,P);  // cas limite, on relance la fonction.
     nbintersections+=iseg;
  }
  if (nbintersections%2==1)  // nbintersections est-il impair ?
     return true;
  else
     return false;
}

Un petit peu de trigonométrie, considérons le triangle ACI rectangle en I. Le point I est inconnu, mais A et C sont connus.
Nous cherchons la distance CI.

Nous connaissons la distance AC, c'est la norme du vecteur kitxmlcodeinlinelatexdvp\vec{AC}finkitxmlcodeinlinelatexdvp

Je rappelle que la norme d'un vecteur v est sa longueur, et qu'elle se calcule ainsi :

Dans notre triangle ACI, nous pouvons écrire que : kitxmlcodeinlinelatexdvpsin(a) = \frac{CI}{AC}finkitxmlcodeinlinelatexdvp, donc que
kitxmlcodeinlinelatexdvpCI = AC * sin(a) (1)finkitxmlcodeinlinelatexdvp (1)

avec a l'angle formé entre les deux vecteurs kitxmlcodeinlinelatexdvp\vec{AI}finkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvp\vec{AC}finkitxmlcodeinlinelatexdvp

Ce qui nous embête maintenant, c'est cet angle, qu'il faudrait calculer. Soit on le calcule, soit on le vire. Une astuce est d'invoquer le produit vectoriel des deux vecteurs. Une des formules du produit vectoriel est la suivante :

donc : kitxmlcodeinlinelatexdvp||\vec{u}\wedge\vec{AC}|| = ||\vec{u}||*AC*sin(a)finkitxmlcodeinlinelatexdvp (2)

En combinant (1) et (2), nous obtenons :

Nous obtenons donc : kitxmlcodeinlinelatexdvpCI = \frac{||\vec{u}\wedge\vec{AC}||}{||\vec{u}||}finkitxmlcodeinlinelatexdvp(3)

Nous nous sommes débarrassé de l'angle. Nous n'avons plus qu'un produit vectoriel et deux normes à calculer. Un produit vectoriel considère des vecteurs dans l'espace. Cependant, nous sommes dans le plan, donc c'est comme si nous étions dans l'espace, mais que les coordonnées z des vecteurs étaient à 0.
À partir de la, la norme d'un produit vectoriel sera un vecteur kitxmlcodeinlinelatexdvp\vec{v}finkitxmlcodeinlinelatexdvpdont les composantes x et y seront nulles, et seule sa composante z sera non nulle. Prendre la norme de ce vecteur reviendra à prendre la valeur absolue de cette composante z, comme ceci :

et donc, dans notre cas :

Il suffira de diviser cette valeur absolue par la norme de u pour obtenir CI.

Et il nous suffira donc de savoir si CI est plus grand que le rayon ou non… Voici le code pour tester si le cercle C touche la droite AB :

bool CollisionDroite(Point A,Point B,Cercle C)
{
   Vecteur u;
   u.x = B.x - A.x;
   u.y = B.y - A.y;
   Vecteur AC;
   AC.x = C.x - A.x;
   AC.y = C.y - A.y;
   float numerateur = u.x*AC.y - u.y*AC.x;   // norme du vecteur v
   if (numerateur <0)
      numerateur = -numerateur ;   // valeur absolue ; si c'est négatif, on prend l'opposé.
   float denominateur = sqrt(u.x*u.x + u.y*u.y);  // norme de u
   float CI = numerateur / denominateur;
   if (CI<C.rayon)
      return true;
   else
      return false;
}

Pour le test d'un point dans un cercle, je vous renvoie au début de ce tutoriel.

Alors l'idée est de savoir si I est entre A et B.

Pour cela, nous allons utiliser le produit scalaire, rapide, et qui a des propriétés bien sympathiques. Regardez le dessin de gauche.
J'ai les points A,B qui me donnent un vecteur \kitxmlcodeinlinelatexdvpvec{AB}finkitxmlcodeinlinelatexdvp, qui part de A.
Au point A, on imagine une frontière verte, orthogonale au vecteur. Si on appelle P l'un des points (rouge ou bleu), le signe du produit scalaire kitxmlcodeinlinelatexdvp\vec{AB}finkitxmlcodeinlinelatexdvp. kitxmlcodeinlinelatexdvp\vec{AP}finkitxmlcodeinlinelatexdvp nous permet de savoir de quel côté de la ligne verte on est. Si le produit scalaire est positif, on est du côté de B, sinon, on est de l'autre côté.

Maintenant, nous voulons savoir si I est entre A et B. Regardons le dessin de droite ci-dessus. Comme I est le projeté orthogonal de C sur la droite, alors pour savoir si I est entre A et B, il suffit de regarder si C est dans la bande verte ou non. Pour cela, on applique deux produits scalaires :

Si pscal1>0 ET pscal2>0, alors C est dans la bande verte, et donc I entre A et B.

Cela nous donne la fonction suivante :

bool CollisionSegment(Point A,Point B,Cercle C)
{
   if (CollisionDroite(A,B,C) == false)
     return false;  // si on ne touche pas la droite, on ne touchera jamais le segment
   Vecteur AB,AC,BC;
   AB.x = B.x - A.x;
   AB.y = B.y - A.y;
   AC.x = C.x - A.x;
   AC.y = C.y - A.y;
   BC.x = C.x - B.x;
   BC.y = C.y - B.y;
   float pscal1 = AB.x*AC.x + AB.y*AC.y;  // produit scalaire
   float pscal2 = (-AB.x)*BC.x + (-AB.y)*BC.y;  // produit scalaire
   if (pscal1>=0 && pscal2>=0)
      return true;   // I entre A et B, ok.
   // dernière possibilité, A ou B dans le cercle
   if (CollisionPointCercle(A,C))
     return true;
   if (CollisionPointCercle(B,C))
     return true;
   return false;
}

Actuellement, nous avons une information sur l'entrée en collision ou non. Mais il peut être utile de savoir à quel endroit on touche. On touche au point I bien entendu, mais comment calculer I ?

Nous avons vu que notre droite a pour équation : kitxmlcodeinlinelatexdvpP(t) = A + t*\vec{u} (avec \vec{u} = \vec{AB}finkitxmlcodeinlinelatexdvp dans notre cas) I appartient à la droite, donc il existe t_i tel que : kitxmlcodeinlinelatexdvpI = A + t_i*\vec{u}finkitxmlcodeinlinelatexdvp (5)

Si on regarde le triangle AIC rectangle en I, de nouveau, avec un peu de trigonométrie, on trouve :

, avec a angle au sommet A.

kitxmlcodeinlinelatexdvpAI = AC*cos(a)finkitxmlcodeinlinelatexdvp (6)

Ici, il est astucieux de considérer la formule suivante du produit scalaire.

kitxmlcodeinlinelatexdvp\vec{u}.\vec{AC} = ||\vec{u}||*||\vec{AC}||*cos(a)finkitxmlcodeinlinelatexdvp (7)
Sachant que kitxmlcodeinlinelatexdvp||\vec{AC}|| = ACfinkitxmlcodeinlinelatexdvp

En utilisant (6) et (7), on trouve :

Si on veut t_i, il faut diviser par la norme de u. Cela donne :

Cela nous épargnera, au niveau optimisation, de calculer la racine carrée de la norme de u puisqu'on la considère au carré.

Nous obtenons la formule finale suivante :

Au niveau du code nous avons donc une droite (AB), et un point C à projeter :

Point ProjectionI(Point A,Point B,Point C)
{
  Vecteur u,AC;
  u.x = B.x - A.x; 
  u.y = B.y - A.y; 
  AC.x = C.x - A.x;
  AC.y = C.y - A.y;
  float ti = (u.x*AC.x + u.y*AC.y)/(u.x*u.x + u.y*u.y);
  Point I;
  I.x = A.x + ti*u.x;
  I.y = A.y + ti*u.y;
  return I;
}

La normale est le vecteur orthogonal à la tangente qui « regarde » le point C. Avoir la normale au point d'impact permet de calculer un rebond par exemple.
Sur une droite, la normale est constante en tout point.

On utilise souvent le produit vectoriel pour calculer des normales. Ici, on fera pareil, en utilisant deux produits vectoriels, un pour calculer un vecteur v orthogonal à notre plan kitxmlcodeinlinelatexdvp\vec{v} = \vec{u}\wedge\vec{AC}finkitxmlcodeinlinelatexdvp , puis on refera un autre produit vectoriel pour trouver notre normale n kitxmlcodeinlinelatexdvp\vec{n} = \vec{v}\wedge\vec{u}finkitxmlcodeinlinelatexdvp.
L'avantage de cette méthode, c'est que la normale « regardera » toujours C, qu'il soit d'un côté ou de l'autre de la droite.
Cet algorithme fonctionne aussi dans l'espace, pour trouver le vecteur kitxmlcodeinlinelatexdvp\vec{IC}finkitxmlcodeinlinelatexdvp.

Si on applique les formules des deux produits vectoriels, on trouve simplement, pour la normale :

Il est d'usage qu'une normale soit normalisée… autrement dit que sa norme (sa longueur) soit 1. Il suffit de diviser N par sa norme :

Au niveau du code, cela nous donne la chose suivante :

Vecteur GetNormale(Point A,Point B,Point C)
{
  Vecteur AC,u,N;
  u.x = B.x - A.x;  
  u.y = B.y - A.y;
  AC.x = C.x - A.x;  
  AC.y = C.y - A.y;
  float parenthesis = u.x*AC.y-u.y*AC.x;  // calcul une fois pour les deux
  N.x = -u.y*(parenthesis);
  N.y = u.x*(parenthesis);
  // normalisons
  float norme = sqrt(N.x*N.x + N.y*N.y);
  N.x/=norme;
  N.y/=norme;
  return N;
}

Voici une utilisation pratique de tout ça : un calcul de rebond. Un jeu de flipper par exemple : votre balle arrive sur un mur en biais, vous voulez calculer le rebond : dans quel sens va-t-elle repartir ?

Regardons le dessin ci-dessus. La balle (qu'on ne voit pas) arrive avec une trajectoire suivant le vecteur v rouge (de A vers I).
Après rebond, il faudra qu'elle reparte avec la trajectoire v_2 violet, de I vers B.

Nous calculons grâce à la fonction de collision si on touche la droite. Ensuite, si on touche, il faut faire rebondir. Pour cela, on aura besoin de la normale (en bleu) au segment (qu'on calculera comme vu au-dessus).

Le vecteur v_2 est tel que la normale soit la bissectrice des vecteurs v et v_2 au point I. Sur le dessin, j'ai mis les angles égaux.

J est le projeté orthogonal de A sur la droite faite par le point I et la normale.
Le vecteur v_3 est le même que le vecteur v_2, en partant de A au lieu de I, mais c'est le même vecteur.
Géométriquement, on peut démontrer que J est le milieu de [IK], et J est aussi le milieu de [AB].

Le vecteur kitxmlcodeinlinelatexdvp\vec{N}finkitxmlcodeinlinelatexdvp est normalisé : rappelez-vous, les normales sont normalisées.

La longueur IJ (qu'on pourra aussi appeler d) s'obtient à partir d'un produit scalaire :

kitxmlcodeinlinelatexdvpd = IJ = \vec{IA}.\vec{N} = - \vec{AI}.\vec{N}finkitxmlcodeinlinelatexdvp (7)
Je considère IA et non AI pour avoir une longueur positive.

On veut calculer le vecteur kitxmlcodeinlinelatexdvp\vec{IB}finkitxmlcodeinlinelatexdvp, donc kitxmlcodeinlinelatexdvp\vec{AK}finkitxmlcodeinlinelatexdvp
Géométriquement :

On simplifie :

En injectant (7), je trouve :

Enfin, un petit code pour terminer cette grande partie. On donne le vecteur kitxmlcodeinlinelatexdvpv (= \vec{AI})finkitxmlcodeinlinelatexdvp incident, et la normale, et on calculera le vecteur de rebond :

Vecteur CalculerVecteurV2(Vecteur v,Vecteur N)
{
  Vecteur v2;
  float pscal = (v.x*N.x +  v.y*N.y);
  v2.x = v.x -2*pscal*N.x;
  v2.y = v.y -2*pscal*N.y;
  return v2;
}

Rappelez-vous le calcul du déterminant de 2 vecteurs qui me dit si un point est « à gauche » ou « à droite » d'une droite. Si on considère le vecteur AB, et le vecteur AP, le déterminant de kitxmlcodeinlinelatexdvpd = \det(\vec{AB},\vec{AP})finkitxmlcodeinlinelatexdvp me dit si mon point P est à gauche ou à droite du mur (en considérant le mur comme « démarrant » au point A et « regardant » le point B.

• Si (d > 0), P est à gauche.
• Si (d < 0), P est à droite.
• Si (d == 0), P est dans le mur : on va éviter ce cas-là.

On va partir du principe que P n'est jamais dans le mur. En effet, dans un jeu comme Doom, on commence hors d'un mur, et quand on évolue, on ne permet pas d'aller « dans » le mur. On permet d'aller proche, mais jamais dedans. Donc on n'est jamais « dans » un mur. Donc d n'est jamais égal à 0.

Maintenant, on calcule le déterminant kitxmlcodeinlinelatexdvpd_P = \det(\vec{AB},\vec{AP})finkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpd_O = \det(\vec{AB},\vec{AO})finkitxmlcodeinlinelatexdvp pour savoir de quel côté sont P et O.

• Si d_P > 0 et d_O > 0 alors ils sont du même côté ;
• Si d_P < 0 et d_O < 0 alors ils sont du même coté ;
• Si d_P > 0 et d_O < 0 alors ils ne sont pas du même côté ;
• Si d_P < 0 et d_O > 0 alors ils ne sont pas du même côté.

ça nous fait quatre conditions à voir, sauf si on pense aux propriétés de la multiplication, qui vont nous simplifier le travail :

• Si d_P * d_O > 0 alors ils sont du même côté ;
• Si d_P * d_O < 0 alors ils ne sont pas du même côté.

Au niveau du code, cela donne ceci :

bool CollisionDroiteSeg(Point A,Point B,Point O,Point P) 
{ 
  Vecteur AO,AP,AB; 
  AB.x = B.x - A.x; 
  AB.y = B.y - A.y; 
  AP.x = P.x - A.x; 
  AP.y = P.y - A.y; 
  AO.x = O.x - A.x; 
  AO.y = O.y - A.y; 
  if ((AB.x*AP.y - AB.y*AP.x)*(AB.x*AO.y - AB.y*AO.x)<0) 
     return true; 
  else 
     return false; 
}

Une idée simple pour calculer la collision entre segment et segment est de se servir deux fois de la formule ci-dessus.
Si vous avez quatre points ABOP, que vous voulez calculer la collision entre le segment [AB] et le segment [OP], il suffit de calculer la collision entre la droite (AB) et le segment [OP], puis la collision entre la droite (OP) et le segment [AB]. Si les deux collisions sont valides, alors les segments se touchent.

Au niveau du code, cela donne :

bool CollisionSegSeg(Point A,Point B,Point O,Point P) 
{ 
  if (CollisionDroiteSeg(A,B,O,P)==false) 
     return false;  // inutile d'aller plus loin si le segment [OP] ne touche pas la droite (AB) 
  if (CollisionDroiteSeg(O,P,A,B)==false) 
     return false; 
  return true; 
}

Cette méthode est plus complexe que la précédente, mais permettra de calculer le point d'intersection.
Grâce au calcul segment/droite, on sait que les points O et P sont de part et d'autre de la droite (AB), mais il y a collision segment/segment seulement si le point d'intersection I est entre A et B. Sinon, le personnage passe à côté du mur : il n'y a pas collision.

Nous allons donc voir si l'intersection est entre A et B ou non. De cette condition dépendra notre collision.

Posons la forme paramétrique de la droite (AB) :

Avec cette forme, nous pouvons affirmer que I est entre A et B si et seulement si 0 <= k <= 1

Il ne reste plus qu'à trouver k.

I appartient également à la droite (OP), donc :

Du coup, on peut écrire :

Nous sommes dans le plan, nous pouvons décomposer les points et les vecteurs comme suit :

Nous avons donc deux équations, et deux inconnues (k et l).
Si nous résolvons ce système, nous obtenons :

Notez que pour notre cas, nous n'avons pas besoin de l. Je le mets quand même, car on en aura besoin plus loin si on veut s'approcher au plus près du mur.

Voici la fonction de Collision Segment-Segment :

bool CollisionSegSeg(Point A,Point B,Point O,Point P) 
{ 
  if (CollisionDroiteSeg(A,B,O,P)==false) 
     return false;  // inutile d'aller plus loin si le segment [OP] ne touche pas la droite (AB) 
  Vecteur AB,OP; 
  AB.x = B.x - A.x; 
  AB.y = B.y - A.y; 
  OP.x = P.x - O.x; 
  OP.y = P.y - O.y; 
  float k = -(A.x*OP.y-O.x*OP.y-OP.x*A.y+OP.x*O.y)/(AB.x*OP.y-AB.y*OP.x); 
  if (k<0 || k>1) 
     return false; 
  else 
     return true; 
}

Pour terminer ce chapitre, quelques idées pour éviter de se retrouver dans le mur.
Si vous êtes le point O et que vous allez vers le mur, alors il y aura collision. L'idée est d'avancer quand même « jusqu'au mur ».

Comme nous allons dans le mur, nous ne déplacerons pas notre joueur selon le vecteur kitxmlcodeinlinelatexdvp\vec{OP}finkitxmlcodeinlinelatexdvp, qui nous amènerait au-delà du mur (au point P).
Nous ne le déplacerons pas non plus selon le vecteur kitxmlcodeinlinelatexdvpl*\vec{OP}finkitxmlcodeinlinelatexdvp, qui nous amènerait dans le mur exactement (ce que nous voulons absolument éviter, il ne faut jamais être « dans » le mur).
Nous déplacerons le joueur selon le vecteur kitxmlcodeinlinelatexdvp(l-e)*\vec{OP}finkitxmlcodeinlinelatexdvp où e est un nombre positif très petit (un « epsilon » dit-on dans le jargon mathématique), par exemple 0.001.
Ainsi, nous nous approcherons au plus près du mur, sans être dedans ni passer à travers.