圆和线段的碰撞检测算法?
圆和线段的碰撞检测算法?
我有一条从A到B的直线,还有一个位于C点、半径为R的圆。
哪种好的算法可以用来检查这条直线是否与圆相交?并且相交发生在圆边的哪个坐标上?
admin 更改状态以发布 2023年5月23日
似乎没有人考虑到投影,我完全偏离了吗?
将向量AC
投影到AB
上。投影向量AD
得到新点D
如果D
和C
之间的距离小于等于R
,则有交点。
就像这样:
社区编辑:
对于稍后偶然发现这篇帖子的任何人,并想知道如何实现这样的算法,这里有一个通用的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}; }
给定:
- E 是射线的起点,
- L 是射线的终点,
- C 是你要测试碰撞的球体的中心点,
- 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。
得到:
- 展开
x2 - 2xh + h2 + y2 - 2yk + k2 - r2 = 0 - 代入
x = ex + tdx
y = ey + tdy
( ex + tdx )2 - 2( ex + tdx )h + h2 +
( ey + tdy )2 - 2( ey + tdy )k + k2 - r2 = 0 - 展开
ex2 + 2extdx + t2dx2 - 2exh - 2tdxh + h2 +
ey2 + 2eytdy + t2dy2 - 2eyk - 2tdyk + k2 - r2 = 0 - 分组
t2( dx2 + dy2 ) +
2t( exdx + eydy - dxh - dyk ) +
ex2 + ey2 -
2exh - 2eyk + h2 + k2 - r2 = 0 - 最终结果
t2( d · d ) + 2t( e · d - d · c ) + e · e - 2( e · c ) + c · c - r2 = 0
其中,d 是向量 d,· 是点积。 - 进一步:
t2( d · d ) + 2t( d · ( e - c ) ) + ( e - c ) · ( e - c ) - r2 = 0 - 令 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 ; }