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.
$\endgroup$ 25 Answers
$\begingroup$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))$.
$\endgroup$ 6 $\begingroup$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). $$
$\endgroup$ 2 $\begingroup$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.
$\endgroup$ $\begingroup$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^2Now 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) + OThe closest intersection point to the ray origin is P2 and the distant one is P1
Line – Circle Points of Intersection using Mirrored Circles Intersection
This problem can also be solved using a combination of techniques which, if you are attempting this problem, you may have already implemented programmatically. The basic idea is to mirror the circle around the line, and then find the intersection of the original and mirrored circles.
Now the dance...
First, you need your line's equation in standard form which looks like this:$$ax + by + c = 0;$$
If you know two points, it can be calculated from this equation:$$a = y_1 – y_2$$$$b = x_2 – x_1$$$$c = x_1y_2 – x_2y_1$$
Next, determine the equation of a line containing the center of the circle and another point which is perpendicular to the original line. This is oddly (or not) straight forward. Simply add ‘a’ from the original line's equation to the center’s x coordinate and ‘b’ to the center’s y coordinate and you have your second point ($P_2$) to determine the perpendicular line’s equation (the center being the first point).$$ P_2x = C_{orig}x + a_1$$$$ P_2y = C_{orig}y + b_1$$
After that, find the intersection of the two lines:$$z = a_1b_2 – a_2b_1$$$$x_{int} = (b_1c_2 – b_2c_1)/z$$$$y_{int} = (a_2c_1 - a_1c_2)/z$$This provides the point to mirror the coordinates of the original circle around.
Now find the difference between the center and intersection and add it to the intersection. This gives you the coordinates of the mirrored circle.$$ dx = x_{int}-C_{orig}x$$$$ dy = y_{int}-C_{orig}y$$$$ C_{mirror}x = C_{orig}x + 2dx$$$$ C_{mirror}y = C_{orig}y + 2dy$$
Finally, finding the intersections of the two circles will yield the intersection of the original line and circle.
Equation of intersection of two circles (from here):$$ (x,y)=\frac{1}{2}(x_1+x_2,y_1+y_2)+ \frac{r_1^2−r_2^2}{2R^2} (x_2−x_1,y_2−y_1)± \sqrt{\frac{r_1^2+r_2^2}{2R^2}−\frac{(r_1^2-r_2^2)^2}{4R^4}-\frac{1}{4}} (y_2−y_1,x_1−x_2)$$Where R is the distance between the centers of the circles.
Since the two radii are equal, the equation shortens to:$$ (x,y)=\frac{1}{2}(x_1+x_2,y_1+y_2)± \sqrt{\frac{r_1^2+r_2^2}{2R^2}-\frac{1}{4}} (y_2−y_1,x_1−x_2)$$
Some substitutions and equation massaging results in:$$(x,y)= (x_{int},y_{int}) ± \sqrt{\frac{r^2}{dx^2 + dy^2} - 1} (dy, -dx)$$
$\endgroup$ 1
