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.

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?

share|improve this question
    
You might be able to adapt this... –  J. M. 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

1 Answer 1

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.

share|improve this answer
    
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

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.