CODEWITHSUNDEEP
cgeometry
Carpe Diem
Carpe Diem

Reputation: 107

If point is inside a triangle (help when point is on the boundary of triangle)

The following code tests whether a point is inside a triangle or not, it does everything correctly but whenever I specify a point on the triangle's boundary it says it is outside (I want it to be inside). Can anyone figure out what's wrong? (I did not write the following code, so please I understand the style is horrible ignore it... trust me it was worse before I cleaned up).

Say if I entered triangle with vertices A(0,0) B(10,0) C(0,10) and point (5,0) it will still show up as outside the triangle!

#include <stdio.h>

int test2( double px, double py, double m, double b ) {    
    if (py < m * px + b ) {
        return -1; // point is under line
    }else if ( py == m * px + b ){
        return 0; // point is on line
    } else {
        return 1; // point is over line
    }
}

int test1(double px, double py, double m,double b, double lx,double ly) {     
   return (test2(px,py, m,b) == test2(lx,ly,m,b));    
}

int tritest (double x0,double y0,double x1,double y1,double x2,double y2,double px, double py) {

   int line1, line2, line3;    
   double m01 = (y1-y0)/(x1-x0);    
   double b01 = m01 * -x1 + y1;    
   double m02, m12, b02, b12;    
   m02 = (y2-y0)/(x2-x0);    
   m12 = (y2-y1)/(x2-x1);    
   b02 = m02 * -x2 + y2;    
   b12 = m12 * -x2 + y2;

   // vertical line checks

   if( x1 == x0 ) {    
      line1 = ( (px <= x0) == (x2 <= x0) );    
   } else {    
      line1 = test1( px, py, m01, b01,x2,y2);    
   }

   if( x1 == x2 ) {    
      line2 = ( (px <= x2) == (x0 <= x2) );    
   } else {    
      line2 = test1(px,py, m12, b12,x0,y0);    
   }

   if( x2 == x0 ) {    
      line3 = ( (px <= x0 ) == (x1 <= x0) );} else {    
      line3 = test1(px, py, m02,b02,x1,y1);    
   }

   return line1 && line2 && line3;
}

int main(int argc, char* argv[]) {    
   double x0,y0,x1,y1,x2,y2,px;    
   double py;    
   int scanfsReturnValueAggregatedOverAllScanfs = 0;

   // get input

   printf("Triangle Vertex A (enter x,y): "); scanfsReturnValueAggregatedOverAllScanfs += scanf("%lf,%lf", &x0,&y0);    
   printf("\nTriangle Vertex B (enter x,y): "); scanfsReturnValueAggregatedOverAllScanfs += scanf("%lf,%lf", &x1,&y1);    
   printf("\nTriangle Vertex C (enter x,y): "); scanfsReturnValueAggregatedOverAllScanfs += scanf("%lf,%lf", &x2,&y2);    
   printf("\nTest Point (enter x,y): "); scanfsReturnValueAggregatedOverAllScanfs += scanf("%lf,%lf", &px,&py);
   // print error

   if( scanfsReturnValueAggregatedOverAllScanfs != 8 ) {    
      printf("You're stup** and didn't put in the right inputs!\n");    
      return 1;    
   }

   // print answer

   printf("\nThe point is ");

   if (tritest(x0,y0,x1,y1,x2,y2,px,py)) {    
      printf("INSIDE");    
   } else {    
      printf("OUTSIDE");    
   }

   printf(" the Triangle\n");

   // return 0

   return 0;    
}

Upvotes: 1

Views: 1924

Answers (2)

Algorithmist
Algorithmist

Reputation: 6695

int test2( double px, double py, double m, double b ) {

if (py < m * px + b ) {
    return -1; 
}else if ( py == m * px + b ){
    return 0;  //Should be return 1 as point is on line.Thus inside the triangle
} else {
    return 1; //should be return 0 as point is outside this line
}
}

I think there is problem in return values that you are returning in above method.These conditions would be different for lines with different slopes.These checks are valid only for m>0 and m<1.And your code is running well because of a fluke .Test Your code for lines with different slopes.

Upvotes: 0

Naveen
Naveen

Reputation: 73493

One thing that comes up straight away for me is that you are comparing doubles using ==.This comparison is never accurate and may produce suprising results. It is better to do something like fabs(d1-d2) < 1e-3 to compare the doubles for equality.

Upvotes: 3

Related Questions