How to determine if a point is in a 2D triangle? [closed]

Question

In general, the simplest (and quite optimal) algorithm is checking on which side of the half-plane created by the edges the point is.

Here's some high quality info in this topic on GameDev, including performance issues.

And here's some code to get you started:

float sign (fPoint p1, fPoint p2, fPoint p3)
{
    return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}

bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
    float d1, d2, d3;
    bool has_neg, has_pos;

    d1 = sign(pt, v1, v2);
    d2 = sign(pt, v2, v3);
    d3 = sign(pt, v3, v1);

    has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
    has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);

    return !(has_neg && has_pos);
}

Solve the following equation system:

p = p0 + (p1 - p0) * s + (p2 - p0) * t

The point p is inside the triangle if 0 <= s <= 1 and 0 <= t <= 1 and s + t <= 1.

s,t and 1 - s - t are called the barycentric coordinates of the point p.

I agree with Andreas Brinck, barycentric coordinates are very convenient for this task. Note that there is no need to solve an equation system every time: just evaluate the analytical solution. Using Andreas' notation, the solution is:

s = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py);
t = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py);

where Area is the (signed) area of the triangle:

Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y);

Just evaluate s, t and 1-s-t. The point p is inside the triangle if and only if they are all positive.

EDIT: Note that the above expression for the area assumes that the triangle node numbering is counter-clockwise. If the numbering is clockwise, this expression will return a negative area (but with correct magnitude). The test itself (s>0 && t>0 && 1-s-t>0) doesn't depend on the direction of the numbering, however, since the expressions above that are multiplied by 1/(2*Area) also change sign if the triangle node orientation changes.

EDIT 2: For an even better computational efficiency, see coproc's comment below (which makes the point that if the orientation of the triangle nodes (clockwise or counter-clockwise) is known beforehand, the division by 2*Area in the expressions for s and t can be avoided). See also Perro Azul's jsfiddle-code in the comments under Andreas Brinck's answer.

I wrote this code before a final attempt with Google and finding this page, so I thought I'd share it. It is basically an optimized version of Kisielewicz answer. I looked into the Barycentric method also but judging from the Wikipedia article I have a hard time seeing how it is more efficient (I'm guessing there is some deeper equivalence). Anyway, this algorithm has the advantage of not using division; a potential problem is the behavior of the edge detection depending on orientation.

bool intpoint_inside_trigon(intPoint s, intPoint a, intPoint b, intPoint c)
{
    int as_x = s.x-a.x;
    int as_y = s.y-a.y;

    bool s_ab = (b.x-a.x)*as_y-(b.y-a.y)*as_x > 0;

    if((c.x-a.x)*as_y-(c.y-a.y)*as_x > 0 == s_ab) return false;

    if((c.x-b.x)*(s.y-b.y)-(c.y-b.y)*(s.x-b.x) > 0 != s_ab) return false;

    return true;
}

In words, the idea is this: Is the point s to the left of or to the right of both the lines AB and AC? If true, it can't be inside. If false, it is at least inside the "cones" that satisfy the condition. Now since we know that a point inside a trigon (triangle) must be to the same side of AB as BC (and also CA), we check if they differ. If they do, s can't possibly be inside, otherwise s must be inside.

Some keywords in the calculations are line half-planes and the determinant (2x2 cross product). Perhaps a more pedagogical way is probably to think of it as a point being inside iff it's to the same side (left or right) to each of the lines AB, BC and CA. The above way seemed a better fit for some optimization however.

C# version of the barycentric method posted by andreasdr and Perro Azul. I added a check to abandon the area calculation when s and t have opposite signs (and neither is zero), since potentially avoiding one-third of the multiplication cost seems justified.

public static bool PointInTriangle(Point p, Point p0, Point p1, Point p2)
{
    var s = (p0.X - p2.X) * (p.Y - p2.Y) - (p0.Y - p2.Y) * (p.X - p2.X);
    var t = (p1.X - p0.X) * (p.Y - p0.Y) - (p1.Y - p0.Y) * (p.X - p0.X);

    if ((s < 0) != (t < 0) && s != 0 && t != 0)
        return false;

    var d = (p2.X - p1.X) * (p.Y - p1.Y) - (p2.Y - p1.Y) * (p.X - p1.X);
    return d == 0 || (d < 0) == (s + t <= 0);
}

update 2021:
This version correctly handles triangles specified in either winding direction (clockwise vs. counterclockwise). Note that for points that lie exactly on the triangle edge, some other answers on this page give inconsistent results depending on the order in which the triangle's three points are listed. Such points are considered "in" the triangle, and this code correctly returns true regardless of winding direction.

Java version of barycentric method:

class Triangle {
    Triangle(double x1, double y1, double x2, double y2, double x3,
            double y3) {
        this.x3 = x3;
        this.y3 = y3;
        y23 = y2 - y3;
        x32 = x3 - x2;
        y31 = y3 - y1;
        x13 = x1 - x3;
        det = y23 * x13 - x32 * y31;
        minD = Math.min(det, 0);
        maxD = Math.max(det, 0);
    }

    boolean contains(double x, double y) {
        double dx = x - x3;
        double dy = y - y3;
        double a = y23 * dx + x32 * dy;
        if (a < minD || a > maxD)
            return false;
        double b = y31 * dx + x13 * dy;
        if (b < minD || b > maxD)
            return false;
        double c = det - a - b;
        if (c < minD || c > maxD)
            return false;
        return true;
    }

    private final double x3, y3;
    private final double y23, x32, y31, x13;
    private final double det, minD, maxD;
}

The above code will work accurately with integers, assuming no overflows. It will also work with clockwise and anticlockwise triangles. It will not work with collinear triangles (but you can check for that by testing det==0).

The barycentric version is fastest if you are going to test different points with the same triangle.

The barycentric version is not symmetric in the 3 triangle points, so it is likely to be less consistent than Kornel Kisielewicz's edge half-plane version, because of floating point rounding errors.

Credit: I made the above code from Wikipedia's article on barycentric coordinates.