Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Probably the best approach is to check both intersection points until you find the one that lies in the proper direction in the line through the vector, i.e. behind the termination point. Of course knowing the termination point is inside the circle is only half the criteria; the starting point needs to lie outside the circle. –  hardmath Feb 23 '13 at 12:20
    
So, in fact, of that "vector" the only thing important to you is that it is a straigh line segment (anchored at the origin, I presume...?), and you only want to know where that straight segment intersects your circle...right? –  DonAntonio Feb 23 '13 at 12:21

3 Answers 3

up vote 3 down vote accepted

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))$.

share|improve this answer
    
This may actually work. You've explained it well enough that even a math n00b like me can understand what's going on (and coders do so like breaking things into steps), and thanks to a little optimization it could be sufficiently fast. –  DigitalMan Feb 23 '13 at 13:29
    
There's a factor of 2 that cancels out, but I thought it not worth trying to mention. You'll see it when you go to code things up. –  hardmath Feb 23 '13 at 14:23
    
Alright, this almost works, except t (which seems to basically be a ratio describing how far along the line the intersection is) isn't quite enough to make the distance from x(t),y(t) greater than or equal to r. Debug readout says the end distance is short by around 0.0000003 units. Not sure if I failed at the math, or if it's a floating-point rounding issue... –  DigitalMan Feb 28 '13 at 18:57
    
If your floating point datatype is single precision, rounding error would account for that discrepancy. –  hardmath Feb 28 '13 at 21:28

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). $$

share|improve this answer
    
Oh dear, I think I hear my phone's processor weeping. Is there perhaps a way to simplify that? As it stands, that's more computationally intensive than the quick hack I've rejected for being too computationally intensive. –  DigitalMan Feb 23 '13 at 12:46
    
If you are just interested in an approximate solution, you could iterate pixel-by-pixel from start to end of your vector and check wether the point is in the circle or not. –  Axel Kemper Feb 23 '13 at 13:00

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.