3

I've seen similar questions but could not solve my problem with those. My question is how to detect an intersection of a line segment and a triangle on a 2D coordinate system? I don't need the point of intersection, I just quickly need to decide whether the segment cuts into the triangle or not.

The Line segment is represented by two points, S (Sx,Sy). The triangle is represented by 3 points, T (T1x,T1y, T2x,T2y, T3x,T3y)

Your help is appreciated.

Martin Sleziak
  • 53,687
Gabor Peto
  • 131
  • 1
  • 1
    One option: Define the line segment as $S(u)=S_0+u(S_1-S_0),0\leq u\leq1$ and a triangle edge as $T(v)=T_0+v(T_1-T_0),0\leq v\leq1$. Then the line segment and the triangle edge intersect if there exists a pair $(u,v)$ satisfying $S(u)=T(v),0\leq u,v\leq1$. This may be harder than the original problem though. – Daryl Mar 28 '13 at 10:10

1 Answers1

0

All right, maybe we can go for an algorithm!

given the two end of the segment $A=(a_x,a_y),B=(b_x,b_y)$ and the three vertices of the triangle $C=(c_x,c_y),D=(d_x,d_y),E=(e_x,e_y)$

Intersection (A,B,C,D,E)

(1) if A is in the triangle and B is not (or vice versa) then return True

(2) if (Intersection(A,(A+B)/2,C,D,E) or Intersection((A+B)/2,B,C,D,E))
then return True else return False

Here is a method to check whether a point is in a triangle using cross product http://www.blackpawn.com/texts/pointinpoly/

bad one (thanks Daryl): To check if an end of the segment, say A, is in the triangle we can simply check it's coordinates against the triangle vertices ones:

For A to be in the triangle we should have $min \{c_x,d_x,e_x\} \leq a_x \leq max \{c_x,d_x,e_x\}$ and $min \{c_y,d_y,e_y\} \leq a_y \leq max \{c_y,d_y,e_y\}$

sciamp
  • 13
  • 4
  • Your check on $A$ only ensures it is in the bounding rectangle of the triangle. It is possible that it is not in the triangle. – Daryl Mar 28 '13 at 10:03
  • yes, you're right! thanks! – sciamp Mar 28 '13 at 10:12
  • So the current algorithm is not correct? It is not enough for me to check the bounding rectangle of the triangle. – Gabor Peto Mar 28 '13 at 15:34
  • the issues is the way i suggested to check if the point belong to the triangle (i.e. the procedure that corresponds to "A is in the triangle and B is not") but you can use the cross product method showed in http://www.blackpawn.com/texts/pointinpoly/ – sciamp Mar 28 '13 at 16:14