Point inside a triangle or NOT

Problem

Given three corner points of a triangle, and one more point P. Write a function to check whether P lies within the triangle or not.

Example

For example, consider the following program, the function should return true for P(10, 15) and false for P’(30, 15)

              B(10,30)  
                / \\  
               /   \\  
              /     \\  
             /   P   \\      P'  
            /         \\  
     A(0,0) ----------- C(20,0)

Solution

Method 1 - Area of triangles made by point and other 2 vertices of triangle
Let the coordinates of three corners be (x1, y1), (x2, y2) and (x3, y3). And coordinates of the given point P be (x, y)

Calculate area of the given triangle, i.e., area of the triangle ABC in the above diagram. Area A = [ x1(y2 - y3) + x2(y3 - y1) + x3(y1-y2)]/2
Area A1 = Calculate area of the triangle PAB (using the same formula)
Area A2 = Calculate area of the triangle PBC
Area A3 = Calculate area of the triangle PAC
If P lies inside the triangle, then A1 + A2 + A3 must be equal to A.

Here is the code

float area(int x1, int y1, int x2, int y2, int x3, int y3)  
{  
   return Math.abs((x1\*(y2-y3) + x2\*(y3-y1)+ x3\*(y1-y2))/2.0);  
}  
  
boolean isInside(int x1, int y1, int x2, int y2, int x3, int y3, int x, int y)  
{     
   // Calculate area of triangle ABC   
   float A = area (x1, y1, x2, y2, x3, y3);  
   
   // Calculate area of triangle PBC     
   float A1 = area (x, y, x2, y2, x3, y3);  
   
   // Calculate area of triangle PAC     
   float A2 = area (x1, y1, x, y, x3, y3);  
   
   // Calculate area of triangle PAB      
   float A3 = area (x1, y1, x2, y2, x, y);  
     
   // Check if sum of A1, A2 and A3 is same as A   
   return (A == A1 + A2 + A3);  
}

But can this differentiate whether the point lies on the edges, I don’t thing so. It can only tell whether it is in triangle or not.

Method 2 - Using Barycentric coordinates
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](http://en.wikipedia.org/wiki/Barycentric_coordinates_%28mathematics%29) of the point `p`.  
  
Now, the barycentric coordinates, generally called `alpha`, `beta`, and `gamma`, are calculated as follows:

float alpha = ((p2.y - p3.y)*(p.x - p3.x) + (p3.x - p2.x)*(p.y - p3.y)) /
((p2.y - p3.y)*(p1.x - p3.x) + (p3.x - p2.x)*(p1.y - p3.y));
float beta = ((p3.y - p1.y)*(p.x - p3.x) + (p1.x - p3.x)*(p.y - p3.y)) /
((p2.y - p3.y)*(p1.x - p3.x) + (p3.x - p2.x)*(p1.y - p3.y));
float gamma = 1.0f - alpha - beta;

```If all of alpha, beta, and gamma are greater than 0, then the point p lies within the triangle made of points p1, p2, and p3.
The explanation behind this is that a point inside a triangle can be described using the points of the triangle, and three coefficients (one for each point, in the range [0,1]):

p = (alpha)\*p1 + (beta)\*p2 + (gamma)\*p3  

```Rearranging this function gives you the formula to compute barycentric coordinates, but I feel like the steps to do so might be beyond the scope of the question. They are provided on the Wikipedia page that I linked up top.  
  
**References**  

*   [http://www.geeksforgeeks.org/check-whether-a-given-point-lies-inside-a-triangle-or-not/](http://www.geeksforgeeks.org/check-whether-a-given-point-lies-inside-a-triangle-or-not/)
*   [http://stackoverflow.com/questions/13300904/determine-whether-point-lies-inside-triangle](http://stackoverflow.com/questions/13300904/determine-whether-point-lies-inside-triangle)

Problem

Example

Solution

See also