Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
Wish I had the reputation to also vote-up, thanks! –  Darthfett Feb 8 '12 at 15:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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