Download Article and Source (39 kb)

I. Introduction

This article is about how to check if a point is inside a given triangle or not. Two approaches are shown and also implemented exemplary as Java applet. This description targets the twodimensional case.

So given is a triangle T with its three vertices V₁= (vx₁, vy₁), V₂= (vx₂, vy₂), V₃= (vx₃, vy₃) and a testpoint P = (px, py).
Question: Is P included in T?

II. Algorithm 1: "Crossproduct Side Algorithm"

Note that above name of this algorithm is not official, but my own invention (hope you like this name!). Note that following topic is quite similar to the discussion in my article about polygon convexity [1], but here we have a look from the other side.

Maybe you ask yourself now how the crossproduct is defined in 2D and how to interpret it geometrically? Well, the crossproduct is actually not well defined for the 2D case, but a common definition is

This is also known as 'perp dot' product and has some nice properties - if you are interested, read [2]. Also note that it returns a scalar and not a vector (in contrast to the 3D crossproduct) and is actually the same as the determinant of the two two-element vectors. From the latter fact, one (with that I mean a good mathematician) can derive following useful properties:

The figure on the left shows the perpDotProduct result geometrically.

So actually this all we need :) Calculate the perpDotProduct/crossproduct of all three points V₁, V₂, V₃ with the testpoint P. (It's important that P is either always the first argument or either always the second argument, otherwise you might get into trouble in the final check below!)
Call c₁ = crossproduct(V₁, P), c₂ = crossproduct(V₂, P) and c₃ = crossproduct(V₃, P).
The final point-in-triangle depends on the prior knowledge of the triangle:

• if you know that the vertices V₁, V₂, V₃ are given in clockwise order, then P is inside the triangle if
  c₁> 0 && c₂> 0 && c₃ > 0.
• if you know that the vertices V₁, V₂, V₃ are given in counterclockwise order, then P is inside the triangle if
  c₁< 0 && c₂< 0 && c₃ < 0.
• if you do know nothing about the given order of vertices V₁, V₂, V_3, then P is inside the triangle if
  (c₁> 0 && c₂> 0 && c₃ > 0) || (c₁< 0 && c₂< 0 && c₃ < 0).
  

III. Algorithm 2: "Barycentric Algorithm"

The barycentric approach is based on another mathematical point of view. Imagine that the triangle is part of a plane -that means all three vertices of the triangle lie inside this plane. So we can pick one vertice and the two edges of the triangle starting from this vertices span the whole plan:

Define w1 = V2 - V1 and w2 = V3 - V1. Then each point in the plane can be written as: P(s,t) = V1 + s * w1 + t * w2      s,t e R By limiting s and t by s >= 0, t >= 0 and (s + t) <= 1, then P(s,t) describes exactly the points inside the triangle!

So have an equation that gives us an arbitrary point inside the traingle by choosing values for s and that fulfill the three limitations s >=0, t >= 0 and (s + t) <= 1.
This means that for our testpoint P, we can describe it with this equation P(s,t) - and if s and t fulfill the requirements than P is inside T. Obviously, our goal is to calculate s and t for testpoint P -

Rearranging gives

or in vector notation:

Either we solve this by hand or apply Cramer's Rule [3] (note that for our special 2D case the determinant is calculated equally as the perpDotProduct!):

The final point-in-triangle is then

• P is inside the triangle if s >= 0 && t >= 0 && (s + t) <= 1.

That's it. Hope you enjoyed this article and find the applet + source useful!

References:

[1] Polygon Convexity
[2] The pleasures of "Perp Dot" Products by Hill in Graphics Gem IV on Google Books
[3] Cramer's Rule @ Wikipedia

Sunshine, December 2011

This site is part of Sunshine's Homepage