5
$\begingroup$

I'm trying to find the value(s) of the parameter $t$ at the intersection point(s) between a 2D general parabola (as a parametric function of $t$) and a line whose equations can be derived from two points $p$ and $q$ ($p \not = q$). The parabola is defined below:

$$x(t) = \frac{1}{2} a_x t^2 + v_x t + x_0 \\ y(t) = \frac{1}{2} a_y t^2 + v_y t + y_0$$

My Interest:

If I could find this solution, then I could predict the time-to-collision between two non-rotating, rigid line segments. By using the relative motion between them as the $a$ and $v$ in this parabolic curve for each point, and finding the intersection between it and the other line segment, I can find the smallest $t > 0$ such that the lines are colliding.

This would be for a physics engine, and using acceleration in the calculation would allow for some huge efficiency gains (not having to constantly predict and handle collision between every pair of line segments, only during relevant time frames or when acceleration changes).

Edit:

Thanks to Andrea Mori, I was able to solve for this equation (given the line defined by $p$ and $q$):

$$(q_y - p_y) x(t) - (q_x - p_x) y(t) - |p \times q| = 0$$

(By treating $a_x b_y - a_y b_x$ as equivalent to $\left| a \times b \right|$ for 2D). Then, substituting $x(t)$ and $y(t)$, I was able to simplify down to more cross products:

$$\frac{1}{2}\left(\left| a \times q \right| - \left| a \times p \right|\right) t^2 + (\left| v \times q \right| - \left| v \times p \right|)t + (\left| r \times q \right| - \left| r \times p \right| - \left| p \times q \right|) = 0$$

The quadratic formula can then be applied using the clearly visible $a$, $b$, and $c$ values (though writing it out would get ugly). A negative discriminant ($b^2 - 4ac$) indicates no collision, zero indicates exactly one, and positive indicates two (the smallest $t > 0$ being the most important one).

I think the second formula would then translate to 3D, though I don't know without evaluating it some more.

$\endgroup$
  • 3
    $\begingroup$ A parabola with an arbitrary axis of symmetry is still called a parabola: en.wikipedia.org/wiki/Parabola#General_parabola $\endgroup$ – Martin Wanvik Feb 7 '12 at 17:08
  • $\begingroup$ By any chance, are your parabolas quadratic Bézier curves? $\endgroup$ – J. M. is a poor mathematician Feb 8 '12 at 15:20
  • $\begingroup$ In any event: the symbolic formulae look to be terribly complicated; you might be better off using a numerical method like Newton-Raphson for generating your intersections. $\endgroup$ – J. M. is a poor mathematician Feb 8 '12 at 15:24
  • $\begingroup$ I'm not sure, as I don't know much about Bézier curves. It looks like it could be a special case with some P0 to P1 being parallel to the Y-axis and some P1 to P2 being parallel to the X-axis. $\endgroup$ – Casey Kuball Feb 8 '12 at 15:33
4
$\begingroup$

If $P=(x_P,y_P)$ and $Q=(x_Q,y_Q)$ the line between $PQ$ has equation $\frac{x-x_P}{x_Q-x_P}=\frac{y-y_P}{y_Q-y_P}$ which we can rewrite as $$ ax+by+c=0, $$ where the coefficients $a$, $b$ and $c$ are very easily computed.

Now, to get the values of the parameter $t$ for which your generic parabola point $(x(t),y(t))$ meets the line $PQ$ you just need to solve the equation (in $t$) $$ ax(t)+by(t)+c=0. $$ This is actually an easy task, since it's just a quadratic equation.

Mind that the procedure is actually more general: it can be easily adapted to find the points where any curve given in parametric form meets a given line. Of course, in general one runs into the problem that the final equation may not be easily solvable.

$\endgroup$
  • $\begingroup$ Wish I had the reputation to also vote-up, thanks! $\endgroup$ – Casey Kuball Feb 8 '12 at 15:41

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.