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

Top

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.

• Term line reffers to infinite line, not line segment
• Let \(C\) be circle with centre \(C_s = (c_x, c_y)\) that we want to move
• Let \(L_s\) be Line Segment defined by 2 points, \(A, B\)
• Let \(L\) be Line defined also by 2 points, \(A, B\)
• Let \(v=(v_x, v_y)\) be vector, defining the movement of the circle \(C\)
• Let \(v'\) be the final movement vector (the result)
• \(L_s\) touches \(C \Leftrightarrow C\) and \(L_s\) have exactly \(1\) intersection point
• \(L_s\) collides \(C \Leftrightarrow C\) and \(L_s\) have exactly \(2\) intersection points

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

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

• Case1: \(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\} \)
• Case2: \(C\) will collide \(L_s\) during movement at one of points \(A\) or \(B\), where \(A\), \(B\) are points defining the line \(L_s\)
• Case3: \(C\) will not collide \(L_s\) during movement at all

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\).

• Calculate line \(L_p\) which is perpendicular to \(L\) and passes through center point \(C_r\) of \(C\)
• Get intersection points of line \(L_p\) and circle \(C\). This always yields points, \(I_1, I_2\)
• Choose point \(I \in \{I_1, I_2\}\) such as distance of \(I\) and \(L\) is minimal possible
• Construct line \(L_v\) from move vector, passing through intersection point \(I\)
• Get intersection \(I_f\) of the \(L_v\) and \(L\). If the lines are paralell, there is no solution, and therefore movement by \(v\) will be allowed
• If the \(I_f\) does not lie on \(I_s\), then movement by \(v\) will be allowed
• Final move vector \(v'\) is created from points \(I\) and \(I_f\), beginning in point \(I\)
• Validate final move vector \(v'\)

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:

• Create line \(L_{pv}\) defined by input point \(P\) and move vector \(v\)
• Get set \(S\) of intersection point(s) of \(L_{pv}\) and circle \(C\)
• If \(S\) is empty, return -> movement shall not be restricted
• Let \(I\) to be point from \(S\), which is closer to \(P\)
• Create vector \(v'\) from points \(I\) and \(P\)
• Validate final move vector \(v'\)

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.

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:

• Step 1: Let \(v_f\) be final movement vector, returned after checking for all cases
• Step 2: Check for case 1. If collision would occur, and \(|v'| < |v_f|\), then \(v_f := v'\)
• Step 3: Check for case 2, use \(A\) as parameter. If collision would occur, and \(|v'| < |v_f|\), then \(v_f := v'\)
• Step 4: Same as Step 3, but use \(B\) as parameter
• Step 5: If \(v_f\) was never set, return no movement restriction. Else, continue.
• Step 6: Return \(v_f\) as movement vector