Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there an algorithm available to determine if a point P lies inside a triangle ABC defined as three points A, B, and C? (The three line segments of the triangle can be determined as well as the centroid if they are needed.)

Grid space is defined as Screen Space, that is, 2D Cartesian with the Y-Axis flipped so "up" is negative y and the origin is the upper left corner.

share|improve this question

5 Answers 5

up vote 4 down vote accepted

This is a fairly well known algorithm. It all comes down to using the cross product. Define the vectors $AB$, $BC$ and $CA$ and the vectors $AP$, $BP$ and $CP$. Then $P$ is inside the triangle formed by $A, B$ and $C$ if and only if all of the cross products $AB\times AP$, $BC\times BP$ and $CA\times CP$ point in the same direction relative to the plane. That is, either all of them point out of the plane, or all of them point into the plane.

Update: this test can be performed using dot products.

Update 2: As emphasised in the comments, you only have to compare signs of the third components.

share|improve this answer
    
Remind me again: A vector is defined as the two points at each end, and...what's the definition of the cross product and dot product? (For once, wikipedia isn't the way to go for a "simple" answer. :P ) –  Casey Jul 14 '11 at 1:25
    
@Casey: actually the formula for cross product is in Wikipedia. Your vectors have only two components, so $(x_1,y_1,0)\times (x_2,y_2,0)=(0,0,x_1y_2-x_2y_1)$ and you just look at the signs of the third components. –  Ross Millikan Jul 14 '11 at 13:04
    
Worked great, thanks. –  Casey Jul 14 '11 at 19:45

I wrote a complete article about point in triangle test. It shows the barycentric, parametric and dot product based methods.

Then it deals with the accuracy problem occuring when a point lies exactly on one edge (with examples). Finally it exposes a complete new method based on point to edge distance.

http://totologic.blogspot.fr/2014/01/accurate-point-in-triangle-test.html

Enjoy !

share|improve this answer

Method

To test any ppoint $P=(x,y)$, first move the origin at one vertex, like $A$ such that $$ B \rightarrow B - A $$ $$ C \rightarrow C - A $$ $$ P \rightarrow P - A $$

Then I calculate the scalar $ d = x_B y_C - x_C y_B $ and the three Barycentric weights

$$ \begin{matrix} w_A = \frac{ x ( y_B-y_C) + y ( x_C-x_B) + x_B\; y_C - x_C\; y_B}{d} \\ w_B = \frac{ x\; y_C - y\; x_C }{d} \\ w_C = \frac{ y\; x_B - x\; y_B }{d} \end{matrix} $$

The point is inside when all weights are between $0\ldots1$.

Examples

Test Case 1

Example: $A=(1,1)$ $B=(4,2)$ $C=(2,7)$. Consider a point $P=(2,3)$ then the sclar is $d=17$ and three weights are: $w_A = \frac{8}{17}$, $w_B = \frac{4}{17}$ and $ w_C=\frac{5}{17}$ which are all $|w_i|<1$.

Test Case 2

On the other hand if $P=(1.5,5)$ then $w_A = \frac{13}{34} $, $w_B = -\frac{1}{17}$ and $ w_C=\frac{23}{34}$ and since $w_B$ does not fall between $0\ldots1$ then the point is outside.

Proof

Use homogeneous coordinates with $A=(x_A,y_A,1)$, $B=(x_B,y_B,1)$, $C=(x_C,y_C,1)$, $P=(x,y,1)$ and use the following relation $$ P = w_A\;A + w_B\;B+w_C\;C $$ to solve for $w_A$, $w_B$ and $w_C$.

The notice that the equation $w_A=0$ described the line $BC$ and the equation $w_A=1$ a line parallel to $BC$ through $A$. Similarly for the other weights. The region where all the weights are $w_i\geq0$ and $ w_i\leq1$ is the triangle described by $ABC$.

share|improve this answer

Yes, this problem certainly has come up a lot before. Eric Haines wrote about the more general "point in polygon" problem (whose algorithms can be vastly simplified for the triangular case) in Graphics Gems IV. He also presented a method using barycentric coordinates in this Dr. Dobb's Journal article.

share|improve this answer

I think you could check by computing the area of $\triangle ABC$, $\triangle ABP$, $\triangle BCP$, and $\triangle ACP$ (which can be done relatively easily from the coordinates of the points), and if $k_{\triangle ABC}=k_{\triangle ABP}+k_{\triangle BCP}+k_{\triangle ACP}$ (where $k_\_$ is the area), then $P$ is inside the triangle (or possibly on its boundary), but if $k_{\triangle ABC}< k_{\triangle ABP}+k_{\triangle BCP}+k_{\triangle ACP}$, $P$ is outside the triangle.

share|improve this answer
    
I believe this will be problematic if dealing with floating point numbers. –  M.B. Jul 13 '11 at 23:59
    
@M.B.: As an issue of precision? –  Isaac Jul 14 '11 at 0:01
    
Isaac: Yes. Comparing floating point numbers by equality is never advised. –  M.B. Jul 14 '11 at 0:03
    
@M.B.: Testing for equality isn't necessary—testing $k_{\triangle ABC}< k_{\triangle ABP}+k_{\triangle BCP}+k_{\triangle ACP}$ is sufficient to determine that $P$ is outside the triangle. –  Isaac Jul 14 '11 at 0:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.