0
$\begingroup$

Recently I have learned how to predict the time of collision between two circles moving linearly. Positions of $P$ and $Q$ after time $t$ are:
$P(t) = P_0 + vPt$
$Q(t) = Q_0 + vQt$
The goal was to find such an instant ($t$) when distance between circle centers equal to sum of their radii:
$P(t) - Q(t) = rP + rQ$
$(P_0 + vPt) - (Q_0 + vQt) = rP + rQ$
$P_0 - Q_0 + (vP - vQ)t = rP + rQ$
$(P_0 - Q_0 + (vP - vQ)t)^2 = (rP + rQ)^2$
$(P_0 - Q_0 + (vP - vQ)t) * (P_0 - Q_0 + (vP - vQ)t) = (rP + rQ)^2$
Some parts of the equation can be reduced:
$A = P_0 - Q_0$
$B = vP - vQ$
$(A + Bt) * (A + Bt) = (rP + rQ)^2$
$A * A + 2(A * B)t + (B * B)t^2 = (rP + rQ)^2$
$A * A + 2(A * B)t + (B * B)t^2 - (rP + rQ)^2 = 0$
This leads to the quadratic equation $at^2 + bt + c = 0$, where:
$a=B * B, b=A * B, c=A * A - (rP + rQ)^2$
From this $t$ is resolvable: $t = \frac{(b ± \sqrt{b^2 - 4ac})}{2a}$
Discriminant $b^2 - 4ac$ has no solutions (no collision) when it is less than zero. Has exactly one solution (touch at some instant) when it is equal to zero. Has more than one solution (collision) when it is greater than zero.

What I'm trying to solve is the time of collision between circles rotating around their fixed points.
collision between two rotating circles after time t
$P(t) = P_0 + \omega Pt$ (i.e. $P_c$ + radial vector $P_cP_0$ rotated by $\omega Pt$)
$Q(t) = Q_0 + \omega Qt$
The goal is to find such an instant when distance between circle centers equal to sum of their radii:
$P(t) - Q(t) = rP + rQ$
$(P_0 + \omega Pt) - (Q_0 + \omega Qt) = rP + rQ$
But at this point I'm pretty much stuck. $P_0 - Q_0$ supposed to result in a vector from $Q_0$ to $P_0$, and $\omega Pt - \omega Qt$ supposed to result in a pseudovector, and I doubt if I can use vector math between them. I'm not sure if $\omega Pt - \omega Qt$ subtraction is allowed either, since they have different fixed point and rotate in different trajectories.

How can I come to the quadratic equation (if possible) or should I go with completely different priori collision detection algorithm to reach the solution?

$\endgroup$
  • $\begingroup$ If I get your question right, you have a circle centered at $P(t)$ with radius $rP$, and another circle centered at $Q(t)$ with radius $rQ$, and want to find out when they collide? Your notations and the image are a little confusing to me. Also, I suggest explaining what "$\omega Pt$ is a little better. $P_0$ is the position of $P(t)$ at $t=0$, and $P_c$ the "fixed position" around which $P(t)$ rotates? $\endgroup$ – N.Bach Nov 8 '17 at 19:36
  • $\begingroup$ Yes, $P(t)$ and $Q(t)$ are circle centers in respect of the time. $rP$ and $rQ$ are their radii. $\omega Pt$ is angular velocity of $P$ in radians per $t$. $P_0$ and $Q_0$ are initial positions of $P$ and $Q$ respectively. $P_c$ and $Q_c$ are fixed points around which $P$ and $Q$ rotate respectively. $\endgroup$ – Ilya Nov 8 '17 at 19:47
  • 1
    $\begingroup$ Your’re missing a norm from the left-hand side of your equation. $\endgroup$ – amd Nov 8 '17 at 22:40
  • $\begingroup$ The "$\omega Pt$" still confuses me. Assuming that $\omega P$ is your angular velocity, then $\omega Pt$ is an angle. You cannot simply add that to your point. The expression "$P(t)=P_c+$ some vector" makes more sense, and then it's a matter of expressing that vector "$P_cP_0$ rotated by $\omega Pt$" properly. Which can be done fairly easily with trigonometric functions. $\endgroup$ – N.Bach Nov 9 '17 at 2:16
  • $\begingroup$ @N.Bach I agree that I cannot add the angle to the point. However I don't know how to express that mathematically. I pointed that in my question $P(t)=P_0+ωPt$ (i.e. $P_c +$ radial vector $P_cP_0$ rotated by $ωPt)$. I would imagine equation would look like that $(P_c +$ radial vector $P_cP_0$ rotated by $ωPt) - (Q_c + $radial vector $Q_cQ_0$ rotated by $ωQt) = rP + rQ$, but that is not mathematical expression. Is that enough to come to quadratic equation and solve it like I did with linear motion case? $\endgroup$ – Ilya Nov 9 '17 at 17:55
0
$\begingroup$

A little bit of a disclaimer, but I'll adopt slightly different notations so I can keep track of what I'm talking about easier. In particular $r_P$ and $\omega_P$ will denote the radius and angular velocity for point $P$, instead of $rP$ and $\omega P$. Likewise for point $Q$.


I'll assume Cartesian coordinates.

Let's start off with a parametric equation of a circle. Say you have a circle centered at some point $C(x_C,y_C)$ with radius $r$, then any point of the circle can always be expressed as $M(x(\theta),y(\theta))$ with \begin{align*} x(\theta) &= x_C+r\cos\theta \\ y(\theta) &= y_C+r\sin\theta \end{align*} for some $\theta\in\mathbb R$. Actually, the value $\theta$ is the angle between the horizontal axis and vector $\vec{CM}$. To make this a little more compact, let $\vec u(\theta)$ be the unit vector $(\cos\theta,\sin\theta)$, then point $M$ at angle $\theta$ is $M=C+r\vec u(\theta)$.

Note that sometimes people prefer to pick $\theta\in[0,2\pi)$, since it's an angle. But for what comes after, $\mathbb R$ makes a little bit more sense.

Anyway, we can apply this to $P(t)$. Let $\theta_{P_0}$ the angle corresponding to $P_0$. Assuming that $\omega_P$ is the counter-clockwise angular velocity, vector $\vec{P_cP(t)}$ forms an angle of $\theta_{P_0}+\omega_P\times t$. So we end up with $P(t)=P_c+\| P_0-P_c \|\vec u(\theta_{P_0}+\omega_P t)$.

Likewise, you get $Q(t)=Q_C+\| Q_0-Q_c\|\vec u(\theta_{Q_0}+\omega_Q t)$. Then the distance between $P(t)$ and $Q(t)$ would be $$ \| P(t)-Q(t) \| = \Big\| \big(P_c-Q_c\big) +\big(\|P_0-P_c\|\vec u(\theta_{P_0}+\omega_Pt) -\|Q_0-Q_c\|\vec u(\theta_{P_0}+\omega_Qt)\big) \Big\| $$ Personally, I don't think you can get a quadratic equation off of that in the general case.

Assuming you go for a detection of the type $\| P(t)-Q(t) \|^2 < (r_P+r_Q)^2$ and use a little bit of trigonometry, you would end up with a collision detection equation of the type: $$ A\cos(\omega_Pt)+B\sin(\omega_Pt)+C\cos(\omega_Qt)+D\sin(\omega_Qt)+E<0 $$ Personally I prefer the equivalent form: $$ F\cos(\omega_Pt+\phi)+G\cos(\omega_Qt+\psi)+E<0 $$ Either way, these are not as nice as the linear case.


So now, can we infer collision of the circles out of this? Well, if you're only interested if whether they collide or not, it's more or less doable. If you want also the time $t$ at which they collide, then things get more awkward.

There are mostly two main cases: when $\frac{\omega_P}{\omega_Q}\in\mathbb Q$, and $\frac{\omega_P}{\omega_Q}\notin\mathbb Q$.


Strangely enough, the irrational case seems easier to test. Notice that $\cos(\omega_Pt+\phi)$ admits a period of $T_P=\frac{2\pi}{\omega_P}$. If we have a look at values $(\omega_Q\times n\times T_p) \mod 2\pi$, where $n$ is a positive integer, we can prove they are dense in $[0,2\pi]$. Long story short, if you chose any two real numbers $\alpha,\beta\in[-1,1]$, there is a time value $t$ such that $$ F\cos(\omega_Pt+\phi)+G\cos(\omega_Qt+\psi)+E \approx \alpha F+\beta G+E $$ and the approximation is arbitrarily good. So testing whether the circles will collide is equivalent to testing $\lvert E\rvert < \lvert F\rvert + \lvert G\rvert$.

(Because I was lazy I didn't check what $E$ looked like in this problem, but it's most likely positive. So you'd end up with testing $E<\lvert F\rvert+\lvert G\rvert$)

When the circle collides, figuring out the precise moment when they collide for the first time gets a lot harder. You can probably get approximations of "guaranteed collision" times fairly easily though.


In the rational case, there exists two integers $N\neq M$ such that $\frac{\omega_P}{\omega_Q}=\frac NM$. We let $\omega$ be the value $\omega=\frac{\omega_P}N=\frac{\omega_Q}M$. We end up with testing for $$ F\cos(N\omega t+\phi)+G\cos(M\omega t+\psi)+E <0 $$ The left hand side is periodic. Assuming that $N$ and $M$ are coprime, and that $\omega$ is irrational, I think the shortest period is $T=\frac{2\pi}{\omega}$. Even if it isn't the shortest, it still is a period.

Now the problem is, depending on the magnitude of $F$, $G$, $N$ and $M$, and the phase difference $\phi-\psi$, a lot of thing can happen.

Long story short, you probably have to study the variations of the left hand side, and it's a bit of a pain. If you like polynomials, you can always use Chebyshev polynomials. If you start off from $$ A\cos(N\omega t)+B\sin(N\omega t)+C\cos(M\omega t)+D\sin(M\omega t)+E<0 $$ you will obtain some polynomial $R[X]$ that satisfies $$ R[\cos(\omega t)]=A\cos(N\omega t)+B\sin(N\omega t)+C\cos(M\omega t)+D\sin(M\omega t)+E $$ so you'd end up with inspecting the range $[-1,1]$ for values $X$ such that $R[X]<0$. Since the degree of $R[X]$ can get arbitrarily large, this is still a fairly difficult task. To be honest, I'm not even sure whether this can be solved exactly.

$\endgroup$
  • $\begingroup$ Thank you for your time. As you mentioned, I need to predict the time of collision (not only to indicate will there be a collision). Perhaps I should take another strategy. $\endgroup$ – Ilya Nov 13 '17 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.