Line Segment vs Circle Swept Collision Detection Algorithm

Notice:

Implementation Can be found on GitHub. Search the username MonkeyToiletLadder for the repository. It has passed all test cases I have given it. It's pretty fast with the most expensive function being a sqrt no trig. Please let me know what you think of it.

Background:

There is plenty of information on how to detect if a circle collides with a line segment, but I have found little information on how to do this over a time step. For example we have a circle that has accelerated through a line segment BE over a indivisible time step. This is just a test case. I would like to test against any line segment. I have thought of two ways of detecting this type of collision . . .

Either Calculate the swept circle and test if points are within or . . .

Find a point on the line segment which is closest to the circle.

Then create a line that goes through this point and points in the direction of the circles velocity.

Find the intersection points of this line and the circle at both time points.

Form a line segment with the intersection points.

If this line segment contains the closest point to the circle than the circle has collided with the line segment at that point.

I prefer not to use the first.

Question:

Is there a formula that calculates a point on a line segment that is closest to a circle? Could I use the parametric equation of a circle?

I think the closest point should either be one of the end points or the intersection point of the segments perpendicular bisector that contains the center of the circle.

• Note that you can change frame of reference so that the circle is stationary and the line is moving. Then your question is whether the parallelogram swept by the line intersects the circle, which may be more tractable. – stewbasic Oct 4 '17 at 3:56
• That sounds interesting I will keep that in mind. It actually sounds really cool. – dylan Oct 4 '17 at 3:58
• I will try to implement this. I think it will work. Its very simple yet outside of the box type solution. Thank you. – dylan Oct 4 '17 at 4:07
• I still need to be able to find the closest point though. After I confirm they are colliding I need a collision point / distance so I can move the circle. – dylan Oct 4 '17 at 4:11
• Yes this might work, but i need the closest point, sweep it along the the circle velocity path forming a line segment. So then at most I only have to check for two intersections instead of six. – dylan Oct 4 '17 at 4:25

I think there are a few questions here. First, how to find the point on a line segment closest to a circle?

Suppose the segment is $ab$ and the circle has center $o$ and radius $r$. Let's assume the segment doesn't intersect the interior of the circle (presumably this is true in the context of your question). Then this is the same as the point on the segment closest to $o$. First find the point $x=ta+(1-t)b$ on the line through $ab$ closest to $o$. This satisfies $$0=(a-b)\cdot(x-o)=(a-b)\cdot(b-o)+t|a-b|^2.$$ Thus $$t=\frac{(a-b)\cdot(o-b)}{|a-b|^2}.$$ If $t<0$, the closest point is $b$. If $t>1$, the closest point is $a$. If $t\in[0,1]$, then $x$ lies on the segment and it is the closest point.

Second question: Can we simplify the collision detection by only considering the point $x$ on the segment which is initially closest to the circle?

I'm not sure if I understand your proposed method correctly, but I think considering only the point $x$ is not sufficient. For example, suppose $o=(0,0)$, $r=1$, $a=(0,2)$ and $b=(4,2)$. Suppose the displacement of the circle is $(4,4)$. Initially the point closest to the circle is $x=a$, and the circle never touches $x$, but it does cross the segment $ab$.

Third question: how to find the collision point, if it occurs.

Unfortunately I can't see a way to do this correctly without considering a few different cases.

I'll assume the line segment moves instead of the circle; it's equivalent, but I find it a bit easier to visualize. Suppose the displacement of the line segment is $v$, so the final endpoints are $a'=a+v$ and $b'=b+v$. One possibility is that the segment collides with the circle at an endpoint. We can check for this by intersecting the circle with segments $aa'$ and $bb'$. Another possibility is that it collides at an interior point. If so, the point of collision must be $$o\pm r\frac{R(a-b)}{|a-b|}$$ where $R$ denotes rotation counterclockwise by $\pi/2$. This means there must be $s_\pm,t_\pm\in[0,1]$ such that $$t_\pm a+(1-t_\pm)b+s_\pm v=o\pm r\frac{R(a-b)}{|a-b|}.$$ Taking the dot product with $R(a-b)$, $$s_\pm=\frac{(o-a)\cdot R(a-b)\pm r|a-b|}{v\cdot R(a-b)}.$$ Taking the dot product with $a-b$, $$t_\pm=\frac{(o-b-s_\pm v)\cdot(a-b)}{|a-b|^2}.$$ We can use these equations to determine $(s_\pm,t_\pm)$. If both are in $[0,1]$, then collision occurs at time $s_\pm$.

If none of these possibilities occurs, then there is no collision.

• Yes my logic is a bit flawed. In the case where the closest point is Not the end points the collision point is not the closest point. I have get a point on the circle closest to the line segment form a line segment with this point by adding the circles velocity and see if this line segment collides with the original. Probably does not make much sense. I might post another drawing to make more sense of it. You have still helped though thank you. – dylan Oct 4 '17 at 17:56
• So for the second question you are right. I have to have the point on the circle closest to the line segment. And project this point to its new position creating a line segment. This solves the test case in the second question. – dylan Oct 4 '17 at 18:07
• Is time s plus or minus an actually time or is it a collision point? If it is a time than it will simplify my algorithm a whole lot. And is the rotation by -Pi/2 specific to the example or used for all cases? – dylan Oct 7 '17 at 3:02