# What is an efficient 2D line-segment-versus-triangle intersection test?

In a 2D plane, I have a line segment (P0 and P1) and a triangle, defined by three points (t0, t1 and t2).

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.

Everything is in 2D, so I can't expect the usual ray-triangle intersection test (3D version) to work.

Edit: Same question is asked on math.SE, but I think asking here is also appropriate as this is as much mathematics as game development, and the approach may be different also.

Here is an algorithm for intersection only (doesn't cover touching) that I believe is fast.

• if t0, t1 and t2 are all on the same side of line P0P1, return NOT INTERSECTING
• if P0 AND P1 are on the other side of line t0t1 as t2, return NOT INTERSECTING
• if P0 AND P1 are on the other side of line t1t2 as t0, return NOT INTERSECTING
• if P0 AND P1 are on the other side of line t2t0 as t1, return NOT INTERSECTING
• otherwise, return INTERSECTING

To check whether point P and point Q are on the same side of line AB, compare the signs of the Z coordinates of AB^AP and AB^AQ where ^ is the cross product.

The following code should work:

/* Check whether P and Q lie on the same side of line AB */
float Side(vec2 p, vec2 q, vec2 a, vec2 b)
{
float z1 = (b.x - a.x) * (p.y - a.y) - (p.x - a.x) * (b.y - a.y);
float z2 = (b.x - a.x) * (q.y - a.y) - (q.x - a.x) * (b.y - a.y);
return z1 * z2;
}

/* Check whether segment P0P1 intersects with triangle t0t1t2 */
int Intersecting(vec2 p0, vec2 p1, vec2 t0, vec2 t1, vec2 t2)
{
/* Check whether segment is outside one of the three half-planes
* delimited by the triangle. */
float f1 = Side(p0, t2, t0, t1), f2 = Side(p1, t2, t0, t1);
float f3 = Side(p0, t0, t1, t2), f4 = Side(p1, t0, t1, t2);
float f5 = Side(p0, t1, t2, t0), f6 = Side(p1, t1, t2, t0);
/* Check whether triangle is totally inside one of the two half-planes
* delimited by the segment. */
float f7 = Side(t0, t1, p0, p1);
float f8 = Side(t1, t2, p0, p1);

/* If segment is strictly outside triangle, or triangle is strictly
* apart from the line, we're not intersecting */
if ((f1 < 0 && f2 < 0) || (f3 < 0 && f4 < 0) || (f5 < 0 && f6 < 0)
|| (f7 > 0 && f8 > 0))
return NOT_INTERSECTING;

/* If segment is aligned with one of the edges, we're overlapping */
if ((f1 == 0 && f2 == 0) || (f3 == 0 && f4 == 0) || (f5 == 0 && f6 == 0))
return OVERLAPPING;

/* If segment is outside but not strictly, or triangle is apart but
* not strictly, we're touching */
if ((f1 <= 0 && f2 <= 0) || (f3 <= 0 && f4 <= 0) || (f5 <= 0 && f6 <= 0)
|| (f7 >= 0 && f8 >= 0))

/* If both segment points are strictly inside the triangle, we
* are not intersecting either */
if (f1 > 0 && f2 > 0 && f3 > 0 && f4 > 0 && f5 > 0 && f6 > 0)
return NOT_INTERSECTING;

/* Otherwise we're intersecting with at least one edge */
return INTERSECTING;
}


There is a lot of factoring possible here; it's possible the compiler will cleverly reuse partial results across calls to Side if it's inlined.

Edit: implement test for touching and overlapping in addition to intersecting.

• Yes, I would need algorithm to check for points that fall exactly on the lines – Graviton Dec 15 '11 at 12:08
• @Graviton: Okay, it should now work for exactly touching, too. – sam hocevar Dec 15 '11 at 15:29
• @SamHocevar Hey Sam! I tried this algorithm and noticed that it returns true whenever the LINE (the endless one) intersects the triangle and not the SEGMENT (the line limited by two points). The only change I made to your code was cutting out the overlapping/being inside checks as I need this to check triangleVStriangle collision (which includes one triangle being inside another) so I only check the first 8 equations and if the segment is strictly outside the triangle(...). Did I do anything wrong or it was intended to work like this? – cubrman Oct 20 '14 at 13:40

The bIg question here is what does your outer loop look like? I.e. Are you intersecting many lines with many triangles, one line to many triangles or many lines to one triangle? Or is it just N pairs of a triangle and a line? Only the last case (which sounds to be the most unlikely case) will best be accelerated by a faster segment to triangle intersection test.

Depending on what the scenario is, you may want to put your triangles OR your line segments into a spatial tree structure of some kind (if your segments are very long (relatively speaking), you can consider a spatial wtructure built on a duality mapping of gradient and offset). E.g. A grid, quad-tree or kd-tree will allow you to test multiple triangles or multiple line segments simultaneously.

If you really do have just one triangle and one line segment, performance shouldn't matter.

I should add, that the above will also dictate what type of primitive intersection test is the most efficient. If after traversal you know that the line segment intersects the bounding box of a triangle, then it also implies that an intersection is likely, which means that early out segment or edge sideness tests are likely wasted computation.

AFAIK you can check collision of each edge of triangle and even if one of the was true, the line segment collides the triangle. according to wikipage you can easily compute intersection point of two lines, in the rare case that you have divisor is zero it means two lines are parralel so they can't collide at all!

then you have to check if the collision point is a part of both line segments, it's also easily done:

// assume we want to check if I (intersection point) is
// between p0 and p1

if (dotproduct(P0-I,p1-I) > 0)
return false;
else
return true;

• Also, if it intersects with more then two sides of the triangle, it passes through – dann.dev Dec 15 '11 at 4:32

here is a routine that we use in our game engine. It can check if two line segments are not intersecting, intersecting or just parallel to each other. If they are intersecting, it will return the intersection XY position. It is used in our PolyPoint Collision System where it can auto trace a sprite image and put a polygon outline around it, then using this routine we walk the line segments of the colliding sprite outlines checking for intersection.

TLineIntersection = (
liNone,
liTrue,
liParallel
);

function  LineIntersection(X1, Y1, X2, Y2, X3, Y3, X4, Y4: Integer; var X, Y: Integer): TLineIntersection;
var
Ax,Bx,Cx,Ay,By,Cy,d,e, f, num: Integer;
offset: Integer;
x1lo,x1hi,y1lo,y1hi: Integer;
begin

Result := liNone;

Ax := x2-x1;
Bx := x3-x4;

if (Ax<0) then      // X bound box test
begin
x1lo := x2;
x1hi := x1;
end else
begin
x1hi := x2;
x1lo := x1;
end;

if(Bx>0) then
begin
if (x1hi < x4) or (x3 < x1lo) then Exit;
end else
begin
if (x1hi < x3)  or (x4 < x1lo) then Exit;
end;

Ay := y2-y1;
By := y3-y4;

if (Ay<0) then // Y bound box test
begin
y1lo := y2;
y1hi := y1;
end else
begin
y1hi := y2;
y1lo := y1;
end;

if (By>0) then
begin
if (y1hi < y4) or (y3 < y1lo) then Exit;
end else
begin
if (y1hi < y3) or (y4 < y1lo) then Exit;
end;

Cx := x1-x3;
Cy := y1-y3;
d  := By*Cx - Bx*Cy;          // alpha numerator
f  := Ay*Bx - Ax*By;          // both denominator

if(f>0) then                  // alpha tests
begin
if (d<0) or (d>f) then Exit;
end else
begin
if (d>0) or (d<f) then Exit
end;

e := Ax*Cy - Ay*Cx;                    // beta numerator
if (f>0) then                // beta tests
begin
if (e<0) or (e>f) then Exit;
end else
begin
if (e>0) or (e<f) then Exit;
end;

// compute intersection coordinates

if(f=0) then
begin
Result := liParallel;
Exit;
end;

num := d*Ax;                // numerator
if SameSignInt(num, f) then
offset := f div 2
else
offset := -f div 2;
x := x1 + (num+offset) div f;                       // intersection x

num := d*Ay;
if SameSignInt(num, f) then
offset := f div 2
else
offset := -f div 2;

y := y1 + (num+offset) div f;                          // intersection y

Result := liTrue;
end;