Circle-Line collision (old solution)

This describes correct solution for circle-line collision with vector.
However, it involves lot of calculations, and this solution is not suitable, as because of the infinitesimal numbers problem it was extremely difficult to aproximate the solutions and keep the game collision functioning correctly.

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 6 cases, all of them will be discussed below.

3.1 Circle - Line segment intersection relationship

To solve all the cases, we need to first check for relation between \(C\) and \(L\) (do they collide each other? Or touch?)

3.1.1 Circle touches Line segment

For this, following statements apply:

To explain the math above in plain words:

3.1.2 Circle collides Line segment

For this, following statements apply:

To explain the math above in plain words:

Case 1: \(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, similar mathematical approach is used as in case2.
It is strongly recommended to read that first, and then come back here for better understanding...

By taking circle equation and line equation and combining them together, the point A (later also B) is plugged into the equations. If there is solution, and the final movement vector \(v\) matches criteria (smaller than original movement vector, etc...for more details, read through case2), then the circle is considered to be colliding line segment at point A (or B, respectivelly).

Case 2: \(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\} \)

Let's reiterate, that \(L\) is line, not a line segment. For simplicity, I will explain the solution on LINE, understanding that narrowing the solution down for line segment involves limitation on interval and adding few other edge cases to entire solution.

Let's start by having the equation of circle \(C\):

Now, we perform translation of the centre by vector \(v\):

However, we do not know how far to move the circle to get exactly one intersection point with \(L\). Therefore, we use parameter \(t\):

The equation above describes all circles, that are moved on the line defined by movement vector \(v'\)

Now, we will solve system of 2 equations:

Where the second equation is the equation of \(L\) in general form

We express \(x\) from the line equation (alternatively, \(y\) must be expressed in some cases to avoid diving by 0):

That value is plugged into the circle equation to get:

Now, considering \(t\) as the polynom variable, if discriminant equals 0, then there is exactly one solution (circle collides line in one point only)

The discriminant is then:

Considering some input values for circle centre, movement vector, radius, etc., this would be more readable result:

The thing left is to compute the \(t\), which is the movement vector multiplier.
Final solution vectors (if the solutions exist) will be:

\(v'_1 = (v_x * t_1, v_y * t_1)\)
\(v'_2 = (v_x * t_2, v_y * t_2)\)

The situation is illustrated by following image

The wolfram mathematica notebook can be downloaded here

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 and yields a solution, then the circle will not collide line segment at all during movement.

Case 4 and 5: \(C\) touches \(L_s\) before movement begins, and \(C\) will (or not) collide \(L_s\) during movement

For this one, imagine following figure:

In general case, imagining vector \(u=|AD|\), then movement of \(C\) using vector \(u\) is valid \(\iff D\) is on same side of line \(t\) as centre of circle \(C\) or \(D \in t\)

Case 6: \(C\) collides \(L_s\) before movement begins

Trivial case, when is done check for whether \(C\) collides \(L_s\), and if so, then no movement is done...