Zone Membres

Créer un compte ou se connecter

Site hébergé

BORPG

Boîte à outils

Intersection dans le plan entre un cercle et un segment

Sommaire

1 Langage mathématique
- 1.1 Hypothèses
- 1.2 Solution
2 Implémentation informatique
- 2.1 Pseudo-code
- 2.2 Implémentation en C
3 Démonstration

[modifier] Langage mathématique

[modifier] Hypothèses

Soit deux points $A \begin{pmatrix} A_x \\ A_y \end{pmatrix}$ et $B \begin{pmatrix} B_x \\ B_y \end{pmatrix}$ deux points du segment $\left [ AB \right ]$ .

Soit un cercle de centre $C \begin{pmatrix} C_x \\ C_y \end{pmatrix}$ , et de rayon $ρ$ .

[modifier] Solution

Posons :

$\alpha = \left ( B_x-A_x \right )^2 + \left ( B_y-A_y \right )^2$
$\beta = 2 \times \left [ \left ( B_x-A_x \right ) \times \left ( A_x - C_x \right ) + \left ( B_y-A_y \right ) \times \left ( A_y-C_y \right ) \right ]$
$\gamma = A_x^2 + A_y^2 + C_x^2 + C_y^2 - 2 \times \left ( A_x \times C_x + A_y \times C_y \right ) - \rho^2$
$\Delta = \beta^2 - 4 \times \alpha \times \gamma$

Si $Δ < 0$ , le segment ne coupe pas le cercle.

Dans le cas contraire, c'est-à-dire $\Delta \ge 0$ , il faut faire un second test :

${ \left ( C_x - A_x \right )\times \left ( B_x - A_x \right ) + \left ( C_y - A_y \right ) \times \left ( B_y - A_y \right ) \over \left ( B_x - A_x \right ) \times \left ( B_x - A_x \right ) + \left ( B_y - A_y \right ) \times \left ( B_y - A_y \right ) } \in \left [ 0, 1 \right ] \Leftrightarrow$ le segment coupe le cercle.

[modifier] Implémentation informatique

[modifier] Pseudo-code




SI  ALORS
  
  SI  ET  ALORS
    RETOURNE Intersection
  SINON
    RETOURNE Pas d'intersection
  FIN SI
SINON
  RETOURNE Pas d'intersection
FIN SI

[modifier] Implémentation en C

((C_x - A_x)*(B_x - A_x) + (C_y - A_y)*(B_y - A_y))/((B_x - A_x)*(B_x - A_x) + (B_y - A_y)*(B_y - A_y))

// La fonction renvoie une valeur non nulle en cas d'intersection
int IntersectionPlanCercleSegmentfloat A[2], float B[2], float C[2], float Rayon)
{
    float Alpha, Beta, Gamma, Delta;
    
    Alpha = (B[0] - A[0]) * (B[0] - A[0]) + (B[1] - A[1]) * (B[1] - A[1]);
    Beta  = 2 * ((B[0] - A[0]) * (A[0] - C[0]) + (B[1] - A[1]) * (A[1] - C[1]));
    Gamma = A[0] * A[0] + A[1] * A[1] + C[0] * C[0] + C[1] * C[1] - 2 * (A[0] * C[0] + A[1] * C[1]) - Rayon * Rayon;
    
    if((Beta * Beta - 4 * Alpha * Gamma) >= 0)
    {
        float u;
        
        u = ((C[0] - A[0]) * (B[0] - A[0]) + (C[1] - A[1]) * (B[1] - A[1])) / ((B[0] - A[0]) * (B[0] - A[0]) + (B[1] - A[1]) * (B[1] - A[1]))
        return 0.0f <= u && u <= 1.0f;
        
    } else {
        return 0;
    }
}

[modifier] Démonstration

Le problème est très proche de celui de l'intersection dans le plan entre un cercle et une droite. En effet, si la droite n'a pas de point d'intersection avec le cercle, le segment non plus. C'est donc notre premier test : est-ce que la droite $\left ( AB \right )$ appartient au cercle ?

Si c'est le cas, ne crions pas tout de suite CQFD : il reste à savoir si le segment $\left [ AB \right ]$ a un point d'intersection avec le cercle. Pour ce faire, il est possible de revenir à la fin de la démonstration de l'intersection dans le plan entre un cercle et une droite, afin de calculer u et de vérifier que $u \in \left [ 0, 1 \right ]$ . Cependant, l'utilisation de la racine carré dans la résolution de u peut rapidement nuir aux performances de votre application ! Cherchons donc une autre solution, même si moins évidente, certes ...

La solution est le produit scalaire. Suivez bien : si nous appelons le point $M \in \left [ AB \right ]$ le point le plus proche du cercle, il vérifie donc $\overrightarrow{MC} \cdot \overrightarrow{AB} = 0$ . Faisons maintenant l'hypothèse que $\left ( AB \right )$ a un point de concours avec le cercle, dans ce cas $\left ( \exists M \in \left ( AB \right ) \right ) \overrightarrow{MC} \cdot \overrightarrow{AB} = 0 \Leftrightarrow \left [ AB \right ]$ a un point d'intersection avec le cercle.

Donc trouvons un point $M$ qui vérifie l'équation $\overrightarrow{MC} \cdot \overrightarrow{AB} = 0$ . Si on pose $M = A + u \times \left ( B - A \right )$ , cela revient à trouver u tel que $\left [ C - A - u \times \left ( B - A \right ) \right ] \cdot \overrightarrow{AB} = 0$ .

On écrit le produit scalaire sous forme algébrique, et on isole u, pour trouver $u = { \left ( C_x - A_x \right )\times \left ( B_x - A_x \right ) + \left ( C_y - A_y \right ) \times \left ( B_y - A_y \right ) \over \left ( B_x - A_x \right ) \times \left ( B_x - A_x \right ) + \left ( B_y - A_y \right ) \times \left ( B_y - A_y \right ) }$ . Et, comme dit précédemment, $M \in \left [ AB \right ] \Leftrightarrow u \in \left [ 0, 1 \right ] \Leftrightarrow$ Le segment a un point d'intersection au cercle.

Maintenant on peut crier CQFD :).

Récupérée de « http://www.games-creators.org/wiki/Intersection_dans_le_plan_entre_un_cercle_et_un_segment »

Catégorie: Mathématiques