I'm a coding guru, and I'm good with math – but only math that I know. Which isn't even at calculus level yet. So I'm hoping I can get some help here for my algorithm.
Say I have a circle. I know its radius and location. And I have a vector. I know its values, with functions to swap between Cartesian and polar at will. Now, it being a vector is very important, because its end point has been found somewhere within the radius of the circle, and the program must not concern its self with how the actual line would pass all the way through; one intersection point only here, the "entry point".
I need to locate that one intersection point. It can be a scalar distance to "back-track" along the vector, or raw Cartesian coordinates, with preference on what requires the least computational overhead. The only limit I really have is the complete inability to work with degrees in Java; only radians. I can only guess it's about how one would calculate a secant intersection point. This certainly seems possible, and probably somewhat "elementary" in higher levels… I'm just not there myself.
EDIT: There is a simple hack for this, which involves guess-and-check (via Binary Search Algorithm) on the vector's length until the distance between the circle center and vector end point is "close enough" to the radius. In this particular scenario, needing relatively low precision on already small numbers, I estimate it would take about… half the time of a full quadratic equation. Which is still too long for my liking, which is why I'm hoping actual math has an even better trick.
Best Answer
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))$.