Sunday, March 18, 2012

Is point p inside a Triangle?


Check Whether Point Lie Inside, on or outside the triangle efficiently what will be time complexity & which data structure algorithm 
as you can see google asked they wants quality code & efficient algorithm.


An easier way than what Richie mentioned is to the following:


if a point P is inside triangle ABC, then


Area PAB + Area PBC + Area PAC == Area ABC


Area of a triangle = Math.sqrt(S(S-a)(S-b)(S-c))
S = (a+b+c)/2
Where a, b and c is the length of the sides of the triangle.


Code input/output:
3
1 0
5 7
8 0
x: 1.0 y: 0.0
x: 5.0 y: 7.0
x: 8.0 y: 0.0


Atotal: 24.5
Aabc: 24.5
Check if point p inside triangle ? true


Atotal: 39.5
Aabc: 24.5
Check if point p inside triangle ? false

No comments:

Post a Comment