Fast 2D Line Triangle Intersection test

In a 2D plane, I have a line segment ($P_0$ and $P_1$) and a triangle, defined by three points ($t_0$, $t_1$ and $t_2$).

My goal is to test, as efficiently as possible ( in terms of computational time), whether the line touches, or cuts through, or overlaps with one of the edge of the triangle.

What is the algorithm I can use for this?

-
You might be able to adapt this... –  Guess who it is. Dec 14 '11 at 7:10
@J.M., I think not. The ray-triangle intersection is in 3D, as such, we can talk about a ray passing through the triangle at a point. But this is not the situation in 2D. In 2D, the normal of the triangle and the 2D line is 90 degree apart. –  Graviton Dec 14 '11 at 7:24

Since both the triangle and the line are convex objects, they are separate (i.e. do not overlap) if and only if there exists a line so that the projections of the two objects onto the line do not overlap.

In your case it suffices to check this condition for four potential projection directions: the direction vectors of the edges, and the direction vector of the line segment.

Let $(x, y)$ be one of the four direction vectors mentioned above. Then $n := (y, -x)$ is a vector that is orthogonal to it. Calculate the dot product of $n$ with $t_0$, $t_1$ and $t_2$, which gives you three scalars. Set $t_{min}$ and $t_{max}$ to the minimum/maximum of these three. Do the same for $P_0$ and $P_1$, which gives you $p_{min}$ and $p_{max}$.

Now check the these two (min, max) ranges for overlap. If they are disjoint, your are done - the triangle and the line segment do not overlap. Otherwise, repeat the check for the next candidate direction. If the ranges overlap for all four of these, the line segment overlaps the triangle.

This procedure does not discriminate between partial overlap and inclusion (i.e. the line segment may lie entirely inside the triangle, without intersecting any of the edges). To detect the latter, test for containment rather than overlap in the (min, max) range check described above.

-
I read your answer a few times, I can't understand the logic behind it, mind to explain more? –  Graviton Dec 15 '11 at 2:33
For the fourth direction, don't you mean the vector normal to the line segment instead? –  Sam Hocevar Dec 15 '11 at 11:02
Sorry, please disregard; they're projection directions, all right. –  Sam Hocevar Dec 15 '11 at 12:04