# Find intersection(s) between parametrized parabola and a line

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.

-
A parabola with an arbitrary axis of symmetry is still called a parabola: en.wikipedia.org/wiki/Parabola#General_parabola – Martin Wanvik Feb 7 '12 at 17:08
By any chance, are your parabolas quadratic Bézier curves? – J. M. Feb 8 '12 at 15:20
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. – J. M. Feb 8 '12 at 15:24
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. – Darthfett Feb 8 '12 at 15:33

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.