views:

5461

answers:

10

I have a line from A to B and a circle positioned at C with the radius R. This is in two dimensions.

Which is a good algorithm to use to check whether the line intersects the circle? And at what coordinate along the circles edge it occurred?

+2  A: 

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:
http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

Martin
It's in 2D, not 3D; as you say, this doesn't really matter
Martijn
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
+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
Jason S
I explained a little better about the closest point, and linked to mathworld instead of pbourke :)
Martin
pbourke is KING
bobobobo
+8  A: 

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!

a_m0d
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
cool, glad to be of help
a_m0d
which is exactly what I said, but never mind :P
Martin
Ok, c is unknown in your equation, but what is "a"? The other answers seem to refer to that variable as "alpha" and "t". Although, this is just a linear function (y=kx+m), quite basic math, so I suddenly feel a bit rusty. Isnt k also unknown? Or do you mean we can assume m=0 and solve k? Wouldnt then m (that is, c) always be zero for our solved k?
mizipzor
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
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
I suggest another method below (with code) that uses the triangle area to compute the distance of the circle center to the line.
chmike
+2  A: 

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 0<=t<=1

and the circle is

(C.x - x)^2 + (C.y - 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.

Gábor Hargitai
+3  A: 

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.

Martijn
+4  A: 

No one seems to consider projection, am I completely off track here?

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.

mizipzor
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
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
+2  A: 

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 < 0 || t > 1)
    {
    // intersection point is not actually within line segment
    }
  }
else if (dist < R)
  {
  // two possible intersection points

  dt = sqrt(R * R - dist * dist) / sqrt(dl);

  // intersection point nearest to A
  t1 = t - dt;
  i1X = aX + t1 * dX;
  i1Y = aY + t1 * dY;
  if (t1 < 0 || t1 > 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 < 0 || 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.

Juozas Kontvainis
You missed one case since we are talking about a line segment: when the segment ends in the circle.
ADB
@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
+17  A: 
bobobobo
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
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
See also http://www.cs.stevens.edu/~quynh/courses/cs537-notes/lesson2-RayTracingIntersections.ppt
bobobobo
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
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
Can someone fully explain how we're going from (x - h)^2 + (y - k)^2 = r^2 to t^2 * (d DOT d) + (2t * (f DOT d)) + (f DOT f - r^2) = 0? I tried plugging in the parametric equivalent of x and y and got something I couldn't reduce. Thanks very much.
Jason
+3  A: 

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 <= t <= 1.

// compute the value t of the closest point to the circle center
t = Dx*(Cx-Ax) + Dy*(Cy-Ax)

// This is the projection of C on the line from A to B.

// compute the coordinates of the point E on line and closest to C
Ex = t*Dx+Ax
Ey = t*Dy+Ay

// compute the euclidean distance from E to C
LEC = sqrt( (Ex-Cx)²+(Ey-Cy)² )

// test if the line intersects the circle
if( LEC < R )
{
    // compute distance from t to circle intersection point
    dt = sqrt( R² - LEC²)

    // compute first intersection point
    Fx = (t-dt)*Dx + Ax
    Fy = (t-dt)*Dy + Ay

    // compute second intersection point
    Gx = (t+dt)*Dx + Ax
    Gy = (t+dt)*Dy + Ay
}

// else test if the line is tangent to circle
else if( LEC == R )
    // tangent point to circle is E

else
    // line doesn't touch circle
chmike
+4  A: 

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 b 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 < R )
{
    ...
}

UPDATE 1 :

You could optimize the code by using the fast inverse square root computation described here to get a good approximation of 1/LAB.

Computing the intersection point is not that difficult. Here it goes

// compute the line AB direction vector components
Dx = (Bx-Ax)/LAB
Dy = (By-Ay)/LAB

// compute the distance from A toward B of closest point to C
t = Dx*(Cx-Ax) + Dy*(Cy-Ax)

// t should be equal to sqrt( (Cx-Ax)² + (Cy-Ay)² - h² )

// compute the intersection point distance from t
dt = sqrt( R² - h² )

// compute first intersection point coordinate
Ex = Ax + (t-dt)*Dx
Ey = Ay + (t-dt)*Dy

// compute second intersection point coordinate
Fx = Ax + (t+dt)*Dx
Fy = Ay + (t+dt)*Dy

If h = R then the line AB is tangent to the circle and the value dt = 0 and E = F. 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.

chmike
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
+1  A: 

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 < 0.0) 
     t = 0.0;
    else 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;
}
pahlevan