@gene i didn't understand the boolean thing in your algo,
Say triangle is ABC, say Point is p
Algo goes like this,
for side AB
1. calculate cross product of(p-A)*(B-A)[ Which is nothing but the side
function in gene algo] See the sign.
2. calculate the cross product of (C-A)*(B-A) . See the sign if it is not
same then say the point lies outside.
3. If the signs are same repeat the step1 from other sides.
The funda here is if a point is inside a triangle then cross product of the
point joining any vertex to the side containing that vertex, should point in
the same side (up or below), with reference to cross product of this vertex
to any reference point(C for AB because they are in the same plane) with the
side (AB) should also point in the same direction, When this process is
repeated for all sides then we can say that the point is inside the
triangle.
On Tue, Sep 21, 2010 at 6:09 AM, Gene <gene.ress...@gmail.com> wrote:
> 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<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
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.
