Circle and line segment collision

Question

What is a good algorithm to use to check whether the line intersects the circle? And at what coordinate along the circles edge it occurred?

Answer 1

Using the math from this link, here is a function that returns all intersection points. The input is the center point and radius for the circle and for the line the elevation m and y-axis offset c.

Adding to the linked math solution I have added code for vertical lines. For these set m = float.PositiveInfinity; and c = y-offset (i.e. the x-coordinate of the line)!

List<PointF> Intersections(PointF cc, float r, float m, float c)
{
    List<PointF> points = new List<PointF>();
    // vertical lines: 
    if (float.IsPositiveInfinity(m))
        {
            float b = (float) Math.Sqrt(r * r + (c - cc.X) * (c - cc.X));
            points.Add(new PointF(c, cc.Y + b));
            points.Add(new PointF(c, cc.Y - b));
            return points;
        }

    float A = (m * m + 1f);
    float B = 2*(m * c - m * cc.Y - cc.X);
    float C = cc.Y * cc.Y  - r * r  + cc.X * cc.X - 2f * c * cc.Y + c * c;
    float disc =  B * B - 4f * A * C;
    if (disc < 0) return points;
    float x1 = (float)(-B - Math.Sqrt(disc)) / 2f / A;
    float y1 = m * x1 + c;
    points.Add(new PointF(x1, y1));
    if (disc != 0)
    {
        float x2 = (float)(-B + Math.Sqrt(disc)) / 2f / A;
        float y2 = m * x2 + c;
        points.Add(new PointF(x2, y2));
    }
    return points;
}

Here is an overload for the two-point form of the line:

List<PointF> Intersections(PointF cc, float r, PointF p1, PointF p2)
{
    float m = 0; float c = 0;
    if (p1.X == p2.X) { m = float.PositiveInfinity; c = p1.X; }
    else              { m = (p2.Y - p1.Y) / (p2.X - p1.X);c = p1.Y - m * p1.X; }
    return Intersections(cc, r, m, c);
}

Here is a small testbed using an empty Form :

float radius = 200;           PointF center = new PointF(480,360);
PointF pt1 = PointF.Empty;    PointF pt2 = PointF.Empty;
List<PointF> pointsM = new List<PointF>();

private void Form1_MouseMove(object sender, MouseEventArgs e)
{   
    if (e.Button == MouseButtons.Left)
    {   // drag around and watch the points
        pt2 = e.Location;
        pointsM = Intersections(center, radius, pt1, pt2, false);
        Invalidate();
    }
}

private void Form1_MouseClick(object sender, MouseEventArgs e)
{   // right-click to set the first point
    if (e.Button == MouseButtons.Right) pt1 = e.Location;
    Invalidate();
}

private void Form1_Paint(object sender, PaintEventArgs e)
{
    e.Graphics.DrawEllipse(Pens.Blue, center.X - radius, center.Y - radius, 
                           radius * 2, radius * 2);
    e.Graphics.DrawLine(Pens.Green, pt1, pt2);
    e.Graphics.FillEllipse(Brushes.Blue, center.X - 4, center.Y - 4, 8, 8);
    foreach (PointF pt in pointsM)
        e.Graphics.FillEllipse(Brushes.DarkOrange, pt.X - 4, pt.Y - 4, 8, 8);
    e.Graphics.FillEllipse(Brushes.Green, pt1.X - 4, pt1.Y - 4, 8, 8);
    e.Graphics.FillEllipse(Brushes.DeepPink, pt2.X - 4, pt2.Y - 4, 8, 8);
    Text = pointsM.Count + " intersection points.";
}

Answer 2

Calculate the distance between the center of the circle and the line as described here.

Check if the closest point is between the endpoints of the line segment. If it is between them, check if distance is smaller than radius; otherwise check if one of the edge points is inside the circle.