我有一条从a到B的直线和一个半径为R的圆。
用什么算法来检查直线是否与圆相交?它在圆边的哪个坐标上?
我有一条从a到B的直线和一个半径为R的圆。
用什么算法来检查直线是否与圆相交?它在圆边的哪个坐标上?
当前回答
我发现这个解决方案似乎比其他一些解决方案更容易遵循。
采取:
p1 and p2 as the points for the line, and
c as the center point for the circle and r for the radius
我可以用斜截式来解直线方程。但是,我不想处理以c为点的复杂方程,所以我只是平移了坐标系使圆在(0,0)处
p3 = p1 - c
p4 = p2 - c
顺便说一下,当我相互减分的时候,我是在减去x再减去y,然后把它们放到一个新的点里,以防有人不知道。
不管怎样,我现在解出p3和p4的直线方程
m = (p4_y - p3_y) / (p4_x - p3) (the underscore is an attempt at subscript)
y = mx + b
y - mx = b (just put in a point for x and y, and insert the m we found)
好的。现在我需要让这两个方程相等。首先我需要解圆的x方程
x^2 + y^2 = r^2
y^2 = r^2 - x^2
y = sqrt(r^2 - x^2)
然后我让它们相等:
mx + b = sqrt(r^2 - x^2)
求二次方程(0 = ax^2 + bx + c)
(mx + b)^2 = r^2 - x^2
(mx)^2 + 2mbx + b^2 = r^2 - x^2
0 = m^2 * x^2 + x^2 + 2mbx + b^2 - r^2
0 = (m^2 + 1) * x^2 + 2mbx + b^2 - r^2
现在我有了a b c。
a = m^2 + 1
b = 2mb
c = b^2 - r^2
我把这个代入二次公式
(-b ± sqrt(b^2 - 4ac)) / 2a
用值代入,然后尽可能简化:
(-2mb ± sqrt(b^2 - 4ac)) / 2a
(-2mb ± sqrt((-2mb)^2 - 4(m^2 + 1)(b^2 - r^2))) / 2(m^2 + 1)
(-2mb ± sqrt(4m^2 * b^2 - 4(m^2 * b^2 - m^2 * r^2 + b^2 - r^2))) / 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * b^2 - (m^2 * b^2 - m^2 * r^2 + b^2 - r^2))))/ 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * b^2 - m^2 * b^2 + m^2 * r^2 - b^2 + r^2)))/ 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * r^2 - b^2 + r^2)))/ 2m^2 + 2
(-2mb ± sqrt(4) * sqrt(m^2 * r^2 - b^2 + r^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(m^2 * r^2 - b^2 + r^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(m^2 * r^2 + r^2 - b^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2
这几乎是化简的极限了。最后,分离出带有±的方程:
(-2mb + 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2 or
(-2mb - 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2
然后简单地将这两个方程的结果代入mx + b中的x。为了清晰起见,我写了一些JavaScript代码来演示如何使用这个:
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((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2)); //the value under the square root sign
if (underRadical < 0){
//line completely missed
return false;
} else {
var t1 = (-2*m*b+2*Math.sqrt(underRadical))/(2 * Math.pow(m,2) + 2); //one of the intercept x's
var t2 = (-2*m*b-2*Math.sqrt(underRadical))/(2 * Math.pow(m,2) + 2); //other intercept's x
var i1 = {x:t1,y:m*t1+b} //intercept point 1
var i2 = {x:t2,y:m*t2+b} //intercept point 2
return [i1,i2];
}
}
我希望这能有所帮助!
附注:如果任何人发现任何错误或有任何建议,请评论。我是新手,欢迎大家的帮助/建议。
其他回答
虽然我认为使用线圆交点,然后检查交点是否在端点之间更好,可能更便宜,但我想添加这个更直观的解决方案。
我喜欢把这个问题想象成“香肠上的点问题”,在不改变算法的情况下,它可以在任何维度上工作。 这个解找不到交点。
以下是我想到的:
(我使用“小于”,但“小于或等于”也可以使用,这取决于我们测试的内容。)
确保Circle_Point小于到无限线的半径距离。(这里使用最喜欢的方法)。 计算从两个Segment_Points到Circle_Point的距离。 测试较大的Circle_Point-Segment_Point距离是否小于根号(Segment_Length^2+Radius^2)。 (这是从一个分段点到一个理论点的距离,也就是从另一个分段点到无限线(直角)的半径距离。见图片)。
3 t。如果为true: Circle_Point在sausage内部。 3 f。如果为false:如果较小的Circle_Point- segment_point距离小于Radius,则Circle_Point在sausage内部。
图片:最粗的线段是选定的线段,没有示例圆。有点粗糙,有些像素有点不对。
function boolean pointInSausage(sp1,sp2,r,c) {
if ( !(pointLineDist(c,sp1,sp2) < r) ) {
return false;
}
double a = dist(sp1,c);
double b = dist(sp2,c);
double l;
double s;
if (a>b) {
l = a;
s = b;
} else {
l = b;
s = a;
}
double segLength = dist(sp1,sp2);
if ( l < sqrt(segLength*segLength+r*r) ) {
return true;
}
return s < r;
}
如果发现任何问题,告诉我,我会编辑或撤回。
如果你找到了圆心(因为它是3D的,我想你是指球体而不是圆)和直线之间的距离,然后检查这个距离是否小于可以做到这一点的半径。
碰撞点显然是直线和球面之间最近的点(当你计算球面和直线之间的距离时,会计算出这个点)
点与线之间的距离: http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html
这个Java函数返回一个DVec2对象。它用DVec2表示圆心,用DVec2表示半径,用Line表示直线。
public static DVec2 CircLine(DVec2 C, double r, Line line)
{
DVec2 A = line.p1;
DVec2 B = line.p2;
DVec2 P;
DVec2 AC = new DVec2( C );
AC.sub(A);
DVec2 AB = new DVec2( B );
AB.sub(A);
double ab2 = AB.dot(AB);
double acab = AC.dot(AB);
double t = acab / ab2;
if (t < 0.0)
t = 0.0;
else if (t > 1.0)
t = 1.0;
//P = A + t * AB;
P = new DVec2( AB );
P.mul( t );
P.add( A );
DVec2 H = new DVec2( P );
H.sub( C );
double h2 = H.dot(H);
double r2 = r * r;
if(h2 > r2)
return null;
else
return P;
}
好吧,我不会给你代码,但既然你已经标记了这个算法,我认为这对你来说无关紧要。 首先,你要得到一个垂直于这条直线的向量。
y = ax + c是一个未知变量c是未知变量 为了解决这个问题,计算直线经过圆心时的值。
也就是说, 将圆心的位置代入直线方程,解出c。 然后计算原直线与其法线的交点。
这样就能得到直线上离圆最近的点。 计算该点到圆中心之间的距离(使用矢量的大小)。 如果这个小于圆的半径,看,我们有一个交点!
采取
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 ;
}