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

Question

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.

Answer 1

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))
        return TOUCHING;

    /* 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.

Answer 2

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.

Answer 3

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;

Answer 4

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;