Vrftsjtryk

• Let this problem be in 2D cartesian plane.
  
  
  
  
  • Let 'Collision' of two objects be $<=>$ they are not touching and they have atleast one intersection point.
  
  
  • Let $C$ be a circle with centre $O$ and radius $R$.
  
  
  • Let $L$ be a line segment defined by two points, $A$, $B$.
  
  
  • Let $Vm$ be vector defining the movement of $C$.
  
  
  
  

Suppose, that we move $C$ using vector Vm and on the path, the circle will collide $L$.

• Let Vc be vector.


• Let $C'$ be circle $C$ moved using $Vc$. (definition and explanation below)

I am tying to find $Vc$.

If we move $C$ by $Vm$ and on the movement path, and $C$ would collide $L$, then $Vc$ is vector such as $C'$ will touch L and length of $Vc$ $lt$ $Vm$.

If $C$ during movement mentioned above would not collide $L$, then $Vc=Vm$

Illustration of the problem

On paper this can be solved by look and see, however, I am looking for idea on how to solve this algorithmically.
Result will be used in computer code.

I solved most of cases by:

1. finding $L2$ orthogonal to $L$ such as $O$ lies on $L2$
   


2. calculating $X$ intersection point of $L$ and $L2$
   


3. calculating distance $|XO|$
   


4. subracting $|XO|$ from length of $Vm$ to get $Vc$ (reducing its length by $|XO|$)

This, however, does deal only with some cases of the problem. Not, for example, the first one displayed in illustration.

Thank you for any help

Node: I would like to avoid having for loop and checking for collision during all the movement steps

So finally I am answering my own question after months of work.
The entire problem is quite complicated, but worth solving, since the final collision handling is really worth it.

This explanation is copied here from my webpage, where the math solution is more detailed and supported with more images plus wolfram mathematica notebooks.

This describes how the collision between the objects in the game is being handled.

If collision between circle and line segment (which is line limited on interval &lta,b&gt 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.

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

• 
  If $C$ does not touch nor collides line $L_s$ before movement begins



Case1: $C$ will collide $L_s$ during movement at one of points $A$ or $B$, where $A$, $B$ are points defining the line $L_s$
Case2: $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 &lcub;M&rcub; / &lcub;A, B&rcub; $
Case3: $C$ will not collide $L_s$ during movement at all



• 
  If $C$ touches $L_s$ before movement begins



Case4: $C$ will collide $L_s$ during movement
Case5: $C$ will not collide $L_s$ during movement


Case6: $C$ collides $L_s$ before movement begins

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

For this, following statements apply:

To explain the math above in plain words:

• If one of the intersection points is $A$, and the other intersection point
  does not lie on the line segment $L_s$ and the B point lies outside the circle, then they touch


• If one of the intersection points is $B$, and the other intersection point
  does not lie on the line segment $L_s$ and the A point lies outside the circle, then they touch

For this, following statements apply:

To explain the math above in plain words:

• If both intersection points lie on $L_s$, then they collide


• If one of the intersection points is $A$, and the other intersection point
  does not lie on the line segment $L_s$ and the $B$ point lies inside or on the circle, then they collide


• If one of the intersection points is $B$, and the other intersection point
  does not lie on the line segment $L_s$ and the $A$ point lies inside or on the circle, then they collide

To solve this, similar mathematical approach is used as in case2.


It is strongly recomended 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).

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$:

$$(x-c_x)^2+(y-c_y)^2=r^2$$

Now, we perform translation of the centre by vector $v$:

$$(x-(c_x+v_x))^2+(y-(c_y+v_y))^2=r^2$$

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

$$(x-(c_x+v_x*t))^2+(y-(c_y+v_y*t))^2=r^2$$


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:

$$(x-(c_x+v_x*t))^2+(y-(c_y+v_y*t))^2=r^2$$
$$a*x+b*y+c=0$$

Where the second equation is the equation of $L$ in general form

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

$$x=frac{-b*y-c}{a}$$

That value is plugged into the circle equation to get:

$$(frac{-b*y-c}{a}-(c_x+v_x*t))^2+(y-(c_y+v_y*t))^2=r^2$$

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

$$Discriminant[(frac{-b*y-c}{a}-(c_x+v_x*t))^2+(y-(c_y+v_y*t))^2-r^2,y]=0$$

The discriminant is then:

$$D=-(frac{1}{a^2})*
4 *(c^2 + 2 a c c_x + a^2 c_x^2 + 2 b c c_y + 2 a b c_x c_y + b^2 c_y^2 -
a^2 r^2 - b^2 r^2 + 2 a c t v_x + 2 a^2 c_x t v_x + 2 a b c_y t v_x +
a^2 t^2 v_x^2 + 2 b c t v_y + 2 a b c_x t v_y + 2 b^2 c_y t v_y +
2 a b t^2 v_x v_y + b^2 t^2 v_y^2)$$

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

$$D=-4(28-36*t+9t^2$$

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)$

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

If none of Case1 or
Case2 holds and yields a solution,
then the circle will not collide line segment at all during movement.

For this one, imagine following figure:

touchMoveIllustration1

• Let $t$ be tangent to $C$ in point $P$, which is touch point of $C$ and $L_s$ (in this example, $P=A$)


• Let $u=|AE|$, $v=|AD|$ be two movement vectors, where we position them to begin in touch point $P=A$
  


• 
  $u=|AE|$ represents movement that would be allowed, whereas $v=|AD|$ represents movement that would NOT be allowed

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$

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

You’ve clearly put a lot of thought and effort into this. I believe that there are far fewer cases to consider than you think, though.

I’m a bit lazy, so for problems like this one, I often find that it’s easier to overgenerate potential solutions and then winnow them down (cf. moving rectangle collision). In that spirit, let’s find all of the contacts between the line segment and a circle moving along the straight line defined by $mathbf v$ regardless of when they occur. If we take $mathbf v$ as defining a unit time step, as you’ve done, then we’re looking for the leading-edge contact that occurs first within the open time interval $(0,1)$, if any.

There are two types of contact of interest: when either endpoint lies on the moving circle and when the line segment is tangent to the moving circle. The times of all of these events are described by simple quadratic equations. To reduce clutter, assume that the center of the circle is at the origin at time $t=0$; you can always translate the points to make it so, and it doesn’t affect the solution. The position of the center of the circle can therefore be parameterized as $C(t) = tmathbf v$. The point $A$ lies on the moving circle when $|A-C(t)|=r$ and similarly for $B$. The lesser of the solutions to this quadratic equation represents the leading-edge contact time. If this is $le0$, discard the event (but see below).

The line through $A$ and $B$ is tangent to the circle when the distance between it and the center of the circle is equal to $r$. This can be expressed using a variation of the standard point-line distance formula: $$left(detbegin{bmatrix}A&B&C(t)\1&1&1end{bmatrix}right)^2 = r^2|A-B|^2.$$ The determinant on the left-hand side can be derived using homogeneous coordinates: Let $mathbf a$ and $mathbf b$ be homogeneous coordinate vectors of the two points, which can be obtained by appending a $1$ to their Cartesian coordinates. The line through these points can be represented by the homogeneous vector $mathbf l=mathbf atimesmathbf b$ (every point $mathbf p$ on the line satisfies $mathbf lcdotmathbf p=0$) and the distance of a point $mathbf p$ to the line is given by ${|mathbf lcdotmathbf P|over|l_1^2+L_2^2|}$. This overgenerates solutions, though, since we have a line segment instead of the entire line. For the line segment to be tangent, the endpoints can’t be on the same side of the perpendicular at the point of tangency. This perpendicular is the line (again in homogeneous vector representation) $mathbf m=[A-B; -(A-B)cdot C(t)]$ and the points $A$ and $B$ are on the same side of this line if the signs of $mathbf mcdotmathbf a$ and $mathbf mcdotmathbf b$ agree. Expanding the first of these dot products, we have $$mathbf mcdotmathbf a = (A-B)cdot A-(A-B)cdot C(t) = (A-B)cdot(A-C(t))$$ and similarly for $B$. Discard any of the up to two tangent contacts that don’t pass this filter.

Select the least nonnegative contact time less than $1$ among the surviving solutions to the above quadratics. If there is such a time $t$, then $mathbf v'=C(t)$.

This approach requires computing three square roots, two of which might turn out to be irrelevant. That’s a relatively expensive operation, but we can improve the efficiency by noting that if there is a tangent contact with the leading edge of the circle, then neither of the segment endpoints can contact the leading edge sooner than that. So, solve for the tangent contact times first, and if the earlier one survives both filters, you’re done. Otherwise, proceed with computing the endpoint contacts.

I’ve assumed in the above that the segment and circle don’t already intersect at $t=0$. If you want to detect this as well, that’s pretty easy to do: if the lesser of any of the $t$ value pairs computed above are $le0$, then the figures are potentially in contact at start. Examine the other $t$ value of the pair: if it’s $ge0$, this means that the trailing-edge contact has not yet occurred, so the figures currently overlap. Again, you’ll need to take a bit of extra care with the tangent contacts: both of the contacts must be real, per the criterion described earlier (most other cases in which only one contact is real are subsumed in endpoint overlaps, but take a careful look at $t=0$).

It’s possible to compute the contact points (and hence times) without directly solving the quadratic equations from above, but I don’t believe that doing so will be any more efficient. It might make the code a bit easier to understand, though, since those calculations are essentially geometric constructions with points and lines instead of complicated formulas that involve a pile of coordinates. It’s also relatively easy to work out the possible points of contact on the leading edge of the circle and then turn the problem into one of computing three segment-segment intersections, for which there are known efficient algorithms, but I’m not sure that doing so result in more efficient code, either.