<s>[INST] How do I calculate the intersection(s) of a straight line and a circle? The basic equation for a straight line is $y = mx + b$, where $b$ is the height of the line at $x = 0$ and $m$ is the gradient. The basic equation for a circle is $(x - c)^2 + (y - d)^2 = r^2$, where $r$ is the radius and $c$ and $d$ are the $x$ and $y$ shifts of the center of the circle away from $(0,\ 0)$.
I'm trying to come up with an equation for determining the intersection points for a straight line through a circle. I've started by substituting the "y" value in the circle equation with the straight line equation, seeing as at the intersection points, the y values of both equations must be identical. This is my work so far:
$$(x - c)^2 + (mx + b - d)^2 = r^2$$
$$x^2 + c^2 - 2xc + m^2x^2 + (b - d)^2 + 2mx(b - d) = r^2$$
I'll shift all the constants to one side
$$x^2 - 2xc + m^2x^2 + 2mx(b - d) = r^2 - c^2 - (b - d)^2$$
$$(m^2 - 1)x^2 + 2x(m(b - d) - c) = r^2 - c^2 - (b - d)^2$$
That's as far as I can get. From what I've gathered so far, I ought to be able to break down the left side of this equation into a set of double brackets like so:
$$(ex + f)(gx + h)$$
where $e,\ f,\ g$ and $h$ are all constants. Then I simply have to solve each bracket for a result of $0$, and I have my $x$ coordinates for the intersections of my two equations. Unfortunately, I can't figure out how to break this equation down.
Any help would be appreciated.
 [/INST] Here's an equation which works even if the line is vertical. This is useful from a computer programming perspective. Let's set up the system of equations using standard formulae:
$$ \begin{cases}
(x - x_0)^2 + (y - y_0)^2 = r^2 \\ 
Ax + By + C = 0
\end{cases} $$
where the circle with radius $r$ is centered at $(x_0, y_0)$; the line contains the points $(x_1, y_1)$ and $(x_2, y_2)$.
From the line equation, we know:
$$
y = \frac{-Ax-C}{B} = - \frac{Ax+C}{B}
$$
($B \neq 0$, we'll get into this in a second)
Therefore,
$$ \begin{align*}
(x - x_0)^2 + \left( - \frac{Ax+C}{B} - y_0 \right)^2 &= r^2 \\
x^2 - 2x_0x + {x_0}^2 + \frac{A^2 x^2 + 2ACx + C^2}{B^2} + 2y_0 \cdot \frac{Ax+C}{B} + {y_0}^2 &= r^2 \\
x^2 - 2x_0x + \frac{A^2 x^2 + 2ACx + C^2}{B^2} + 2y_0 \cdot \frac{Ax+C}{B} &= r^2 - {x_0}^2 - {y_0}^2
\end{align*} $$
Multiply both sides by $B^2$.
$$ \begin{align*}
B^2 x^2 - (2B^2 x_0)x + A^2 x^2 + (2AC)x + C^2 + 2By_0(Ax+C) &= B^2(r^2 - {x_0}^2 - {y_0}^2) \\
(A^2 + B^2)x^2 + (2AC - 2B^2 x_0)x + (2AB y_0)x &= -C^2 - 2BCy_0 + B^2(r^2 - {x_0}^2 - {y_0}^2)
\end{align*} $$
Therefore, we have a quadratic equation $ax^2 + bx + c = 0$ with:
$$ \begin{cases}
a = A^2 + B^2 \\
b = 2AC + 2AB y_0 - 2B^2 x_0 \\
c = C^2 + 2BC y_0 - B^2 (r^2 - {x_0}^2 - {y_0}^2)
\end{cases} $$
where
$$ \begin{cases}
A = y_2 - y_1 \\
B = x_1 - x_2 \\
C = x_2 y_1 - x_1 y_2
\end{cases} $$
Now you can use $\{ x = \frac{-b \pm \sqrt{\Delta}}{2a}, y= -\frac{Ax+C}{B} \}$ to solve for the points.

The above equation doesn't work for $B=0$. Besides this, if $|B|$ is too small, then floating point computation gets inaccurate. 
If $B=0$, or is too small, then we let $x = -\frac{By+C}{A}$, and sub it into the circle's formula:
$$ \begin{align*}
\left( - \frac{By+C}{A} - x_0 \right)^2 + (y - y_0)^2 &= r^2 \\
\frac{B^2 y^2 + 2BCy + C^2}{A^2} + 2x_0 \cdot \frac{By+C}{A} + y^2 - 2y_0 y &= r^2 - {x_0}^2 - {y_0}^2 \\
B^2 y^2 + 2BCy + C^2 + 2Ax_0 (By+C) + A^2y^2 - 2A^2 y_0 y &= A^2(r^2 - {x_0}^2 - {y_0}^2) \\
(A^2 + B^2)y^2 + (2BC + 2ABx_0 - 2A^2 y_0)y &= -C^2 - 2ACx_0 + A^2(r^2 - {x_0}^2 - {y_0}^2)
\end{align*} $$
Thus, we have a quadratic equation $ay^2 + by + c = 0$ where
$$ \begin{cases}
a = A^2 + B^2 \\
b = 2BC + 2ABx_0 -2A^2 y_0 \\
c = C^2 + 2ACx_0 -A^2(r^2 - {x_0}^2 - {y_0}^2)
\end{cases} $$
</s>