Algorithme de détection des collisions entre segments de ligne en cercle ?

Question

Je dispose d'une ligne allant de A à B et d'un cercle positionné en C avec le rayon R.

Quel est un bon algorithme à utiliser pour vérifier si la ligne intersecte le cercle ? Et à quelle coordonnée le long de l'arête du cercle cela se produit-il ?

Answer 1

En prenant

1. E est le point de départ du rayon,
2. L est le point final du rayon,
3. C est le centre de la sphère que vous testez.
4. r est le rayon de cette sphère

Calculer :
d \= L - E (vecteur directionnel du rayon, du début à la fin)
f \= E - C (vecteur du centre de la sphère au début du rayon)

Ensuite, l'intersection est trouvée par
Branchement :
P = E + t * d
Il s'agit d'une équation paramétrique :
P _x \= E _x + td _x
P _y \= E _y + td _y
en
(x - h) 2 + (y - k) 2 \= r 2
(h,k) = centre du cercle.

Note : Nous avons simplifié le problème en 2D ici, la solution que nous obtenons s'applique également en 3D.

pour obtenir :

1. Développez x 2 - 2xh + h 2 + y 2 - 2yk + k 2 - r 2 \= 0
2. Bouchon x = e _x + td _x
   y = e _y + td _y
   ( e _x + td _x ) 2 - 2( e _x + td _x )h + h 2 + ( e _y + td _y ) 2 - 2( e _y + td _y )k + k 2 - r 2 \= 0
3. Explosion e _x 2 + 2e _x td _x + t 2 d _x 2 - 2e _x h - 2td _x h + h 2 + e _y 2 + 2e _y td _y + t 2 d _y 2 - 2e _y k - 2td _y k + k 2 - r 2 \= 0
4. Groupe t 2 ( d _x 2 + d _y 2 ) + 2t( e _x d _x + e _y d _y - d _x h - d _y k ) + e _x 2 + e _y 2 - 2e _x h - 2e _y k + h 2 + k 2 - r 2 \= 0
5. Enfin, t 2 ( d - d ) + 2t( e - d - d - c ) + e - e - 2( e - c ) + c - c - r 2 \= 0
   Où d est le vecteur d et - est le produit scalaire.
6. Et puis, t 2 ( d - d ) + 2t( d - ( e - c ) ) + ( e - c ) - ( e - c ) - r 2 \= 0
7. Location f \= e - c t 2 ( d - d ) + 2t( d - f ) + f - f - r 2 \= 0

Donc on a :
t 2 * ( d - d ) + 2t*( f - d ) + ( f - f - r 2 ) = 0

Donc, en résolvant l'équation quadratique :

float a = d.Dot( d ) ;
float b = 2*f.Dot( d ) ;
float c = f.Dot( f ) - r*r ;

float discriminant = b*b-4*a*c;
if( discriminant < 0 )
{
  // no intersection
}
else
{
  // ray didn't totally miss sphere,
  // so there is a solution to
  // the equation.

  discriminant = sqrt( discriminant );

  // either solution may be on or off the ray so need to test both
  // t1 is always the smaller value, because BOTH discriminant and
  // a are nonnegative.
  float t1 = (-b - discriminant)/(2*a);
  float t2 = (-b + discriminant)/(2*a);

  // 3x HIT cases:
  //          -o->             --|-->  |            |  --|->
  // Impale(t1 hit,t2 hit), Poke(t1 hit,t2>1), ExitWound(t1<0, t2 hit), 

  // 3x MISS cases:
  //       ->  o                     o ->              | -> |
  // FallShort (t1>1,t2>1), Past (t1<0,t2<0), CompletelyInside(t1<0, t2>1)

  if( t1 >= 0 && t1 <= 1 )
  {
    // t1 is the intersection, and it's closer than t2
    // (since t1 uses -b - discriminant)
    // Impale, Poke
    return true ;
  }

  // here t1 didn't intersect so we are either started
  // inside the sphere or completely past it
  if( t2 >= 0 && t2 <= 1 )
  {
    // ExitWound
    return true ;
  }

  // no intn: FallShort, Past, CompletelyInside
  return false ;
}

Answer 2

Personne ne semble envisager la projection, suis-je complètement à côté de la plaque ?

Projeter le vecteur AC sur AB . Le vecteur projeté, AD donne le nouveau point D .
Si la distance entre D et C est inférieur (ou égal) à R nous avons une intersection.

Comme ça :

Answer 3

J'utiliserais l'algorithme pour calculer la distance entre un point (centre du cercle) et une ligne (ligne AB). Cette distance peut ensuite être utilisée pour déterminer les points d'intersection de la ligne avec le cercle.

Disons que nous avons les points A, B, C. Ax et Ay sont les composantes x et y des points A. De même pour B et C. Le scalaire R est le rayon du cercle. Idem pour B et C. Le scalaire R est le rayon du cercle.

Cet algorithme exige que A, B et C soient des points distincts et que R soit différent de 0.

Voici l'algorithme

// compute the euclidean distance between A and B
LAB = sqrt( (Bx-Ax)²+(By-Ay)² )

// compute the direction vector D from A to B
Dx = (Bx-Ax)/LAB
Dy = (By-Ay)/LAB

// the equation of the line AB is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= LAB.

// compute the distance between the points A and E, where
// E is the point of AB closest the circle center (Cx, Cy)
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)    

// compute the coordinates of the point E
Ex = t*Dx+Ax
Ey = t*Dy+Ay

// compute the euclidean distance between E and C
LEC = sqrt((Ex-Cx)²+(Ey-Cy)²)

// test if the line intersects the circle
if( LEC < R )
{
    // compute distance from t to circle intersection point
    dt = sqrt( R² - LEC²)

    // compute first intersection point
    Fx = (t-dt)*Dx + Ax
    Fy = (t-dt)*Dy + Ay

    // compute second intersection point
    Gx = (t+dt)*Dx + Ax
    Gy = (t+dt)*Dy + Ay
}

// else test if the line is tangent to circle
else if( LEC == R )
    // tangent point to circle is E

else
    // line doesn't touch circle

Answer 4

Ok, je ne vous donnerai pas de code, mais puisque vous avez marqué ceci algorithme mais je ne pense pas que cela vous concerne. D'abord, tu dois obtenir un vecteur perpendiculaire à la ligne.

Vous aurez une variable inconnue dans y = ax + c ( c sera inconnu )
Pour résoudre cela, calculez sa valeur lorsque la ligne passe par le centre du cercle.

C'est-à-dire,
Introduisez la position du centre du cercle dans l'équation de la ligne et résolvez pour c .
Calculez ensuite le point d'intersection de la ligne d'origine et de sa normale.

Vous obtiendrez ainsi le point de la ligne le plus proche du cercle.
Calculez la distance entre ce point et le centre du cercle (en utilisant la magnitude du vecteur).
Si cette valeur est inférieure au rayon du cercle, voilà, nous avons une intersection !

Answer 5

Une autre méthode utilise la formule de l'aire du triangle ABC. Le test d'intersection est plus simple et plus efficace que la méthode de projection, mais trouver les coordonnées du point d'intersection demande plus de travail. Au moins, il sera retardé jusqu'au moment où il sera nécessaire.

La formule pour calculer l'aire du triangle est : aire = bh/2

où b est la longueur de la base et h est la hauteur. Nous avons choisi le segment AB comme base pour que h soit la plus courte distance entre C, le centre du cercle, et la ligne.

Puisque l'aire du triangle peut également être calculée par un produit scalaire vectoriel, nous pouvons déterminer h.

// compute the triangle area times 2 (area = area2/2)
area2 = abs( (Bx-Ax)*(Cy-Ay) - (Cx-Ax)(By-Ay) )

// compute the AB segment length
LAB = sqrt( (Bx-Ax)² + (By-Ay)² )

// compute the triangle height
h = area2/LAB

// if the line intersects the circle
if( h < R )
{
    ...
}        

UPDATE 1 :

Vous pouvez optimiser le code en utilisant le calcul rapide de la racine carrée inverse décrit dans le document suivant ici pour obtenir une bonne approximation de 1/LAB.

Le calcul du point d'intersection n'est pas si difficile. Voici comment procéder

// compute the line AB direction vector components
Dx = (Bx-Ax)/LAB
Dy = (By-Ay)/LAB

// compute the distance from A toward B of closest point to C
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)

// t should be equal to sqrt( (Cx-Ax)² + (Cy-Ay)² - h² )

// compute the intersection point distance from t
dt = sqrt( R² - h² )

// compute first intersection point coordinate
Ex = Ax + (t-dt)*Dx
Ey = Ay + (t-dt)*Dy

// compute second intersection point coordinate
Fx = Ax + (t+dt)*Dx
Fy = Ay + (t+dt)*Dy

Si h = R alors la droite AB est tangente au cercle et la valeur dt = 0 et E = F. Les coordonnées du point sont celles de E et F.

Vous devez vérifier que A est différent de B et que la longueur du segment n'est pas nulle si cela peut se produire dans votre application.