Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C program to check whether a point lies inside a triangle

  1. Jul 30, 2006 #1
    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.

    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. jcsd
  3. Jul 30, 2006 #2
    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...
  4. Jul 30, 2006 #3
    if your not to lazy see if your library has a book by Joseph O'rourke titled
    Computational Geometry.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook