Finding Intersections Between Circles and Lines: A Programmer's Guide

[Pazil]

Hi!

I'm new to these forums, and a grade 10 Flash programmer. I'm currently building a collision detection library, with which I currently have Lines and Circles.

My problem is that I don't know how to get the intersection points between a circle and a line. I'm using mx+b for the line, in other words infinite lines. I already have intersection with the equation x^2 + y^2 = r^2 good to go, but I have no idea how to translate this into:
(x - h)^2 + (y - k)^2 = r^2, in other words add coordinates to the intersection calculation. I only need the calculations up to the point where I can get A, B, and C variables for the quadratic formula (from then on it's simple plugging in).

Any help what so ever is greatly appreciated! I just found these forums, and it seems as though I'll be in heaven from now on!

P.

 

[yyat]

If you define new coordinates (by translation):

x1 = x-h
y1 = y-k

then you have reduced to the case you already know (center at origin):

x1^2 + y1^2 = r^2

y1+k=m(x1+h)+b, i.e y1=mx1+(b+mh-k)

Compute the intersection and convert the result back to (x,y)-coordinates.

 

[Pazil]

Alright, I'll try that!

Thank you!

Edit:

I'm still a bit confused, since I have no idea how to get that into Ax^2 + Bx + C = 0 form...?
I get to (1 + m^2)x1^2 + (b + mh - k)^2 = r^2
But I don't see how to get a B for Bx, since there's no x1 terms.

 

[HallsofIvy]

Then B= 0. In fact, that form is particularly easy to solve. If $ax^2+ bx+ c= 0$ and b= 0, $ax^2+ c= 0$ or $ax^2= -c$ so $x^2= -c/a$ which has real roots if and only if -c/a is non-negative and in that case $x= \pm\sqrt{-c/a}$.

 

[Pazil]

Alright then. I guessed that much, and I realized that B would then be excluded, but I just don't understand how this form, which includes the x/y coordinates factors to only:
Ax^2 + c = 0
When if you do:

x^2 + y^2 = r^2
y = mx + b

x^2 + (mx+b)^2 = r^2

(1+m^2)x^2 + 2mbx + b^2 - r^2 = 0
Therefore:
A = 1+m^2
B = 2mb
C = b^2 - r^2

I realize that it has to do with assigning x1 = x - h and same for the y, but I just don't understand how you would factor it still...I mean, I do, but...I hate when I do something in Math, and I don't understand what's happening.
Please go easy on me, since I'm in grade 10 (I mean, not easy...but just, explain a bit more please?)

P.

 

[yyat]

(1+m^2)x^2 + 2mbx + b^2 - r^2 = 0
Therefore:
A = 1+m^2
B = 2mb
C = b^2 - r^2

That is correct.

I get to (1 + m^2)x1^2 + (b + mh - k)^2 = r^2

Here you forgot the 2mx1(b+mh-k) term.

 

[Pazil]

Well, I apologize for the seemingly empty posts I've been writing, but I haven't had enough time to totally just sit down and work out the things you threw at me.
I tried to collect all like terms again, and this is what I got (Ax^2 + Bx + C = 0):

(1 + m^2)x^2 + (-2h + 2bm - 2km)x + h^2 + b^2 - 2kb + k^2 - r^2 = 0
This is from (x - h)^2 + (mx+b - k)^2 = r^2

Does it look alright to you guys?

P.

 

[bpet]

Well, I apologize for the seemingly empty posts I've been writing, but I haven't had enough time to totally just sit down and work out the things you threw at me.
I tried to collect all like terms again, and this is what I got (Ax^2 + Bx + C = 0):

(1 + m^2)x^2 + (-2h + 2bm - 2km)x + h^2 + b^2 - 2kb + k^2 - r^2 = 0
This is from (x - h)^2 + (mx+b - k)^2 = r^2

Does it look alright to you guys?

P.

Looks good :) It's also good to test the solution by plugging in a few values for m,b,etc and see if the solutions satisfy the equations of the line and the circle.

How do the results change if the line is expressed as ax+by+c=0 (this includes the vertical line when b=0).

 

[Pazil]

I just tested in my collision engine and it works perfectly also!

How would I plugin in the ax + by + c = 0 into the (x - h)^2 + (y - k)^2 = r^2 equation?
Supporting vertical lines would of course be a big bonus!

P.

Or, how could I parametrize this, so that x becomes a function of t?

 

[yyat]

How would I plugin in the ax + by + c = 0 into the (x - h)^2 + (y - k)^2 = r^2 equation?
Supporting vertical lines would of course be a big bonus!

I think that at some point you will have to distinguish between two cases. If b is nonzero in ax+by+c you can solve for y in terms of x. In the other case you could just temporarily switch the x and y coordinates.

 

[Pazil]

I thought of that just after I posted!

I'm going to try to parametrize my line equations by myself, but I'll definitely need help for parametric circles vs. lines and circles vs. circles...

P.

By the way, in some equations, I spot this: x = 2[ y + jh - 5] or something...what does the 2[] mean? I'm guessing it's just like normal brackets?