Fast 2D Line–Triangle Intersection Test

To test an infinite line against a filled 2D triangle, you do not need to find where the line crosses the triangle’s edges. Instead, check which side of the line each triangle vertex lies on. A line intersects the closed triangle if its vertices are on both sides, or at least one vertex lies on the line.

This test is fast: it needs three 2D cross products and comparisons, with no square roots or division. It assumes the line has a nonzero direction vector. The triangle may be listed clockwise or counterclockwise; its vertex order does not affect the result.

The signed-side test

Represent the line by a point $P=(p_x,p_y)$ and a nonzero direction $D=(d_x,d_y)$. For each triangle vertex $V_i=(x_i,y_i)$, compute

$$s_i = D \times (V_i-P) = d_x(y_i-p_y)-d_y(x_i-p_x).$$

The sign of $s_i$ tells you which side of the line the vertex is on. A zero value means the vertex is on the line. In code-like form:

s0 = cross(D, V0 - P)
s1 = cross(D, V1 - P)
s2 = cross(D, V2 - P)

intersects = not (all three are positive or all three are negative)

Equivalently, let lo be the smallest of the three values and hi the largest. The closed triangle intersects the line exactly when lo <= 0 and hi >= 0.

Why the test works

The signed-side value is an affine function of the point’s coordinates. As you move across the triangle, its value changes continuously. If all three vertices have strictly positive values, then every point in the triangle has a positive value too, so the triangle is entirely on one side of the line. The same reasoning applies if all values are strictly negative.

If some values are positive and others negative, the segment joining vertices with opposite signs crosses the line. That segment is inside the filled triangle, so the line intersects the triangle. If a value is zero, that vertex itself is an intersection point. This also handles a line that touches the triangle at a vertex or runs along one of its edges.

Worked example

Take the line through $P=(0,1)$ with direction $D=(1,0)$, so the line is $y=1$. Let the triangle vertices be

$$V_0=(0,0),\qquad V_1=(3,0),\qquad V_2=(1,2).$$

For this horizontal direction, the cross product reduces to the vertex’s vertical offset from the line:

$$\begin{aligned} s_0 &= 1(0-1)-0(0-0)=-1,\\ s_1 &= 1(0-1)-0(3-0)=-1,\\ s_2 &= 1(2-1)-0(1-0)=1. \end{aligned}$$

There are both negative and positive values, so the line intersects the triangle. In fact, it crosses the triangle at $(0.5,1)$ and $(2,1)$, but the sign test can answer the yes-or-no question without calculating those points.

If the same triangle is tested against $y=3$, using $P=(0,3)$ and the same direction, the values are $-3,-3,-1$. They are all negative, so the triangle does not intersect that line.

Implementation and numerical care

A simple implementation can compute the three values and compare their minimum and maximum. Prefer these comparisons over multiplying values to test their signs: products can overflow or underflow for large or tiny coordinates.

The formula uses ordinary floating-point arithmetic in most applications. If coordinates may be nearly collinear, rounding can make a theoretically zero cross product slightly positive or negative. A fixed tolerance is not reliable for every coordinate scale. For more dependable results, use a scale-aware tolerance or a robust orientation predicate; exact-predicate methods are especially useful in geometry software where incorrect classifications cause downstream failures.

A tolerance changes the meaning of the test: values treated as zero count as touching, so near misses may be reported as intersections. Choose that behavior deliberately. Also reject a line direction with $D=(0,0)$, since it does not define a line.

If you mean a segment, ray, or half-line

The sign test is for an infinite line. It can report an intersection beyond the endpoints of a segment. For a segment from $S$ to $E$, parameterize its points as $X(t)=S+t(E-S)$ for $0\le t\le1$. To test a segment against a triangle, clip this parameter interval against the triangle’s three edge half-planes.

For a counterclockwise triangle, each edge from $A$ to $B$ imposes the condition

$$(B-A)\times(X(t)-A)\ge 0.$$

Substituting $X(t)$ gives a linear inequality in $t$. Intersect the allowed intervals from all three edges with $[0,1]$. If the final interval is nonempty, the segment intersects the closed triangle. Reverse the inequality for a clockwise triangle, or first determine the triangle’s orientation. A ray uses the same approach but starts with the parameter range $t\ge0$ instead of $0\le t\le1$.

Common mistakes

• Treating a segment as an infinite line: Opposite vertex signs establish a line intersection, not necessarily a segment intersection.
• Rejecting zero values: A zero means contact with the line, which counts for a closed triangle. Excluding zero incorrectly misses vertex or edge touches.
• Depending on triangle winding: The line-side test does not use triangle edge orientation. Winding matters only when clipping against oriented triangle edges.
• Using a zero direction: The cross-product test is meaningful only when the direction vector is nonzero.