# Check whether a given point lies inside a triangle or not

Check whether a given point lies inside a triangle or not – Geometric Algorithm – Given three corner points of a triangle, and one more point P.

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.

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:
Let the coordinates of three corners be (x1, y1), (x2, y2) and (x3, y3). And coordinates of the given point P be (x, y)

1) 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
2) Calculate area of the triangle PAB. We can use the same formula for this. Let this area be A1.
3) Calculate area of the triangle PBC. Let this area be A2.
4) Calculate area of the triangle PAC. Let this area be A3.
5) If P lies inside the triangle, then A1 + A2 + A3 must be equal to A.

[pastacode lang=”cpp” manual=”%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%20%0A%2F*%20A%20utility%20function%20to%20calculate%20area%20of%20triangle%20formed%20by%20(x1%2C%20y1)%2C%20%0A%20%20%20(x2%2C%20y2)%20and%20(x3%2C%20y3)%20*%2F%0Afloat%20area(int%20×1%2C%20int%20y1%2C%20int%20×2%2C%20int%20y2%2C%20int%20×3%2C%20int%20y3)%0A%7B%0A%20%20%20return%20abs((x1*(y2-y3)%20%2B%20×2*(y3-y1)%2B%20×3*(y1-y2))%2F2.0)%3B%0A%7D%0A%20%0A%2F*%20A%20function%20to%20check%20whether%20point%20P(x%2C%20y)%20lies%20inside%20the%20triangle%20formed%20%0A%20%20%20by%20A(x1%2C%20y1)%2C%20B(x2%2C%20y2)%20and%20C(x3%2C%20y3)%20*%2F%0Abool%20isInside(int%20×1%2C%20int%20y1%2C%20int%20×2%2C%20int%20y2%2C%20int%20×3%2C%20int%20y3%2C%20int%20x%2C%20int%20y)%0A%7B%20%20%20%0A%20%20%20%2F*%20Calculate%20area%20of%20triangle%20ABC%20*%2F%0A%20%20%20float%20A%20%3D%20area%20(x1%2C%20y1%2C%20×2%2C%20y2%2C%20×3%2C%20y3)%3B%0A%20%0A%20%20%20%2F*%20Calculate%20area%20of%20triangle%20PBC%20*%2F%20%20%0A%20%20%20float%20A1%20%3D%20area%20(x%2C%20y%2C%20×2%2C%20y2%2C%20×3%2C%20y3)%3B%0A%20%0A%20%20%20%2F*%20Calculate%20area%20of%20triangle%20PAC%20*%2F%20%20%0A%20%20%20float%20A2%20%3D%20area%20(x1%2C%20y1%2C%20x%2C%20y%2C%20×3%2C%20y3)%3B%0A%20%0A%20%20%20%2F*%20Calculate%20area%20of%20triangle%20PAB%20*%2F%20%20%20%0A%20%20%20float%20A3%20%3D%20area%20(x1%2C%20y1%2C%20×2%2C%20y2%2C%20x%2C%20y)%3B%0A%20%20%20%0A%20%20%20%2F*%20Check%20if%20sum%20of%20A1%2C%20A2%20and%20A3%20is%20same%20as%20A%20*%2F%0A%20%20%20return%20(A%20%3D%3D%20A1%20%2B%20A2%20%2B%20A3)%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%2F*%20Let%20us%20check%20whether%20the%20point%20P(10%2C%2015)%20lies%20inside%20the%20triangle%20%0A%20%20%20%20%20%20formed%20by%20A(0%2C%200)%2C%20B(20%2C%200)%20and%20C(10%2C%2030)%20*%2F%0A%20%20%20if%20(isInside(0%2C%200%2C%2020%2C%200%2C%2010%2C%2030%2C%2010%2C%2015))%0A%20%20%20%20%20printf%20(%22Inside%22)%3B%0A%20%20%20else%0A%20%20%20%20%20printf%20(%22Not%20Inside%22)%3B%0A%20%0A%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]

Ouptut:

` Inside`

## Branch And Bound | Set 4 (Job Assignment Problem)

Branch And Bound (Job Assignment Problem) – Branch And Bound – It is required to perform all jobs by assigning exactly one worker to each job.

## C++ Programming – Program to add two polynomials

C++ Programming – Program to add two polynomials – Mathematical Algorithms – Addition is simpler than multiplication of polynomials. We initialize result

## Branch and Bound | Set 3 (8 puzzle Problem)

Branch and Bound (8 puzzle Problem) – Branch and Bound – We have introduced Branch and Bound and discussed 0/1 Knapsack problem in below posts.

## C programming-Lucky Numbers

C programming-Lucky Numbers – Mathematical algorithms – Lucky numbers are subset of integers. let us see the process of arriving at lucky numbers.

## Add 1 to a given number

Add 1 to a given number – Bit Algorithm – Add 1 to a given number write a program to add 1 to a given number. You are not allowed to use operators like ‘+’,

## C Programming – Horner’s Method for Polynomial Evaluation

C Programming Horner’s Method for Polynomial Evaluation – Mathematical Algorithms – Input is in form of array say poly[] where poly[0] represent coefficient