Get location of vector/circle intersection?

Let's set up an equation to find both points of intersection between a line and a circle, but do it in a way that makes it easy to tell which one (if either) lies between the terminating point and the starting point of your vector.

Suppose our equation of the circle is this:

$$ (x-h)^2 + (y-k)^2 = r^2 $$

where the center is $(h,k)$ and radius $r$.

Your vector will have a starting point $(x_0,y_0)$ and a terminating point $(x_1,y_1)$. The points along the line through these two points will be given in parametric form by:

$$ x(t) = (x_1-x_0)t + x_0 $$ $$ y(t) = (y_1-y_0)t + y_0 $$

where $t$ is a real number. More specifically those points strictly between the starting and terminating points correspond to values $0 \lt t \lt 1$.

Now if we substitute for $x,y$ in the equation of the circle the parameterized expressions, we get a quadratic equation in $t$. Generally a quadratic equation might have two or fewer real roots, but if it were the case that the starting point is outside the circle and the terminating point is inside the circle, then there would be exactly two real roots. The "entry" point would correspond to a root $t$ between $0$ and $1$, and the "exit" point to a root greater than $1$.

$$ ((x_1-x_0)t + x_0 - h)^2 + ((y_1-y_0)t + y_0 - k)^2 = r^2 $$

After collecting terms we have a real quadratic equation:

$$ a t^2 + b t + c = 0 $$

where:

$$ a = (x_1-x_0)^2 + (y_1-y_0)^2 $$ $$ b = 2(x_1-x_0)(x_0-h) + 2(y_1-y_0)(y_0-k) $$ $$ c = (x_0-h)^2 + (y_0-k)^2 - r^2 $$

and the roots for $t$ may be found in the usual quadratic form:

$$ t = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} $$

Certainly $a$ will be positive (if the two points that start and terminate the vector are distinct), and $c$ will be positive if the starting point lies outside the circle. As before, we are hoping to find a root between $0$ and $1$. Since the root we want is the smaller of two positive roots (assuming all the geometry is correct), we would want the minus sign on the square root if the vector is where it should be (and $b$ should be negative).

It is worthwhile to use the alternative quadratic formula in this case:

$$ t = \frac{2c}{-b + \sqrt{b^2 - 4ac}} $$

where the proper choice of sign has been made in a way that avoids error of "cancellation".

From a good programming perspective the discriminant $b^2 - 4ac$ needs to be checked to be positive, and also a final check that $0 < t < 1$. If these conditions are not true, something has gone wrong.

Plugging root $t$ back into the parametric form of the line gives the desired point of intersection $(x(t),y(t))$.

So you know the center $(a,b)$ and radius $r$ of a circle and have a line segment with end points $(0,0)$ outside and $(c,d)$ inside the circle? The points on the line have the form $(tc,td)$ with $t\in\mathbb R$ (and with $0\le t\le 1$ if the point is to be on the line segment only, not the infinite line). The squared distance from the circle center is given (per Pythagoras) by $(tc-a)^2+(td-b)^2$ and shall equal $r^2$. Thus we have a quadratic equation $$ (c^2+d^2)t^2-(2ac+2bd)t+(a^2+b^2-r^2)=0.$$ Solving for $t$ we find two solutions $$t_{1,2}=\frac{(ac+bd)\pm\sqrt{(ac+bd)^2-(c^2+d^2)(a^2+b^2-r^2)}}{(c^2+d^2)}. $$ By what we are given there must be one slolution with $t<1$ and one with $t>1$, especially the radicand cannot be negative (as that would corresond to the line not intersecting the circle at all). So the intersection point "before" $(a,b)$ must correspond to the negative sign and hence it is at $$\left(\tfrac{(ac+bd)-\sqrt{(ac+bd)^2-(c^2+d^2)(a^2+b^2-r^2)}}{(c^2+d^2)}\cdot c,\tfrac{(ac+bd)-\sqrt{(ac+bd)^2-(c^2+d^2)(a^2+b^2-r^2)}}{(c^2+d^2)}\cdot d\right). $$

Assuming that the start end end point of your vector are different from the origin $(0, 0)$, you could transform the coordinates in such a way that the center of the circle is the origin and apply the Circle-Line Intersection calculation of WolframMathWorld. The coordinate transform just subtracting the center coordinates from the vector coordinates.

If you are in 2D vector form the equations above can be represented as vectors by using origin O and direction of a ray D, where |D| must be strongly positive for the ray to intersect the circle. Let's say that the circle center is at position vector M and its radius is R. First, you need to define the vector from the center of the circle being M to the ray origin O:

OM = O - M (O and M are position vectors)

In vector form you can define the quadratic equation coefficients like follows ( ^ means to the power of, dot means dot product between two 2D vectors ):

A = |D|^2
B = 2 * D dot OM
C = |OM|^2 - R^2

Now we can calculate the discriminant: Q = B^2 - 4*A*C

If the given value is negative, there is no intersection if the value is zero, you have one root and one intersection as two roots for two intersection points. Store the value of G = 1/(2*A) in a variable it will become in handy later. Now calculate the determinant Q = G*sqrt(Q) and update the value of B = (-B * G)

Now we are ready to calculate the intersection points. Let's call them P1 and P2 where we will have an equation as follows where B and Q are number scalars:

P1 = D * (B + Q) + O
P2 = D * (B - Q) + O

The closest intersection point to the ray origin is P2 and the distant one is P1