Circle-Line collision (used solution)

This describes the actually used way how the collision between line segment and circle is being resolved in the game engine.
Make sure you also check out the infinitesimal numbers problem

This is sub-layout for documentation pages


If collision between circle and line segment (which is line limited on interval \(<a,b>\)) is resolved, then, using line segment, other geometrical shapes can be created (such as triangle or polygon), and thus, the collision between them and circle is already solved.

1 Definitions

2 Objective

Imagine, that being given movement vector \(v\), the circle \(C\) would collide \(L_s\) during movement, if we move \(C\) by \(v\).

The objective is to determine vector \(v'\) such as, when moving \(C\) by vector \(v'\), then \(C\) will collide \(L_s\) in exactly one point.

The situation is illustrated by following image

3 Mathematical solution

The problem is divided to 3 cases, all of them will be discussed below.

Case 1: \(C\) will collide \(L_s\) during movement at point \(P\). Let \(M\) be, set of all points on line \(L_s\). Then, for \(P\) applies: \(P \in {M} / {A, B} \)

Case 1: \(C\) will collide \(L_s\) during movement at point \(P\). Let \(M\) be, set of all points on line \(L_s\). Then, for \(P\) applies: \(P \in \{M\} / \{A, B\} \)

To solve this case, let \(L\) be line defined by \(L_s\).

Case 2: \(C\) will collide \(L_s\) during movement at one of points \(A\) or \(B\), where \(A\), \(B\) are points defining the line \(L_s\)

To solve this, let's define a function, which will take edge point \(P \in \{ A, B\}\) as an argument. It will return whether the movement would cause collision with that point, or not.

Like this, such a function can be called twice, first with point \(A\) then with point \(B\).

The algorithm to decide whether \(C\) would collide \(L_s\) at \(P\) is as follows:

Of course, the final vectors \(v'_1, v'_2\) might not face in same direction as \(v'\).
In that case, the solution is discarted.
Moreover, if \(|t_1| > 1 \lor |t_2| > 1\), then \(t_1\), respectivelly \(t_2\) is discarted.
That is because we require final vector to have same or smaller length then the original move vector

Case 3: \(C\) will not collide \(L_s\) during movement at all

If none of Case1 or Case2 holds (or they yield no valid solution) solution, then the circle will not collide line segment at all during movement.

4 Using math above to get the final vector

Now, the math above explains, how to receive movement vectors for each case.
Being given some limited line \(L_s\) defined by points \(A, B\), circle \(C\), and movement vector \(v\), then: