La méthode la plus basique pour vérifier la collision de deux cercles est d’étudier si la distance entre le centre de chaque cercle est inférieure à la somme du rayon de chaque cercle.

On a donc l’inéquation suivante :
racine((xb- xa)² + (yb- ya)²) <= (da + db)

Avec :
A(xa,ya) le cercle de largeur da et B(xb,yb) le cercle de rayon db

Si l’inéquation ci-dessus est vérifiée, alors nous pouvons dire qu’il y a une collision entre le cercle A et le cercle B.

La racine carrée étant une fonction dite “coûteuse” (en temps et en calcul) en informatique, les algorithmes préfèrent fonctionner à l’aide de l’inéquation suivante :
(xb- xa)² + (yb- ya)² <= (da + db)²
(ceci est possible du fait que les rayons sont strictement positifs, donc l’inéquation reste inchangée même si on les met au carré)

Avec :
A(xa,ya) le cercle de rayon da et B(xb,yb) le cercle de rayon db

Nous pouvons donc concevoir nos cercles de la manière suivante : 

On aura donc la méthode suivante pour vérifier la collision entre deux cercles :

Cela nous permet de créer les représentations suivantes :

Lorsque les deux cercles se touchent, ils sont affichés en rouge/bleu tandis que si ils ne se touchent pas, ils sont affichées en vert. C’est la fonction collide() qui permet de déterminer s’ils se touchent ou non.

Nous avons par la suite décidé d’étudier le temps de calcul moyen pour vérifier la collision entre deux cercles en fonction du nombre de calculs.
En Java, cela donnait le résultat suivant :

Ce résultat paraissant étrange, nous avons décidé d’appliquer le même test dans le langage python et nous avons obtenu les résultats ci-dessous :

Dans la suite du projet, nous réétudierons ces résultats afin de les comparer avec d’autres algorithmes.

Vous pourrez trouver le code en suivant ce lien :
https://drive.google.com/open?id=1a0fqIXFVAjvlT0dXTJhqDQiJ48Q_MEaP