如何确定直线和圆之间的交点？

Question

我在圆圈内有一个点,在圆圈外有另一个点.我想找到线与圆相交的点.我怎么能在Windows Phone 8中这样做.请给我任何想法.

Answer 1

这既是一个简单而复杂的问题,很大程度上取决于你的意思.我从你的开场发帖中得知你所说的线段而不是真正的(无限)线.

在这种情况下,你有几个案例需要解决.交点仅在一个点位于圆内并且一个点位于圆外时发生.下面的算法没有捕捉到的情况

1. 该线与圆相切
2. 一个或两个点正好在圆圈上
3. 该线在两点相交

这些都集中在"无交叉"结果中.这仅处理内部严格一个点和圆外一个点的情况.

首先,您需要一些辅助功能.这些使用基本几何来确定点是在圆内还是在圆外(圆上的点被计为"外"),以及两个点是否形成与圆相交的线段.

private bool IsInsideCircle(Point CirclePos, float CircleRad, Point checkPoint)
{
    if (Math.Sqrt(Math.Pow((CirclePos.X - checkPoint.X), 2) +
                  Math.Pow((CirclePos.Y - checkPoint.Y), 2)) < CircleRad)
    { return true; } else return false;
}

private bool IsIntersecting(Point CirclePos, float CircleRad, Point LineStart, 
                                                              Point LineEnd)
{
    if (IsInsideCircle(CirclePos, CircleRad, LineStart) ^
        IsInsideCircle(CirclePos, CircleRad, LineEnd)) 
    { return true; } else return false;
}

注意使用^(异或) - 我们希望内部有一个点,外部有一个点.

有了这个,我们可以发挥更大的作用:

private int Intersect (Point CirclePos, float CircleRad, 
                       Point LineStart, Point LineEnd, ref Point Intersection)
{
    if (IsIntersecting(CirclePos, CircleRad, LineStart, LineEnd)) 
    {
        //Calculate terms of the linear and quadratic equations
        var M = (LineEnd.Y - LineStart.Y) / (LineEnd.X - LineStart.X);
        var B = LineStart.Y - M * LineStart.X;
        var a = 1 + M*M;
        var b = 2 * (M*B - M*CirclePos.Y - CirclePos.X);
        var c = CirclePos.X * CirclePos.X + B * B +  CirclePos.Y * CirclePos.Y -
                CircleRad * CircleRad - 2 * B * CirclePos.Y;
        // solve quadratic equation
        var sqRtTerm = Math.Sqrt(b * b - 4 * a * c);
        var x = ((-b) + sqRtTerm)/(2*a);
        // make sure we have the correct root for our line segment
       if ((x < Math.Min(LineStart.X, LineEnd.X) || 
          (x > Math.Max(LineStart.X, LineEnd.X)))) 
        { x = ((-b) - sqRtTerm) / (2 * a); }
        //solve for the y-component
        var y = M * x + B;
        // Intersection Calculated
        Intersection = new Point(x, y);
        return 0;
    } else {
        // Line segment does not intersect at one point.  It is either 
        // fully outside, fully inside, intersects at two points, is 
        // tangential to, or one or more points is exactly on the 
        // circle radius.
        Intersection = new Point(0, 0);
        return -1;
    }            
}

此函数将交点作为ref参数并返回-1(无交点)或0(找到交点).我使用了一个int返回值,以防你想扩展它以区分边缘情况.交点是从基本几何计算的 - 记住一条线表示为(参见:坡度截距和坡度坡度表格)

• y = M*x + B.

和圆(以(C.x, C.y)半径为中心r)是

• (x-Cx)^ 2 +(y-Cy)^ 2-r ^ 2 = 0

你通过替换来解决这个方程组:

• (x-Cx)^ 2 +((M*x + B)-Cy)^ 2-r ^ 2 = 0

扩展和收集您获得的条款:

• (1 + M ^ 2)x ^ 2 + 2*(M*B - M*Cy - Cx)x +(Cx ^ 2 + Cy ^ 2 + B ^ 2 - r ^ 2 - B*Cy)= 0

这是形式的标准二次方程

• ax ^ 2 + bx + c = 0
• 其中:
• a =(1 + M ^ 2)
• b = 2*(M*B - M*Cy - Cx)
• c =(Cx ^ 2 + Cy ^ 2 + B ^ 2 - r ^ 2 - B*Cy)

这可以通过二次公式求解(参见:二次公式):

• x =( - b±Sqrt(b ^ 2 - 4ac))/(2a)

这为我们的线段所在的无限线提供了两个根 - 我们在上面进行最后检查,以确保我们为特定线段选择解决方案.

这就是为什么在数学课上注意很重要!

现在......取决于你在做什么,有很多方法可以优化它.上面的解决方案概述了基本方法,但是如果需要的话,当然可以更快地完成这项工作.显然,参数可以根据您使用的任何类型的点或对象进行调整.我试图让它尽可能一般.

另外,要显示如何调用它的示例:

Point iPt = new Point();

var rslt = Intersect(new Point(2,3), 5.0f, new Point(2,2), 
                     new Point(8,6), ref iPt);

if (rslt == 0) {
    MessageBox.Show(String.Format("Intersection at: x = {0}, y = {1}",
                                   iPt.X, iPt.Y));
} 
else {
    MessageBox.Show("No Intersection");
}