Circle line collision detection?

If E is the starting point of the ray, .. and L is the end point of the ray, .. and C is the center of sphere you're testing against .. and r is the radius of that sphere Compute: d = L - E ; // Direction vector of ray, from start to end f = E - C ; // Vector from center sphere to ray start Then the intersection is found by.. Plugging: P = E + t * d (this is a parametric equation: Px = Ex + tdx Py = Ey + tdy ) into (x - h)2 + (y - k)2 = r2 (( (h,k) = center of circle. Note: we've simplified the problem to 2D here, the solution we get applies in 3D however )) to get: 1. Expand x2 - 2xh + h2 + y2 - 2yk + k2 - r2 = 0 2.

Plug x = ex + tdx y = ey + tdy ( ex + tdx )2 - 2( ex + tdx )h + h2 + ( ey + tdy )2 - 2( ey + tdy )k + k2 - r2 = 0 3. Explode ex2 + 2extdx + t2dx2 - 2exh - 2tdxh + h2 + ey2 + 2eytdy + t2dy2 - 2eyk - 2tdyk + k2 - r2 = 0 4. Group t2( dx2 + dy2 ) + 2t( exdx + eydy - dxh - dyk ) + ex2 + ey2 - 2exh - 2eyk + h2 + k2 - r2 = 0 5.

Finally, t2( _d * _d ) + 2t( _e * _d - _d * _c ) + _e * _e - 2( _e*_c ) + _c * _c - r2 = 0 ** Where _d is the vector d and * is the dot product. 6. And then, t2( _d * _d ) + 2t( _d * ( _e - _c ) ) + ( _e - _c ) * ( _e - _c ) - r2 = 0 7.So letting _f = _e - _c t2( _d * _d ) + 2t( _d * _f ) + _f * _f - r2 = 0 So we get: t2 * (d DOT d) + 2t*( f DOT d ) + ( f DOT f - r2 ) = 0 So solving the quadratic equation: float a = d.

Dot( d ) ; float be = 2*f. Dot( d ) ; float c = f. Dot( f ) - r*r ; float discriminant = b*b-4*a*c; if( discriminant = 0 && t1.

Seems to work if I do straight copy and paste, but Im looking to understand it to. In (x-h)^2+(y-k)^2=r^2 what is h and k? Is k to constant by which the line/ray increases on y over x?

And what is t? Looking at the code it seems you have assumed its 1 (so its just "removed"). Do these formulas have a name or something?

Maybe I can look them up in detail on Wolfram. – mizipzor Jul 6 '09 at 12:17 2 h and k are the center of the circle that you're intersecting against. T is the parameter of the line equation.In the code, t1 and t2 are the solutions.

T1 and t2 tell you "how far along the ray" the intersection happened. – bobobobo Jul 6 '09 at 13:22 1 See also cs.stevens.Edu/~quynh/courses/cs537-notes/… – bobobobo Jul 6 '09 at 19:22 Very elegant solution that requires only one square root computation and should in principle work in 3D. What would be the 3D equation and how do we find the roots?

– chmike Jul 10 '09 at 6:17 Ok, got it. The dot product is simply computed over the three elements (x,y,z) vectors. I will switch my code to this algorithm.

– chmike Jul 10 '09 at 6:23.

Okay, I won't give you code, but since you have tagged this algorithm, I don't think that will matter to you. First, you have to get a vector perpendicular to the line. You will have an unknown variable (y = ax + c; c will be unknown) - to solve for this, calculate its value when the line passes through the center of the circle (i.e.

Plug in the location of the circle center to the line equation and solve for c). Then calculate the intersection point of the original line and its normal. This will give you the closest point on the line to the circle.

Calculate the distance between this point and the circle center (using the magnitude of the vector) and if this is less than the radius of the circle - voila, we have an intersection!

1 That was, in fact, what I wanted. I want the theory, a google search of line-circle collision algorithm turns up only code as far as I can see. – mizipzor Jul 2 '09 at 9:25 cool, glad to be of help – a_m0d Jul 2 '09 at 9:27 which is exactly what I said, but never mind :P – Martin Jul 2 '09 at 10:24 1 Oh, sorry - I am using the simple equation of a line with a gradient and offset (the cartesian equation).

I assumed that you were storing the line as such an equation - in which case you use the negative of the gradient for k. If you don't have the line stored like this, you could calculate k as (y2-y1)/(x2-x1) – a_m0d Jul 3 '09 at 21:22 1 We don't assume that m is zero; we calculate the gradient first (so that the equation of the line then looks like y=2x+m as an example), and then once we have the gradient we can solve for m by plugging in the center of the circle for y and x. – a_m0d Jul 3 '09 at 21:24.

Project the vector AC onto AB. The projected vector, AD, gives the new point D. If the distance between D and C is smaller than, or equal to, R we have an intersection.

1 I was writing my answer based on that just as you posted this answer :) You are correct, this is a good way to check whether intersection exists. – Juozas Kontvainis Jul 3 '09 at 14:01 There are many details to take into consideration: does D lie between AB? Is C perpendicular distance to the line larger than the radius?

All of these involve magnitude of vector, i.e. Square root. – ADB Sep 1 '10 at 14:42.

I would use the algorithm to compute the distance between a point (circle center) and a line (line AB). This can then be used to determine the intersection points of the line with the circle. Let say we have the points A, B, C.Ax and Ay are the x and y components of the A points.

Same for B and C. The scalar R is the circle radius. Here is the algorithm // compute the euclidean distance between A and B LAB = sqrt( (Bx-Ax)²+(By-Ay)² ) // compute the direction vector D from A to B Dx = (Bx-Ax)/LAB Dy = (By-Ay)/LAB // Now the line equation is x = Dx*t + Ax, y = Dy*t + Ay with 0.

You'll need some math here: Suppose A = (Xa, Ya), B = (Xb, Yb) and C = (Xc, Yc). Any point on the line from A to B has coordinates (alpha*Xa + (1-alpha)Xb, alphaYa + (1-alpha)*Yb) = P If the point P has distance R to C, it must be on the circle. What you want is to solve distance(P, C) = R that is (alpha*Xa + (1-alpha)*Xb)^2 + (alpha*Ya + (1-alpha)*Yb)^2 = R^2 alpha^2*Xa^2 + alpha^2*Xb^2 - 2*alpha*Xb^2 + Xb^2 + alpha^2*Ya^2 + alpha^2*Yb^2 - 2*alpha*Yb^2 + Yb^2=R^2 (Xa^2 + Xb^2 + Ya^2 + Yb^2)*alpha^2 - 2*(Xb^2 + Yb^2)*alpha + (Xb^2 + Yb^2 - R^2) = 0 if you apply the ABC-formula to this equation to solve it for alpha, and compute the coordinates of P using the solution(s) for alpha, you get the intersection points, if any exist.

If you find the distance between the center of the sphere (since it's 3D I assume you mean sphere and not circle) and the line, then check if that distance is less than the radius that will do the trick. The collision point is obviously the closest point between the line and the sphere (which will be calculated when you're calculating the distance between the sphere and the line) Distance between a point and a line: mathworld.wolfram.com/Point-LineDistance....

1 It's in 2D, not 3D; as you say, this doesn't really matter – Martijn Jul 2 '09 at 9:21 I'm no mathematician so I thought I'd be better outlining a general approach and leaving it to others to figure out specific maths (although I does look rather trivial) – Martin Jul 2 '09 at 9:30 1 +1 with a strong upvote. (though I would have linked to another site, the pbourke site looks confusing) All the other answers so far are overcomplicated. Although your comment "That point is also the intersection point on the line" is incorrect, there is no point that has been constructed in the computation process.

– Jason S Jul 2 '09 at 19:03 2 mathworld.wolfram. Com/Point-LineDistance3-Dimensional. Html and mathworld.wolfram.Com/Point-LineDistance2-Dimensional.

Html are better & from a more reputable site – Jason S Jul 2 '09 at 19:05 I explained a little better about the closest point, and linked to mathworld instead of pbourke :) – Martin Jul 2 '09 at 21:19.

Another method uses the triangle ABC area formula. The intersection test is simpler and more efficient than the projection method, but finding the coordinates of the intersection point requires more work. At least it will be delayed to the point it is required.

The formula to compute the triangle area is : area = bh/2 where be is the base length and h is the height. We chose the segment AB to be the base so that h is the shortest distance from C, the circle center, to the line. Since the triangle area can also be computed by a vector dot product we can determine h.

// compute the triangle area times 2 (area = area2/2) area2 = abs( (Bx-Ax)*(Cy-Ay) - (Cx-Ax)(By-Ay) ) // compute the AB segment length LAB = sqrt( (Bx-Ax)² + (By-Ay)² ) // compute the triangle height h = area2/LAB // if the line intersects the circle if( h The point coordinates are those of E and F. You should check that A is different of B and the segment length is not null if this may happen in your application.

1 I like the simplicity in this method. Maybe I could adapt some of the surrounding code to not need the actual collision point itself, Ill see what happens if I use A or B rather than the calculated point in between. – mizipzor Jul 7 '09 at 11:00.

If the line's coordinates are A. X, A. Y and B.

X, B. Y and the circles center is C. X, C.

Y then the lines formulae are: x = A. X * t + B. X * (1 - t) y = A.

Y * t + B. Y * (1 - t) where 0Y - y)^2 = R^2 if you substitute x and y formulae of the line into the circles formula you get a second order equation of t and its solutions are the intersection points (if there are any). If you get a t which is smaller than 0 or greater than 1 then its not a solution but it shows that the line is 'pointing' to the direction of the circle.

You can find a point on a infinite line that is nearest to circle center by projecting vector AC onto vector AB. Calculate the distance between that point and circle center. If it is greater that R, there is no intersection.

If the distance is equal to R, line is a tangent of the circle and the point nearest to circle center is actually the intersection point. If distance less that R, then there are 2 intersection points. They lie at the same distance from the point nearest to circle center.

That distance can easily be calculated using Pythagorean theorem. Here's algorithm in pseudocode: { dX = bX - aX; dY = bY - aY; if ((dX == 0) && (dY == 0)) { // A and B are the same points, no way to calculate intersection return; } dl = (dX * dX + dY * dY); t = ((cX - aX) * dX + (cY - aY) * dY) / dl; // point on a line nearest to circle center nearestX = aX + t * dX; nearestY = aY + t * dY; dist = point_dist(nearestX, nearestY, cX, cY); if (dist == R) { // line segment touches circle; one intersection point iX = nearestX; iY = nearestY; if (t 1) { // intersection point is not actually within line segment } } else if (dist 1) { // intersection point is not actually within line segment } // intersection point farthest from A t2 = t + dt; i2X = aX + t2 * dX; i2Y = aY + t2 * dY; if (t2 1) { // intersection point is not actually within line segment } } else { // no intersection } } EDIT: added code to check whether found intersection points actually are within line segment.

You missed one case since we are talking about a line segment: when the segment ends in the circle. – ADB Sep 1 '10 at 14:47 @ADB actually my algorithm only works for infinite lines only, not line segments. There are many cases that it does not handle with line segments.

– Juozas Kontvainis Sep 2 '10 at 6:52.

This Java Function returns a DVec2 Object. It takes a DVec2 for the center of the circle, the radius of the circle, and a Line. Public static DVec2 CircLine(DVec2 C, double r, Line line) { DVec2 A = line.

P1; DVec2 B = line. P2; DVec2 P; DVec2 AC = new DVec2( C ); AC. Sub(A); DVec2 AB = new DVec2( B ); AB.

Sub(A); double ab2 = AB. Dot(AB); double acab = AC. Dot(AB); double t = acab / ab2; if (t 1.0) t = 1.0; //P = A + t * AB; P = new DVec2( AB ); P.

Mul( t ); P. Add( A ); DVec2 H = new DVec2( P ); H. Sub( C ); double h2 = H.

Dot(H); double r2 = r * r; if(h2 > r2) return null; else return P; }.

Okay, I won't give you code, but since you have tagged this algorithm, I don't think that will matter to you. First, you have to get a vector perpendicular to the line.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.