This is okay, but does more math than necessary. Here's another approach: // Return 0 if p is left of a->b, 2 if right of a->b, and 1 if on a- >b. int side(PT *p, PT *a, PT *b) { float d = (p.x-a.x) * (b.y-a.y) - (p.y-a.y) * (b.x-a.x); return d < 0 ? 0 : d > 0 ? 2 : 1; }
// This table treats points on the edges as inside. Just redo the // table to count them as outside. bool inside_polygon(PT *p, PT *a, PT *b, PT *c) { bool p[3][3][3] = {{ // <0, ... // <0 =0 >0 { true, true, false }, // <0, ... { true, true, false }, // =0 { false, false, false }}, // >0 {{ // =0, { true, true, false }, // <0 { true, true, true }, // =0 { false, true, true }}, // >0 {{ // >0, { false, false, false }, // <0 { false, true, true }, // =0 { false, true, true }}}; // >0 return p[side(p, a, b)][side(p, b, c)][side(p, c, a)]; } This relies on the facts 1) if a, b, c if abc are given in CCW order, then all three side values are 0 iff the point is inside; and 2) if they are given in CW order, then the side values are 2 iff the point is inside; 3) the values can't be 000 if the vertices are in CCW order (except for the point at infinity, which doesn't exist in a computer); and 4) the values can't be 222 if the vertices are given in CW order (again except for the point at infinity). On Sep 20, 4:20 pm, Naveen Agrawal <nav.coo...@gmail.com> wrote: > Take intersection point of triangle as a,b,c > > And the testing point as p > > boolean SameSide(p,s,t ,u) > if s && p lies on same side //to check same side form equation > using t and u and then evaluate the value of point > return true //p&s,if both gives same > sign(+ve or -ve) value then they are on same side > else > return false > void PointInTriangle(p, a,b,c) > if (SameSide(p,a, b,c) && SameSide(p,b, a,c) && SameSide(p,c, a,b)) > Inside the triange > else > outside triangle -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.