Determine if a line passes through a triangle ...

Question

Math gurus...

I am looking for a way to tell if a line passes through a triangle as shown in the diagram below - the line described by the points p0 and p1 pass through the triangle described by the vertices v0, v1, v2:

I will readily admit, I don't have a clue -- so any help is appreciated as always!

Answer 1

The triangle $\Delta(v_0,v_1,v_2)$ defines a plane $\Pi$. If the line $\ell$ is not parallel to $\Pi$ it will intersect the plane in exactly one point $p$. Then we can apply three determinants $det(p,v_0,v_1)$, $det(p,v_1,v_2)$, and $det(p,v_2,v_0)$ determine the orientation (sign) and know if $p$ lies inside of $\Delta$, if so then $\ell$ intersects $\Delta$.

To calculate $p$ we can use the parametric form (Wikipedia):

$\Pi$: $v_0 + (v_1 - v_0)u + (v_2-v_0)w$

Assuming $\ell$ is defined by two points $p_0$ and $p_1$. Then we can write the point of intersection as:

$p_0 + (p_1-p_0)t = v_0 + (v_1 - v_0)u + (v_2-v_0)w$

$\Leftrightarrow p_0 - v_0 = (p_0 - p_1)t + (v_1 - v_0)u + (v_2-v_0)w$

Three equations (one for each $x$, $y$, and $z$) three unknown variables ($t$, $u$, and $w$) gives us an exact solution.

Then $p$ lies in the plane $\Pi$ and we can see the problem as $2D$ point location problem where we have to find out if $p$ lies inside of $\Delta$. Here we apply the three determines as explained above.

---

EDIT: Coplanarity was given later and only in the comments.

In case all points a coplanar we can simply calculate $det(p_0,p_1,v_0)$, $det(p_0,p_1,v_1)$, and $det(p_0,p_1,v_2)$. If one sign is different the line passes trough $\Delta$ otherwise it does not. (This variant was already described by another answer but as it seems it was deleted.)

Answer 2

Ingredients:

1) Equation of a plane determined by three points in the space.

2) Parametric equation of the line T passing through $p_0,p_1$, and of the three lines bordure of the triangle.

3) Put line T coordinates obtained in the plane equation.

4)Put you triangle inside a parallepipede L $(x_{min},x_{max})\times (y_{min},y_{max})$

The line passes through the plane if in 3) we get equation verified for any point of T.

The line T intersectes the triangle if the point of intersections of T with line bordures when they exist are in L.