如何判斷線段和圓弧是否相交？

01-29

有沒有現成的高效的演算法？

聯合直線參數式方程和圓形隱式方程，是一個二次方程，求解後獲最多兩個根。然後檢查各根是否在線段及圓弧的範圍內。

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 didnt 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 its closer than t2 // (since t1 uses -b - discriminant) // Impale, Poke return true ; } // here t1 didnt 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 ; }

Circle line-segment collision detection algorithm?

這是你要的答案嗎？