我有一条从a到B的直线和一个半径为R的圆。
用什么算法来检查直线是否与圆相交?它在圆边的哪个坐标上?
我有一条从a到B的直线和一个半径为R的圆。
用什么算法来检查直线是否与圆相交?它在圆边的哪个坐标上?
当前回答
这里是一个用golang写的解决方案。这个方法和这里发布的其他一些答案类似,但不完全相同。它易于实现,并已经过测试。以下是步骤:
Translate coordinates so that the circle is at the origin. Express the line segment as parametrized functions of t for both the x and y coordinates. If t is 0, the function's values are one end point of the segment, and if t is 1, the function's values are the other end point. Solve, if possible, the quadratic equation resulting from constraining values of t that produce x, y coordinates with distances from the origin equal to the circle's radius. Throw out solutions where t is < 0 or > 1 ( <= 0 or >= 1 for an open segment). Those points are not contained in the segment. Translate back to original coordinates.
这里导出了二次曲线的A、B和C的值,其中(n-et)和(m-dt)分别是直线x坐标和y坐标的方程。R是圆的半径。
(n-et)(n-et) + (m-dt)(m-dt) = rr
nn - 2etn + etet + mm - 2mdt + dtdt = rr
(ee+dd)tt - 2(en + dm)t + nn + mm - rr = 0
因此A = ee+dd, B = - 2(en + dm), C = nn + mm - rr。
下面是函数的golang代码:
package geom
import (
"math"
)
// SegmentCircleIntersection return points of intersection between a circle and
// a line segment. The Boolean intersects returns true if one or
// more solutions exist. If only one solution exists,
// x1 == x2 and y1 == y2.
// s1x and s1y are coordinates for one end point of the segment, and
// s2x and s2y are coordinates for the other end of the segment.
// cx and cy are the coordinates of the center of the circle and
// r is the radius of the circle.
func SegmentCircleIntersection(s1x, s1y, s2x, s2y, cx, cy, r float64) (x1, y1, x2, y2 float64, intersects bool) {
// (n-et) and (m-dt) are expressions for the x and y coordinates
// of a parameterized line in coordinates whose origin is the
// center of the circle.
// When t = 0, (n-et) == s1x - cx and (m-dt) == s1y - cy
// When t = 1, (n-et) == s2x - cx and (m-dt) == s2y - cy.
n := s2x - cx
m := s2y - cy
e := s2x - s1x
d := s2y - s1y
// lineFunc checks if the t parameter is in the segment and if so
// calculates the line point in the unshifted coordinates (adds back
// cx and cy.
lineFunc := func(t float64) (x, y float64, inBounds bool) {
inBounds = t >= 0 && t <= 1 // Check bounds on closed segment
// To check bounds for an open segment use t > 0 && t < 1
if inBounds { // Calc coords for point in segment
x = n - e*t + cx
y = m - d*t + cy
}
return
}
// Since we want the points on the line distance r from the origin,
// (n-et)(n-et) + (m-dt)(m-dt) = rr.
// Expanding and collecting terms yeilds the following quadratic equation:
A, B, C := e*e+d*d, -2*(e*n+m*d), n*n+m*m-r*r
D := B*B - 4*A*C // discriminant of quadratic
if D < 0 {
return // No solution
}
D = math.Sqrt(D)
var p1In, p2In bool
x1, y1, p1In = lineFunc((-B + D) / (2 * A)) // First root
if D == 0.0 {
intersects = p1In
x2, y2 = x1, y1
return // Only possible solution, quadratic has one root.
}
x2, y2, p2In = lineFunc((-B - D) / (2 * A)) // Second root
intersects = p1In || p2In
if p1In == false { // Only x2, y2 may be valid solutions
x1, y1 = x2, y2
} else if p2In == false { // Only x1, y1 are valid solutions
x2, y2 = x1, y1
}
return
}
我用这个函数进行了测试,确认解点在线段内和圆上。它创建了一个测试段,并围绕给定的圆进行扫描:
package geom_test
import (
"testing"
. "**put your package path here**"
)
func CheckEpsilon(t *testing.T, v, epsilon float64, message string) {
if v > epsilon || v < -epsilon {
t.Error(message, v, epsilon)
t.FailNow()
}
}
func TestSegmentCircleIntersection(t *testing.T) {
epsilon := 1e-10 // Something smallish
x1, y1 := 5.0, 2.0 // segment end point 1
x2, y2 := 50.0, 30.0 // segment end point 2
cx, cy := 100.0, 90.0 // center of circle
r := 80.0
segx, segy := x2-x1, y2-y1
testCntr, solutionCntr := 0, 0
for i := -100; i < 100; i++ {
for j := -100; j < 100; j++ {
testCntr++
s1x, s2x := x1+float64(i), x2+float64(i)
s1y, s2y := y1+float64(j), y2+float64(j)
sc1x, sc1y := s1x-cx, s1y-cy
seg1Inside := sc1x*sc1x+sc1y*sc1y < r*r
sc2x, sc2y := s2x-cx, s2y-cy
seg2Inside := sc2x*sc2x+sc2y*sc2y < r*r
p1x, p1y, p2x, p2y, intersects := SegmentCircleIntersection(s1x, s1y, s2x, s2y, cx, cy, r)
if intersects {
solutionCntr++
//Check if points are on circle
c1x, c1y := p1x-cx, p1y-cy
deltaLen1 := (c1x*c1x + c1y*c1y) - r*r
CheckEpsilon(t, deltaLen1, epsilon, "p1 not on circle")
c2x, c2y := p2x-cx, p2y-cy
deltaLen2 := (c2x*c2x + c2y*c2y) - r*r
CheckEpsilon(t, deltaLen2, epsilon, "p2 not on circle")
// Check if points are on the line through the line segment
// "cross product" of vector from a segment point to the point
// and the vector for the segment should be near zero
vp1x, vp1y := p1x-s1x, p1y-s1y
crossProd1 := vp1x*segy - vp1y*segx
CheckEpsilon(t, crossProd1, epsilon, "p1 not on line ")
vp2x, vp2y := p2x-s1x, p2y-s1y
crossProd2 := vp2x*segy - vp2y*segx
CheckEpsilon(t, crossProd2, epsilon, "p2 not on line ")
// Check if point is between points s1 and s2 on line
// This means the sign of the dot prod of the segment vector
// and point to segment end point vectors are opposite for
// either end.
wp1x, wp1y := p1x-s2x, p1y-s2y
dp1v := vp1x*segx + vp1y*segy
dp1w := wp1x*segx + wp1y*segy
if (dp1v < 0 && dp1w < 0) || (dp1v > 0 && dp1w > 0) {
t.Error("point not contained in segment ", dp1v, dp1w)
t.FailNow()
}
wp2x, wp2y := p2x-s2x, p2y-s2y
dp2v := vp2x*segx + vp2y*segy
dp2w := wp2x*segx + wp2y*segy
if (dp2v < 0 && dp2w < 0) || (dp2v > 0 && dp2w > 0) {
t.Error("point not contained in segment ", dp2v, dp2w)
t.FailNow()
}
if s1x == s2x && s2y == s1y { //Only one solution
// Test that one end of the segment is withing the radius of the circle
// and one is not
if seg1Inside && seg2Inside {
t.Error("Only one solution but both line segment ends inside")
t.FailNow()
}
if !seg1Inside && !seg2Inside {
t.Error("Only one solution but both line segment ends outside")
t.FailNow()
}
}
} else { // No intersection, check if both points outside or inside
if (seg1Inside && !seg2Inside) || (!seg1Inside && seg2Inside) {
t.Error("No solution but only one point in radius of circle")
t.FailNow()
}
}
}
}
t.Log("Tested ", testCntr, " examples and found ", solutionCntr, " solutions.")
}
下面是测试的输出:
=== RUN TestSegmentCircleIntersection
--- PASS: TestSegmentCircleIntersection (0.00s)
geom_test.go:105: Tested 40000 examples and found 7343 solutions.
最后,该方法很容易扩展到射线从一点开始,经过另一点并延伸到无穷远的情况,只需测试t > 0或t < 1,而不是两者都测试。
其他回答
在此post circle中,通过检查圆心与线段上的点(Ipoint)之间的距离来检查线碰撞,该点表示从圆心到线段的法线N(图2)之间的交点。
(https://i.stack.imgur.com/3o6do.png)
在图像1中显示一个圆和一条直线,向量A指向线的起点,向量B指向线的终点,向量C指向圆的中心。现在我们必须找到向量E(从线起点到圆中心)和向量D(从线起点到线终点)这个计算如图1所示。
(https://i.stack.imgur.com/7098a.png)
在图2中,我们可以看到向量E通过向量E与单位向量D的“点积”投影到向量D上,点积的结果是标量Xp,表示向量N与向量D的直线起点与交点(Ipoint)之间的距离。 下一个向量X是由单位向量D和标量Xp相乘得到的。
现在我们需要找到向量Z(向量到Ipoint),它很容易它简单的向量加法向量A(在直线上的起点)和向量x。接下来我们需要处理特殊情况,我们必须检查是Ipoint在线段上,如果不是我们必须找出它是它的左边还是右边,我们将使用向量最接近来确定哪个点最接近圆。
(https://i.stack.imgur.com/p9WIr.png)
当投影Xp为负时,Ipoint在线段的左边,距离最近的向量等于线起点的向量,当投影Xp大于向量D的模时,距离最近的向量在线段的右边,距离最近的向量等于线终点的向量在其他情况下,距离最近的向量等于向量Z。
现在,当我们有最近的向量,我们需要找到从圆中心到Ipoint的向量(dist向量),很简单,我们只需要从中心向量减去最近的向量。接下来,检查向量距离的大小是否小于圆半径,如果是,那么它们就会碰撞,如果不是,就没有碰撞。
(https://i.stack.imgur.com/QJ63q.png)
最后,我们可以返回一些值来解决碰撞,最简单的方法是返回碰撞的重叠(从矢量dist magnitude中减去半径)和碰撞的轴,它的向量d。如果需要,交点是向量Z。
只是这个线程的一个补充… 下面是pahlevan发布的代码版本,但针对c# /XNA,并做了一些整理:
/// <summary>
/// Intersects a line and a circle.
/// </summary>
/// <param name="location">the location of the circle</param>
/// <param name="radius">the radius of the circle</param>
/// <param name="lineFrom">the starting point of the line</param>
/// <param name="lineTo">the ending point of the line</param>
/// <returns>true if the line and circle intersect each other</returns>
public static bool IntersectLineCircle(Vector2 location, float radius, Vector2 lineFrom, Vector2 lineTo)
{
float ab2, acab, h2;
Vector2 ac = location - lineFrom;
Vector2 ab = lineTo - lineFrom;
Vector2.Dot(ref ab, ref ab, out ab2);
Vector2.Dot(ref ac, ref ab, out acab);
float t = acab / ab2;
if (t < 0)
t = 0;
else if (t > 1)
t = 1;
Vector2 h = ((ab * t) + lineFrom) - location;
Vector2.Dot(ref h, ref h, out h2);
return (h2 <= (radius * radius));
}
也许有另一种方法来解决这个问题,使用坐标系的旋转。
通常,如果一个线段是水平的或垂直的,这意味着平行于x轴或y轴,交点的求解很容易,因为我们已经知道交点的一个坐标,如果有的话。剩下的显然是用圆的方程找到另一个坐标。
受此启发,我们可以利用坐标系旋转,使一个轴的方向与线段的方向重合。
让我们以圆x^2+y^2=1和线段P1-P2为例,P1(-1.5,0.5)和P2(-0.5,-0.5)在x-y系统中。下面的方程提醒你旋转的原理,其中是逆时针方向的角度,x'-y'是旋转后的方程组:
x'=x*cos () + y*sin () y' = - x*sin () + y*cos ()
和反向
X = X ' * cos - y' * sin Y = x' * sin + Y ' * cos
考虑P1-P2方向(用-x表示为45°),我们可以取=45°。将第二个旋转方程转化为x-y系统中的圆方程:x^2+y^2=1,经过简单的运算,我们得到x'-y'系统中的“相同”方程:x'^2+y'^2=1。
利用第一个旋转方程=> P1(-根号(2)/2,根号(2)),P2(-根号(2)/ 2,0),线段端点变成x'-y'系统。
假设交点为p,在x'-y'中,Px = -根号2 /2。使用新的圆方程,我们得到Py = +根号(2)/2。将P转换成原始的x-y系统,最终得到P(-1,0)
为了实现这个数值,我们可以先看看线段的方向:水平,垂直或不垂直。如果它属于前两种情况,很简单。如果是最后一种情况,应用上述算法。
为了判断是否有交集,我们可以将解与端点坐标进行比较,看看它们之间是否有一个根。
我相信只要我们有了它的方程,这个方法也可以应用于其他曲线。唯一的缺点是,我们应该在x'-y'坐标系下解方程,这可能很难。
我发现这个解决方案似乎比其他一些解决方案更容易遵循。
采取:
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];
}
}
我希望这能有所帮助!
附注:如果任何人发现任何错误或有任何建议,请评论。我是新手,欢迎大家的帮助/建议。
这里你需要一些数学知识:
假设A = (Xa, Ya), B = (Xb, Yb), C = (Xc, Yc)。从A到B的直线上的任意一点都有坐标(*Xa + (1-)Xb, * ya + (1-)*Yb) = P
如果点P的距离是R到C,它一定在圆上。你想要的是解决
distance(P, C) = R
这是
(alpha*Xa + (1-alpha)*Xb)^2 + (alpha*Ya + (1-alpha)*Yb)^2 = R^2
alpha^2*Xa^2 + alpha^2*Xb^2 - 2*alpha*Xb^2 + Xb^2 + alpha^2*Ya^2 + alpha^2*Yb^2 - 2*alpha*Yb^2 + Yb^2=R^2
(Xa^2 + Xb^2 + Ya^2 + Yb^2)*alpha^2 - 2*(Xb^2 + Yb^2)*alpha + (Xb^2 + Yb^2 - R^2) = 0
如果你将abc公式应用到这个方程来求解,并使用alpha的解来计算P的坐标,你会得到交点,如果存在的话。