圆线段碰撞检测算法？

Question

圆线段碰撞检测算法？我有一条从A到B的直线，在C上有一个半径为R的圆。检查直线是否与圆相交的好算法是什么？在圆周边缘的什么坐标上发生了这种情况？

Answer 1

取

1. E

   是射线的起点，

2. L

   是射线的终点，

3. C

   是你要测试的球体的中心

4. r

   是那个球体的半径

计算：
d=L-E(射线的方向矢量，从头到尾)
f=E-C(从中心球到射线起始的矢量)

然后交叉口被.。
堵塞：
P=E+t*d
这是一个参数方程：
P_x=E_x+TD_x
P_y=E_y+TD_y
进
(X-h)²+(y-k)²=r²
(h，k)=圆心。

注意：我们将问题简化为2D，我们得到的解决方案也适用于3D

得到：

1. 扩张
   x²

   -2xh+h

   ²

   +y

   ²

   -2yk+k

   ²

   -r

   ² = 0

2. 塞子
   

   X=e

   _x

   +TD

   _x
   

   Y=e

   _y

   +TD

   _y
   

   (E)

   _x

   +TD

   _x )²

   -2(E)

   _x

   +TD

   _x

   )h+h

   ²

   +(E)

   _y

   +TD

   _y )²

   -2(E)

   _y

   +TD

   _y

   )k+k

   ²

   -r

   ² = 0

3. 爆炸

   
   e_x²

   +2E

   _x

   白破疫苗

   _x

   +t

   ²d_x²

   -2e

   _x

   H-2Td

   _x

   H+h

   ²

   +e

   _y²

   +2E

   _y

   白破疫苗

   _y

   +t

   ²d_y²

   -2e

   _y

   K-2td

   _y

   K+k

   ²

   -r

   ² = 0

4. 群
   t²

   (D)

   _x²

   +d

   _y²

   )+2t(E)

   _xd_x

   +e

   _yd_y

   -d

   _x

   氢-d

   _y

   k)+e

   _x²

   +e

   _y²

   -2e

   _x

   氢-2e

   _y

   K+h

   ²

   +k

   ²

   -r

   ² = 0

5. 最后，
   t²

   (_d*_d)+2t(_e*_d-_d*_c)+_e*_e-2(_e*_c)+_c*_c-r

   ² = 0
   

   *其中_d是向量d，*是点积。

6. 然后,
   t²

   (_d*_d)+2t(_d*(_e-c)+(_e-c)*(_e-c)-r

   ² = 0

7. 让f=_e-_c
   t²

   (_d*_d)+2t(_d*_f)+_f*_f-r

   ² = 0

所以我们得到：
t²*(D DOT D)+2t*(F DOT D)+(f DOT f-r)² ) = 0
所以解二次方程：

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

似乎没有人考虑投影，我是不是完全偏离轨道了？

投影向量AC落在AB..投影矢量，AD，给出了新的观点D.
如果之间的距离D和C小于(或等于)R我们有个十字路口。

Answer 3

我会使用算法来计算点(圆心)和直线(AB线)之间的距离。然后，这可以用来确定直线与圆的交点。

假设我们有点A，B，C，Ax和Ay是A点的x和y分量。B和C相同，标量R是圆半径。

该算法要求A、B和C是不同的点，而R不是0。

这是算法

// 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