Calculating the intersection of a fast moving circle and a line

Question

Inside of my game, I am in need of a way to test the collision between a line segment and a fast-moving circle. I would say I need a line v capsule collision however the problem is I need the collision point. None of the existing formulas I can find can do quite what I need. I have tried line x line intersection and just moving the lines by the radius of the capsule sort of work however then the collision point found around the edges is off. Additionally, I can't find a way to work back from the collision point to the point that the circle first collided at.

Above is sort of a picture of what I am hoping to achieve. The green capsule represents the circle's path.

So really the problem here is finding that collision point because a yes or no answer is trivial here. There are formulas for ray capsule or box capsule however none of them will get me this collision point.

Does anyone have any ideas on how I can figure this out?

Answer 1

I assume that the black line (in the end: repeat for each line) is given as $$a+sb, \quad s \in I,$$ (where \$a\$ and \$b\$ are vectors denoting starting point and direction and \$I\subset\mathbb{R}\$ is an interval, probably \$[0,\infty)\$ for the first of your lines and \$(-\infty,\infty)\$ for the second) and that the green path (more precisely: the path of the centre of the circle) is similarly given as $$c+td, \quad t\in J,$$ (with given vectors \$c\$,\$d\$ and interval \$J=[0,?]\$).

Then the point you are searching for should be described by $$|a+sb-(c+td)|^2=R^2 \qquad (\star)$$ (with \$|.|\$ denoting Euclidean distance and \$R\$ being the radius of the circle).

Up to now, this is one equation for two unknowns (\$s\$ and \$t\$). You want that \$t\$ is as small as possible and then want to know \$s\$. Consider \$t\$ as given and (\$\star\$) as quadratic equation in \$s\$. Then you can compute the discriminant of this quadratic equation, which will tell you how many solutions the quadratic equation has. As the discriminant is an expression depending on \$t\$ (and known constants), you can compute the smallest value of \$t\$ (\$\in J\$) for which (\$\star\$) has a solution (if such \$t\$ exists). With this value of \$t\$ solve (\$\star\$) for \$s\$. If \$s\in I\$, then \$a+sb\$ is the point you were searching for.

If \$s\not\in I\$, then (probably) the endpoint of \$I\$ is the only possible collision point, and checking the path of the circle(-midpoint, i.e. the line \$c+td, t\in J\$) for intersection with a circle with radius \$R\$ around that endpoint should tell you if a collision occurs there.

Answer 2

Why do you need the collision point of the circle at all? Couldn't you simply calculate a circle-circle collision with your red circle and the end point of your line?

if (dx * dx + dy * dy <= r1 * r1 + r2 * r2) {
  // Collision detected
}

Or maybe a look on this stackoverflow post will help: https://stackoverflow.com/questions/1736734/circle-circle-collision

Darth Moon