C program to check whether a point lies inside a triangle

1. Jul 30, 2006

Gagan A

Ok the question goes as:
Take four co-ordinates and check whether the fourth coordinate lies inside the triangle. I first did it with the area concept, that is, find the area of the whole triangle, then find the area of the three trangles formed by the fourth coordinate. if the sum of the other three areas comes equal to the total area then the point lies inside the triangle. But after successfull compilation i realized that my program will fail if there are floating point integers. So I did it another way.

#include<stdio.h>
int main()
{
float a,b,c,d,e,f,g,h,k,l,m,n,o,p; //(a,b),(c,d),(e,f),(g,h) are coordinates. Others are variables.
scanf("%f%f%f%f%f%f%f%f",&a,&b,&c,&d,&e,&f,&g,&h); //Take input.

k = e*(b-d) + f*(c-a) + a*d - b*c;
l = g*(b-d) + h*(c-a) + a*d - b*c;

m = a*(f-d) + b*(c-e) + e*d - f*c;
n = g*(f-d) + h*(c-e) + e*d - f*c;

o = c*(b-f) + d*(e-a) + a*f - b*e;
p = g*(b-f) + h*(e-a) + a*f - b*e;

if (l==0 || n==0 || p==0) printf("YES\n"); // If the point lies on side of triangle. I think this needs some modification.
else if ((k/l>=0) && (m/n>=0) && (o/p>=0)) printf("YES\n");
else printf("NO\n");

return 0;
}

This is based on the concept that if the fourth coordinnate and the coordinates of the triangle lie on the same side the answer wil be yes. For that, find the equation of line passing through (a,b) and (c,d), Simplify the equation to form l = 0, and then put (e,f) and (g,h).
But the problem I am facing is that when the point lies in line of the triangle (you extend a line of the triangle and the point is on the extended portion) the answer still comes to be yes. I don't want that. Could someone please tell me how can I do that?

Last edited: Jul 30, 2006
2. Jul 30, 2006

fargoth

combine your original way witht the existing one - if you got a yes answer - compare the areas of the original triangle and the triangle formed with the new point, and if the new area is bigger, the point is somewhere along the extended lines...

3. Jul 30, 2006

neurocomp2003

if your not to lazy see if your library has a book by Joseph O'rourke titled
Computational Geometry.