我有一条从a到B的直线和一个半径为R的圆。
用什么算法来检查直线是否与圆相交?它在圆边的哪个坐标上?
我有一条从a到B的直线和一个半径为R的圆。
用什么算法来检查直线是否与圆相交?它在圆边的哪个坐标上?
当前回答
我会用这个算法来计算点(圆心)和线(线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
其他回答
如果直线的坐标为A.x, A.y和B.x, B.y,圆心为C.x, C.y,则直线公式为:
x = A.x * t + B.x * (1 - t)
y = A.y * t + B.y * (1 - t)
0 < = t < = 1
这个圆是
(C.x - x)²+ (C.y - y)²= R²
如果你把直线的x和y公式代入圆公式,你会得到一个t的二阶方程,它的解是交点(如果有的话)。如果你得到的t小于0或大于1,那么它不是一个解,但它表明这条线“指向”圆的方向。
奇怪的是,我可以回答,但不能评论…… 我喜欢Multitaskpro的方法,它可以移动所有东西,使圆的中心落在原点上。不幸的是,他的代码中有两个问题。首先在平方根下的部分,你需要去掉双倍的幂。所以不是:
is underRadical = Math.pow((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2));
but:
under Radical = Math.pow(r,2)*(Math.pow(m,2)+1)) - Math.pow(b,2);
在最后的坐标中,他忘记把解移回来。所以不是:
var i1 = {x:t1,y:m*t1+b}
but:
Var i1 = {x:t1+c。x, y: m * t1 + b +陈守惠};
整个函数就变成:
function interceptOnCircle(p1, p2, c, r) {
//p1 is the first line point
//p2 is the second line point
//c is the circle's center
//r is the circle's radius
var p3 = {x:p1.x - c.x, y:p1.y - c.y}; //shifted line points
var p4 = {x:p2.x - c.x, y:p2.y - c.y};
var m = (p4.y - p3.y) / (p4.x - p3.x); //slope of the line
var b = p3.y - m * p3.x; //y-intercept of line
var underRadical = Math.pow(r,2)*Math.pow(m,2) + Math.pow(r,2) - Math.pow(b,2); //the value under the square root sign
if (underRadical < 0) {
//line completely missed
return false;
} else {
var t1 = (-m*b + Math.sqrt(underRadical))/(Math.pow(m,2) + 1); //one of the intercept x's
var t2 = (-m*b - Math.sqrt(underRadical))/(Math.pow(m,2) + 1); //other intercept's x
var i1 = {x:t1+c.x, y:m*t1+b+c.y}; //intercept point 1
var i2 = {x:t2+c.x, y:m*t2+b+c.y}; //intercept point 2
return [i1, i2];
}
}
采取
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
得到:
Expand x2 - 2xh + h2 + y2 - 2yk + k2 - r2 = 0 Plug x = ex + tdx y = ey + tdy ( ex + tdx )2 - 2( ex + tdx )h + h2 + ( ey + tdy )2 - 2( ey + tdy )k + k2 - r2 = 0 Explode ex2 + 2extdx + t2dx2 - 2exh - 2tdxh + h2 + ey2 + 2eytdy + t2dy2 - 2eyk - 2tdyk + k2 - r2 = 0 Group t2( dx2 + dy2 ) + 2t( exdx + eydy - dxh - dyk ) + ex2 + ey2 - 2exh - 2eyk + h2 + k2 - r2 = 0 Finally, t2( d · d ) + 2t( e · d - d · c ) + e · e - 2( e · c ) + c · c - r2 = 0 Where d is the vector d and · is the dot product. And then, t2( d · d ) + 2t( d · ( e - c ) ) + ( e - c ) · ( e - c ) - r2 = 0 Letting 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 ;
}
另一种方法使用三角形ABC面积公式。交点检验比投影法简单高效,但求交点坐标需要更多的工作。至少它会被推迟到需要的时候。
三角形面积的计算公式为:area = bh/2
b是底长,h是高。我们选择线段AB作为底,使h是圆心C到直线的最短距离。
因为三角形的面积也可以用向量点积来计算,所以我们可以确定h。
// compute the triangle area times 2 (area = area2/2)
area2 = abs( (Bx-Ax)*(Cy-Ay) - (Cx-Ax)(By-Ay) )
// compute the AB segment length
LAB = sqrt( (Bx-Ax)² + (By-Ay)² )
// compute the triangle height
h = area2/LAB
// if the line intersects the circle
if( h < R )
{
...
}
更新1:
您可以通过使用这里描述的快速平方根倒数计算来优化代码,以获得1/LAB的良好近似值。
计算交点并不难。开始了
// compute the line AB direction vector components
Dx = (Bx-Ax)/LAB
Dy = (By-Ay)/LAB
// compute the distance from A toward B of closest point to C
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)
// t should be equal to sqrt( (Cx-Ax)² + (Cy-Ay)² - h² )
// compute the intersection point distance from t
dt = sqrt( R² - h² )
// compute first intersection point coordinate
Ex = Ax + (t-dt)*Dx
Ey = Ay + (t-dt)*Dy
// compute second intersection point coordinate
Fx = Ax + (t+dt)*Dx
Fy = Ay + (t+dt)*Dy
如果h = R,则直线AB与圆相切,且值dt = 0, E = F。点的坐标为E和F的坐标。
如果在应用程序中出现这种情况,您应该检查A与B是否不同,并且段长度不为空。
以下是我在TypeScript中的解决方案,遵循@Mizipzor建议的想法(使用投影):
/**
* Determines whether a line segment defined by a start and end point intersects with a sphere defined by a center point and a radius
* @param a the start point of the line segment
* @param b the end point of the line segment
* @param c the center point of the sphere
* @param r the radius of the sphere
*/
export function lineSphereIntersects(
a: IPoint,
b: IPoint,
c: IPoint,
r: number
): boolean {
// find the three sides of the triangle formed by the three points
const ab: number = distance(a, b);
const ac: number = distance(a, c);
const bc: number = distance(b, c);
// check to see if either ends of the line segment are inside of the sphere
if (ac < r || bc < r) {
return true;
}
// find the angle between the line segment and the center of the sphere
const numerator: number = Math.pow(ac, 2) + Math.pow(ab, 2) - Math.pow(bc, 2);
const denominator: number = 2 * ac * ab;
const cab: number = Math.acos(numerator / denominator);
// find the distance from the center of the sphere and the line segment
const cd: number = Math.sin(cab) * ac;
// if the radius is at least as long as the distance between the center and the line
if (r >= cd) {
// find the distance between the line start and the point on the line closest to
// the center of the sphere
const ad: number = Math.cos(cab) * ac;
// intersection occurs when the point on the line closest to the sphere center is
// no further away than the end of the line
return ad <= ab;
}
return false;
}
export function distance(a: IPoint, b: IPoint): number {
return Math.sqrt(
Math.pow(b.z - a.z, 2) + Math.pow(b.y - a.y, 2) + Math.pow(b.x - a.x, 2)
);
}
export interface IPoint {
x: number;
y: number;
z: number;
}