Collision between circle and line

[Aaron]

I'm working on a collision method that detects at what time a moving circle makes contact with a line over the interval [0, 1] (it returns 1.0 if there's no collision).  I'm able to determine whether or not the circle is moving toward the line and if the circle's velocity could ever move itself close enough to the line for there to be collision.  However, I can't figure out how to find the distance the circle would have to go to hit the line, which I'd get my time from.

Here's pseudo code for the part of my method that works.  I assume the line is infinite:

*****

double calculateCollisionTime(Line2D line, Circle circle) {

// Get unit vector of line's normal pointing to side of line circle is on,
// as well as shortest distance between line and circle's centre coordinate.

if (circle.velocityMagnitude() < circle_line_distance - circle.radius())
   return 1.0;

// Get unit vector of circle's velocity.
// Get dot product of circle's unit velocity vector and line's unit normal vector.
// This corresponds to the angle between the circle's velocity and the line.

if (dotprod <= 0) // Circle parallel to or going away from line.
   return 1.0;

// This is the part I'm having trouble with.
// Find distance between circle and line parallel to circle's velocity.  If it's less
// than the circle's velocity, expect a collision.  Divide this distance by the circle's
// velocity to get time.

return time.

}

*****

I have searched on the internet, and the few articles I found didn't help me.  Does anyone here have any suggestions?

Thank you.

[c_lilian]

Here is a usefull resource :

http://www.c-program.com/c-g-a-faq1.html

a "simple" method to find the intersection is :
 - find the point on the circle closest to the line :
     * find the perpendicular projection of the center of the circle on the line
     * draw a line from the center to this point
     * find the point on this line at radius distance from the center.
 - find the intersection of a line going through this point and whith the same direction as the circle speed (line - line intersection : easy)
 
Hope it helps

Lilian

[Aaron]

Thanks for the site, Lilian.

I've been looking at the "distance from a point to a line" part with interest, but what do they mean by "L**2"?  Is that L squared?

Games published by our own members! Check 'em out!

[c_lilian]

Yes

[Aaron]

Thanks.

Anyway, that link you gave me helped me optimize some of my code, but I'm still having problems.

What I'm doing now is look for the possible intersection point on the circle's radius, which is where the line normal would cross if reaching for the circle's centre.  I came up with two ways of calculating the distance between the line and this intersection point parallel to the circle's velocity; one from the web site you gave me Lilian and another site at http://www.gamespp.com/algorithms/collisionDetectionTutorial02.html.

First I get the intersection point:

1   2   3

// Point of possible intersection on ball. double intsect1X = A.x() + (-Nx * A.radius()); double intsect1Y = A.y() + (-Ny * A.radius());

Getting the distance based on the second site:

1   2

double d = (line.getX1() * Nx) + (line.getY1() * Ny); double actDist = d - ((intsect1X * Nx) + (intsect1Y * Ny));

Getting the distance based on the first site:

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18

double intsect2X = A.x() + (-Nx * A.radius()) + A.dx(); double intsect2Y = A.y() + (-Ny * A.radius()) + A.dy(); // Find distance between intersection point on ball and line parallel to ball velocity.         double denom = ((line.getX2() - line.getX1()) * (intsect2Y -  intsect1Y)) - ((line.getY2() - line.getY1()) * (intsect2X - intsect1X));         if (denom == 0) // Lines are parallel.    return 1.0;         double r2 = (((line.getY1() - intsect1Y) * (intsect2X - intsect1X)) - ((line.getX1() - intsect1X) * (intsect2Y - intsect1Y))) / denom;         // Z is intersection point. double Zx = line.getX1() + (r2 * (line.getX2() - line.getX1())) - intsect1X; double Zy = line.getY1() + (r2 * (line.getY2() - line.getY1())) - intsect1Y;         // Distance ball actually has to move. double actDist = Math.sqrt((Zx * Zx) + (Zy * Zy));

Both of these are followed by this:

1   2   3   4

if (dV <= Math.abs(actDist))     return 1.0;         return Math.abs(actDist) / dV;

The problem is first of all that it looks like my line is "one-sided," the ball is only blocked from one side.  It can still pass through the other side.  Even on the side where it's blocked, it seems to be still possible for the ball to pass through if I press the forward key long enough (I'm controlling the ball with the keyboard).