Point in Triangle Algorithms |

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_{1}= (vx_{1}, vy_{1}), V_{2}= (vx_{2}, vy_{2}), V_{3}= (vx_{3}, vy_{3}) 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

perpDotProduct(v |

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:

perpDotProduct(v |

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_{1}, V_{2}, V_{3} 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_{1} = crossproduct(V_{1}, P), c_{2} = crossproduct(V_{2}, P) and c_{3} = crossproduct(V_{3}, P).

The final point-in-triangle depends on the prior knowledge of the triangle:

- if you know that the vertices V
_{1}, V_{2}, V_{3}are given in clockwise order, then P is inside the triangle if

c_{1}> 0 && c_{2}> 0 && c_{3}> 0. - if you know that the vertices V
_{1}, V_{2}, V_{3}are given in counterclockwise order, then P is inside the triangle if

c_{1}< 0 && c_{2}< 0 && c_{3}< 0. - if you do know nothing about the given order of vertices V
_{1}, V_{2}, V_{3, }then P is inside the triangle if

(c_{1}> 0 && c_{2}> 0 && c_{3}> 0) || (c_{1}< 0 && c_{2}< 0 && c_{3}< 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 w Then each point in the plane can be written as: By limiting s and t by |

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 -

V |

Rearranging gives

s * w |

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!):

s = determinant(P - V |

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