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

Question

Is there an easy way to determine if a point is inside a triangle? It's 2D, not 3D.

Answer 1

I just want to use some simple vector math to explain the barycentric coordinates solution which Andreas had given, it will be way easier to understand.

1. Area A is defined as any vector given by s * v02 + t * v01, with condition s >= 0 and t >= 0. If any point inside the triangle v0, v1, v2, it must be inside Area A.

2. If further restrict s, and t belongs to [0, 1]. We get Area B which contains all vectors of s * v02 + t * v01, with condition s, t belongs to [0, 1]. It is worth to note that the low part of the Area B is the mirror of Triangle v0, v1, v2. The problem comes to if we can give certain condition of s, and t, to further excluding the low part of Area B.

3. Assume we give a value s, and t is changing in [0, 1]. In the following pic, point p is on the edge of v1v2. All the vectors of s * v02 + t * v01 which are along the dash line by simple vector sum. At v1v2 and dash line cross point p, we have:

(1-s)|v0v2| / |v0v2| = tp|v0v1| / |v0v1|

we get 1 - s = tp, then 1 = s + tp. If any t > tp, which 1 < s + t where is on the double dash line, the vector is outside the triangle, any t <= tp, which 1 >= s + t where is on single dash line, the vector is inside the triangle.

Then if we given any s in [0, 1], the corresponding t must meet 1 >= s + t, for the vector inside triangle.

So finally we get v = s * v02 + t * v01, v is inside triangle with condition s, t, s+t belongs to [0, 1]. Then translate to point, we have

p - p0 = s * (p1 - p0) + t * (p2 - p0), with s, t, s + t in [0, 1]

which is the same as Andreas' solution to solve equation system p = p0 + s * (p1 - p0) + t * (p2 - p0), with s, t, s + t belong to [0, 1].

Answer 2

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);
}

Answer 3

By using the analytic solution to the barycentric coordinates (pointed out by Andreas Brinck) and:

• not distributing the multiplication over the parenthesized terms
• avoiding computing several times the same terms by storing them
• reducing comparisons (as pointed out by coproc and Thomas Eding)

one can minimize the number of "costy" operations:

function ptInTriangle(p, p0, p1, p2) {
    var dX = p.x-p2.x;
    var dY = p.y-p2.y;
    var dX21 = p2.x-p1.x;
    var dY12 = p1.y-p2.y;
    var D = dY12*(p0.x-p2.x) + dX21*(p0.y-p2.y);
    var s = dY12*dX + dX21*dY;
    var t = (p2.y-p0.y)*dX + (p0.x-p2.x)*dY;
    if (D<0) return s<=0 && t<=0 && s+t>=D;
    return s>=0 && t>=0 && s+t<=D;
}

(code can be pasted in Perro Azul jsfiddle)

Leading to:

• variable "recalls": 30
• variable storage: 7
• additions: 4
• substractions: 8
• multiplications: 6
• divisions: none
• comparisons: 4

This compares quite well with Kornel Kisielewicz solution (25 recalls, 1 storage, 15 substractions, 6 multiplications, 5 comparisons), and might be even better if clockwise/counter-clockwise detection is needed (which takes 6 recalls, 1 addition, 2 substractions, 2 multiplications and 1 comparison in itself, using the analytic solution determinant, as pointed out by rhgb).

Answer 4

Supposedly high-performance code which I adapted in JavaScript(article below):

function pointInTriangle (p, p0, p1, p2) {
  return (((p1.y - p0.y) * (p.x - p0.x) - (p1.x - p0.x) * (p.y - p0.y)) | ((p2.y - p1.y) * (p.x - p1.x) - (p2.x - p1.x) * (p.y - p1.y)) | ((p0.y - p2.y) * (p.x - p2.x) - (p0.x - p2.x) * (p.y - p2.y))) >= 0;
}

pointInTriangle (p, p0, p1, p2) - for counter-clockwise triangles

pointInTriangle (p, p0, p1, p2) - for clockwise triangles

Look in jsFiddle (performance test included), there's also winding checking in a separate function http://jsfiddle.net/z7x0udf7/3/

Inspired by this: http://www.phatcode.net/articles.php?id=459

Answer 5

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.

Answer 6

Other function in python, faster than Developer's method (for me at least) and inspired by Cédric Dufour solution:

def ptInTriang(p_test, p0, p1, p2):       
     dX = p_test[0] - p0[0]
     dY = p_test[1] - p0[1]
     dX20 = p2[0] - p0[0]
     dY20 = p2[1] - p0[1]
     dX10 = p1[0] - p0[0]
     dY10 = p1[1] - p0[1]

     s_p = (dY20*dX) - (dX20*dY)
     t_p = (dX10*dY) - (dY10*dX)
     D = (dX10*dY20) - (dY10*dX20)

     if D > 0:
         return (  (s_p >= 0) and (t_p >= 0) and (s_p + t_p) <= D  )
     else:
         return (  (s_p <= 0) and (t_p <= 0) and (s_p + t_p) >= D  )

You can test it with:

X_size = 64
Y_size = 64
ax_x = np.arange(X_size).astype(np.float32)
ax_y = np.arange(Y_size).astype(np.float32)
coords=np.meshgrid(ax_x,ax_y)
points_unif = (coords[0].reshape(X_size*Y_size,),coords[1].reshape(X_size*Y_size,))
p_test = np.array([0 , 0])
p0 = np.array([22 , 8]) 
p1 = np.array([12 , 55]) 
p2 = np.array([7 , 19]) 
fig = plt.figure(dpi=300)
for i in range(0,X_size*Y_size):
    p_test[0] = points_unif[0][i]
    p_test[1] = points_unif[1][i]
    if ptInTriang(p_test, p0, p1, p2):
        plt.plot(p_test[0], p_test[1], '.g')
    else:
        plt.plot(p_test[0], p_test[1], '.r')

It takes a lot to plot, but that grid is tested in 0.0195319652557 seconds against 0.0844349861145 seconds of Developer's code.

Finally the code comment:

# Using barycentric coordintes, any point inside can be described as:
# X = p0.x * r + p1.x * s + p2.x * t
# Y = p0.y * r + p1.y * s + p2.y * t
# with:
# r + s + t = 1  and 0 < r,s,t < 1
# then: r = 1 - s - t
# and then:
# X = p0.x * (1 - s - t) + p1.x * s + p2.x * t
# Y = p0.y * (1 - s - t) + p1.y * s + p2.y * t
#
# X = p0.x + (p1.x-p0.x) * s + (p2.x-p0.x) * t
# Y = p0.y + (p1.y-p0.y) * s + (p2.y-p0.y) * t
#
# X - p0.x = (p1.x-p0.x) * s + (p2.x-p0.x) * t
# Y - p0.y = (p1.y-p0.y) * s + (p2.y-p0.y) * t
#
# we have to solve:
#
# [ X - p0.x ] = [(p1.x-p0.x)   (p2.x-p0.x)] * [ s ]
# [ Y - p0.Y ]   [(p1.y-p0.y)   (p2.y-p0.y)]   [ t ]
#
# ---> b = A*x ; ---> x = A^-1 * b
# 
# [ s ] =   A^-1  * [ X - p0.x ]
# [ t ]             [ Y - p0.Y ]
#
# A^-1 = 1/D * adj(A)
#
# The adjugate of A:
#
# adj(A)   =   [(p2.y-p0.y)   -(p2.x-p0.x)]
#              [-(p1.y-p0.y)   (p1.x-p0.x)]
#
# The determinant of A:
#
# D = (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x)
#
# Then:
#
# s_p = { (p2.y-p0.y)*(X - p0.x) - (p2.x-p0.x)*(Y - p0.Y) }
# t_p = { (p1.x-p0.x)*(Y - p0.Y) - (p1.y-p0.y)*(X - p0.x) }
#
# s = s_p / D
# t = t_p / D
#
# Recovering r:
#
# r = 1 - (s_p + t_p)/D
#
# Since we only want to know if it is insidem not the barycentric coordinate:
#
# 0 < 1 - (s_p + t_p)/D < 1
# 0 < (s_p + t_p)/D < 1
# 0 < (s_p + t_p) < D
#
# The condition is:
# if D > 0:
#     s_p > 0 and t_p > 0 and (s_p + t_p) < D
# else:
#     s_p < 0 and t_p < 0 and (s_p + t_p) > D
#
# s_p = { dY20*dX - dX20*dY }
# t_p = { dX10*dY - dY10*dX }
# D = dX10*dY20 - dY10*dX20