Popular Posts

Friday, July 29, 2011

Is given point lies inside a triangle

Given three points A,B,C which forms a triangle and a point P.Now check whether point P lies inside the triangle formed by ABC.
Solution : Trick is to check for each line of a triangle formed by any two of A,B,C whether point P and remaining point lies on same side or opposite side.If they lies on same side,it will form a triangle.

for line AB----->C,P should be on same side.
for line BC----->A,P should be on same side.
for line CA----->B,P should be on same side.

If it satisfies above three conditions,we can say point is inside the triangle.

Now how do we check whether two points lie on same side of a line?
Substitute the given points in the line and check if they are yielding result with same sign.
ex: eq is Px+Qy+R=0;
for points (X1,Y1),(X2,Y2),substitute these points in the equation..
after substituting,if  PX1+QY1+R and PX2+QY2+R have the same sign,both points are on same side else they are on opposite side.

Method 2 : Calculate areas of triangles ABP,BCP,ACP and ABC.if sum of these 3 triangle areas is equal to the main triangle area,point is inside the triangle.It is very complex to calculate the area of the triangle and if area is float value, comparison will be difficult(doesn't give accurate result).

No comments:

Post a Comment