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 <[email protected]> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
