圆线段碰撞检测算法? [英] Circle line-segment collision detection algorithm?

问题描述

我有一条从 A 到 B 的直线和一个位于 C 处、半径为 R 的圆.

I have a line from A to B and a circle positioned at C with the radius R.

用于检查直线是否与圆相交的好算法是什么?它发生在沿圆边缘的哪个坐标处?

What is a good algorithm to use to check whether the line intersects the circle? And at what coordinate along the circles edge it occurred?

推荐答案

采取

1. E 是射线的起点，
2. L 是射线的终点，
3. C 是您要测试的球心
4. r 是球体的半径

1. E is the starting point of the ray,
2. L is the end point of the ray,
3. C is the center of sphere you're testing against
4. r is the radius of that sphere

计算:
d = L - E(射线的方向向量，从开始到结束)
f = E - C(从中心球体到射线起点的向量)

Compute:
d = L - E ( Direction vector of ray, from start to end )
f = E - C ( Vector from center sphere to ray start )

然后通过..找到交点
堵塞:
P = E + t * d
这是一个参数方程:
P_x = E_x + td_x
P_y = E_y + td_y
进入
(x - h)² + (y - k)² = r²
(h,k) = 圆心.

Then the intersection is found by..
Plugging:
P = E + t * d
This is a parametric equation:
P_x = E_x + td_x
P_y = E_y + td_y
into
(x - h)² + (y - k)² = r²
(h,k) = center of circle.

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

Note: We've simplified the problem to 2D here, the solution we get applies also in 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_xtd_x + t²d_x² - 2e_xh - 2td_xh + h² +e_y² + 2e_ytd_y + t²d_y² - 2e_yk - 2td_yk + k² - r² = 0
4. 群组t²( d_x² + d_y² ) +2t( e_xd_x + e_yd_y - d_xh- d_yk ) +e_x² + e_y² -2e_xh - 2e_yk + 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. Letting f = e - ct²( d · d ) + 2t( d · f ) +f · f - r² = 0

1. Expand x² - 2xh + h² + y² - 2yk + k² - r² = 0
2. Plug 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. Explode e_x² + 2e_xtd_x + t²d_x² - 2e_xh - 2td_xh + h² + e_y² + 2e_ytd_y + t²d_y² - 2e_yk - 2td_yk + k² - r² = 0
4. Group t²( d_x² + d_y² ) + 2t( e_xd_x + e_yd_y - d_xh - d_yk ) + e_x² + e_y² - 2e_xh - 2e_yk + h² + k² - r² = 0
5. Finally, t²( d · d ) + 2t( e · d - d · c ) + e · e - 2( e · c ) + c · c - r² = 0
   Where d is the vector d and · is the dot product.
6. And then, t²( d · d ) + 2t( d · ( e - c ) ) + ( e - c ) · ( e - c ) - r² = 0
7. Letting f = e - c t²( d · d ) + 2t( d · f ) + f · f - r² = 0

所以我们得到:
t² * (d · d) + 2t*( f · d) + ( f · f - r² ) = 0

So we get:
t² * (d · d) + 2t*( f · d ) + ( f · 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 ;
}

这篇关于圆线段碰撞检测算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！