• Create Account

\$10

Like
0Likes
Dislike

# Point in a poly II

By Cornelis Wessels | Published Jul 16 1999 11:58 AM in Math and Physics

p->x edu usenet p->y vector2d return(true index ncros
 If you find this article contains errors or problems rendering it unreadable (missing images or files, mangled code, improper text formatting, etc) please contact the editor so corrections can be made. Thank you for helping us improve this resource

From pdxgate!usenet.ee.pdx.edu!reed!henson!news.u.washington.edu!usenet.coe.montana.edu!caen!uunet!mcsun!sun4nl!bsoatr!bskewe!kewe Tue Mar 2 15:21:37 PST 1993

In article douglasg@gr.hp.com writes:

>
> I'm looking for an algorithm which determines if a point
> falls within an arbitrary (convex or concave) polygon.
>
> Thanks,
>
> Douglas Gennetten
> Hewlett-Packard
>
>
>

BOOLEAN PointInsideOfPolygon ( POLYGOON *P, VECTOR2D *p )
{
VECTOR2D o, v, w;
INDEX    ncross, N, n;

ncros             = 0;
N                 = PolygonLength(P);   /* Number of vertices */
GivePolygonVertex ( P, N, &o );

for ( n=1; n<=N; n++ )
{
GivePolygonVertex ( P, n, &v );

if ( o.x >= p->x && v.x <  p->x ||
o.x <  p->x && v.x >= p->x  )
{
w.x = p->x;
LinearInterpolation ( &o, &v, &w );

if ( w.x == p->x && w.y == p->y )
return(TRUE);
else if ( w.y > p->y )
ncross++;
}

CopyVector2d ( &v, &o );
}

if ( ncross%2 == 0 )
return(FALSE);
else
return(TRUE);
}

Cornelis Wessels
kewe@bskewe.atr.bso.nl

Krommenoord 14
3079 ZT ROTTERDAM
The Netherlands
+31 - 10 - 4826394