Intersection of two moving line segments (or a moving line segment and a point)

Question

I'm trying to design a 2D physics engine with continuous collision detection. Objects are stored as a list of non-rotating line-segments. Therefore I can detect collisions by finding the collision time between each pair of line segments between any two objects.

I want to find the exact time for an intersection between two moving line-segments that are moving in a constant direction, and it is proving to be difficult.

I have figured out that I can simplify the problem further by finding the collision time between each point on a line-segment and the other line-segment (and vice versa). It's possible that it is computationally inefficient, so a general solution for two line segments would be the ideal answer. I can also ignore the case in which lines are parallel (I want to treat a line/point sharing the same position and velocity as 'no collision').

If the answer is "not possible" to exactly find this intersection time, I would accept it as a solution. Any help on the subject would be appreciated.

EDIT: According to Wikipedia's article on a Line segment, for a line segment with endpoints A = (a_x, a_y) and C = (c_x, c_y), a general equation for the line segment looks like this:

For a line-segment--point intersection, would substituting

• p_x + p_v * t for a_x (left-side only, right-side is just p_x)
• p_y + p_v * t for a_y (left-side only, right-side is just p_y)
• q_x + q_v * t for c_x (left-side only, right-side is just q_x)
• q_y + q_v * t for c_y (left-side only, right-side is just q_y)
• r_x + r_v * t for x
• r_y + r_v * t for y

for a line segment pq [(p_x, p_y), (q_x, q_y)], point r (r_x, r_y), moving at rates of p_v == q_v != r_v be solvable for t? Here's the full equation:

Answer 1

The equation I have up above is incorrect in that it uses the same velocity for both its x and y components.

Since velocity is constant, I can simplify the equation such that the point is moving in reference to the line segment. The amount of variables used for velocity reduces greatly, by using v = r_v - qp_v for the velocity of the point r, and 0 for the velocity of each line segment. The equation with the variables plugged in then becomes:

Thanks to WolframAlpha, the equation is then solved for t:

What's interesting is that if you analyze this, it's symmetrical for 3D. Cross product for [x1, y1, 0] and [x2, y2, 0] is [0, 0, x1*y2 - y1*x2]. This equation then translates into: