hey, I'm trying to figure out an equation that can calculate t(between 0 and 1) that will detect if a circle will collide with a stationary line, using circle Initial center point, goal center point, and vertexes of the line segment, beginning and end? Any ideas to get me started?? In addition Points can be negative, which is some of my reasons for failures:(

Well, here's an idea about how to detect collision. By going from start to end, the circle will sweep an area which is the union of a rectangle and two circles, something like this:

O=====O

Since half a circle at each end overlaps with the rectangle, you can actually think of it as semi-circles:

O====D

But that's probably not useful, since it's probably easier to compute intersection with a circle anyway.

So to check whether there will be an intersection, you just do three tests -- for the rectangle and the two circles.

Is that what you wanted to achieve? Or do you also want to know when the intersection will occur?

looking for when!
the time(t) when intersection will occur

So how about this, then. You express the coordinates of the circle's center as a function of t. Based on this post: http://doswa.com/blog/?p=158, you compute what they call dist_v, which will depend on the center coordinates and therefore on t. You then look for solutions of the equation dist_v = R (it may be easier to solve dist_v^2 = R^2) as a function of t. If there are no solutions, or if the solutions are outside of [0, 1], then there are no intersections (exception: check explicitly for intersection at t = 0). If a solution is between 0 and 1, this is the intersection time.

oh easy problem. Move the line segment along it's normal toward the circle (found by using the dot product) a distance of the radius of the circle. Then treat the circle as a line segment going from pos to pos + velocity. Perform a line-segment to line-segment intersection test. If you don't have that equation it can be found here: Intersection functions. Okay you'll end up with an intersection point if it's in the range 0 to 1. (Use a line to line-segment if you want a range outside of that). Then find the distance between the intersection and circle's pos. Basically just: (intersectionPoint - circlePos).Length() and divide that length by the velocity. You'll get the 0 to 1 range you require.

If you don't understand the dot product part just remember that if you take two vectors a and b then a . b will be greater than 0 if they face the same direction (the angle is < 90 degrees). So if you take the right hand normal of (vert2 - vert1) and dot it with circlePos - vert1 you can see what side the circle is on by seeing if it's greater than or less than 0.

Quote:Original post by Sirisian
oh easy problem. Move the line segment along it's normal toward the circle (found by using the dot product) a distance of the radius of the circle. Then treat the circle as a line segment going from pos to pos + velocity. Perform a line-segment to line-segment intersection test. If you don't have that equation it can be found here: Intersection functions. Okay you'll end up with an intersection point if it's in the range 0 to 1. (Use a line to line-segment if you want a range outside of that). Then find the distance between the intersection and circle's pos. Basically just: (intersectionPoint - circlePos).Length() and divide that length by the velocity. You'll get the 0 to 1 range you require.

Are you certain that this will handle all cases correctly? What about if the circle center lies on the segment's supporting line?

@The OP: Although there are different ways of expressing the solution, the dynamic circle/sphere-vs.-segment test basically boils down to raytracing a capsule. A fairly straightforward (although not necessarily efficient) way to do this in 2-d is to raytrace against the rectangle and two circles that make up the capsule, and take the first time of intersection (if any).

Quote:Original post by jyk

Quote:Original post by Sirisian
oh easy problem. Move the line segment along it's normal toward the circle (found by using the dot product) a distance of the radius of the circle. Then treat the circle as a line segment going from pos to pos + velocity. Perform a line-segment to line-segment intersection test. If you don't have that equation it can be found here: Intersection functions. Okay you'll end up with an intersection point if it's in the range 0 to 1. (Use a line to line-segment if you want a range outside of that). Then find the distance between the intersection and circle's pos. Basically just: (intersectionPoint - circlePos).Length() and divide that length by the velocity. You'll get the 0 to 1 range you require.

Are you certain that this will handle all cases correctly? What about if the circle center lies on the segment's supporting line?

oh whoops I left off the end caps. What's a supporting line? Actually I'm kind of interested in all the implementations out there. If I have time tomorrow (it's 1 AM right now) I'll write up a quick example.