圆和线段的碰撞检测算法?

7 浏览
0 Comments

圆和线段的碰撞检测算法?

我有一条从A到B的直线,还有一个位于C点、半径为R的圆。

\"Image\"

哪种好的算法可以用来检查这条直线是否与圆相交?并且相交发生在圆边的哪个坐标上?

admin 更改状态以发布 2023年5月23日
0
0 Comments

似乎没有人考虑到投影,我完全偏离了吗?

将向量AC投影到AB上。投影向量AD得到新点D
如果DC之间的距离小于等于R,则有交点。

就像这样:
Image by SchoolBoy

社区编辑:

对于稍后偶然发现这篇帖子的任何人,并想知道如何实现这样的算法,这里有一个通用的JavaScript实现,使用常见的向量操作函数。

/**
 * Returns the distance from line segment AB to point C
 */
function distanceSegmentToPoint(A, B, C) {
    // Compute vectors AC and AB
    const AC = sub(C, A);
    const AB = sub(B, A);
    // Get point D by taking the projection of AC onto AB then adding the offset of A
    const D = add(proj(AC, AB), A);
    const AD = sub(D, A);
    // D might not be on AB so calculate k of D down AB (aka solve AD = k * AB)
    // We can use either component, but choose larger value to reduce the chance of dividing by zero
    const k = Math.abs(AB.x) > Math.abs(AB.y) ? AD.x / AB.x : AD.y / AB.y;
    // Check if D is off either end of the line segment
    if (k <= 0.0) {
        return Math.sqrt(hypot2(C, A));
    } else if (k >= 1.0) {
        return Math.sqrt(hypot2(C, B));
    }
    return Math.sqrt(hypot2(C, D));
}

为了实现此代码,我使用了一些常见的向量操作函数,这些函数可能已经被提供在您正在工作的任何环境中。但是,如果您没有这些函数可用,以下是它们的实现方法。

// Define some common functions for working with vectors
const add = (a, b) => ({x: a.x + b.x, y: a.y + b.y});
const sub = (a, b) => ({x: a.x - b.x, y: a.y - b.y});
const dot = (a, b) => a.x * b.x + a.y * b.y;
const hypot2 = (a, b) => dot(sub(a, b), sub(a, b));
// Function for projecting some vector a onto b
function proj(a, b) {
    const k = dot(a, b) / dot(b, b);
    return {x: k * b.x, y: k * b.y};
}

0
0 Comments

给定:

  1. E 是射线的起点,
  2. L 是射线的终点,
  3. C 是你要测试碰撞的球体的中心点,
  4. r 是该球体的半径

计算:
d = L - E (射线的方向向量,从起点到终点)
f = E - C (从球体中心到射线起点的向量)

然后交点可以通过以下方式确定..
代入:
P = E + t * d
这是一个参数方程:
Px = Ex + tdx
Py = Ey + tdy

(x - h)2 + (y - k)2 = r2
(h,k) = 圆的中心点。

注意:我们在此将问题简化为了2D,得到的解决方案也适用于3D。

得到:

  1. 展开
    x2 - 2xh + h2 + y2 - 2yk + k2 - r2 = 0
  2. 代入
    x = ex + tdx
    y = ey + tdy
    ( ex + tdx )2 - 2( ex + tdx )h + h2 +
    ( ey + tdy )2 - 2( ey + tdy )k + k2 - r2 = 0
  3. 展开
    ex2 + 2extdx + t2dx2 - 2exh - 2tdxh + h2 +
    ey2 + 2eytdy + t2dy2 - 2eyk - 2tdyk + k2 - r2 = 0
  4. 分组
    t2( dx2 + dy2 ) +
    2t( exdx + eydy - dxh - dyk ) +
    ex2 + ey2 -
    2exh - 2eyk + h2 + k2 - r2 = 0
  5. 最终结果
    t2( d · d ) + 2t( e · d - d · c ) + e · e - 2( e · c ) + c · c - r2 = 0
    其中,d 是向量 d,· 是点积。
  6. 进一步:
    t2( d · d ) + 2t( d · ( e - c ) ) + ( e - c ) · ( e - c ) - r2 = 0
  7. f = e - c
    t2( d · d ) + 2t( d · f ) + f · f - r2 = 0

所以我们得到:
t2 * (d · d) + 2t*( f · d ) + ( f · f - r2 ) = 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 ;
}

0