2D collision between a moving circle and a fixed line segment

Joel picture Joel · Aug 15, 2011 · Viewed 7.6k times · Source

In the context of a game program, I have a moving circle and a fixed line segment. The segment can have an arbitrary size and orientation.

  • I know the radius of the circle: r
  • I know the coordinates of the circle before the move: (xC1, yC1)
  • I know the coordinates of the circle after the move: (xC2, yC2)
  • I know the coordinates of the extremities of the line segment: (xL1, yL1) - (xL2, yL2)

moving circle

I am having difficulties trying to compute:

  • A boolean: If any part of the circle hits the line segment while moving from (xC1, yC1) to (xC2, yC2)
  • If the boolean is true, the coordinates (x, y) of the center of the circle when it hits the line segment (I mean when circle is tangent to segment for the first time)

Answer

Gleno picture Gleno · Aug 15, 2011

I'm going to answer with pseudo-algorithm - without any code. The way I see it there are two cases in which we might return true, as per the image below:

Two cases

Here in blue are your circles, the dashed line is the trajectory line and the red line is your given line.

  • We build a helper trajectory line, from and to the center of both circles. If this trajectory line intersects the given line - return true. See this question on how to compute that intersection.
  • In the second case the first test has failed us, but it might just so happen that the circles nudged the line as they passed on the trajectory anyway. We will need the following constuction: Construction

From the trajectory we build normal lines to each point A and B. Then these lines are chopped or extended into helper lines (Ha and Hb), so that their length from A and B is exactly the radius of the circle. Then we check if each of these helper lines intersects with the trajectory line. If they do return true.

  • Otherwise return false.