Appendix III
[Top] [Up] [Next] [Previous]

# Appendix III

ANSI C Code for testing if a point lies within a polygon. This may be freely used provided the original copyright message is retained in full.

```/*
** Reproduced with thanks from mapper 1.2
** 7/26/93 Kevin Hughes, kevinh@pulua.hcc.hawaii.edu
** polygon code copyright 1992 by Eric Haines, erich@eye.com
*/

#include <stdio.h>

#define MAXLINE 500
#define MAXVERTS 100
#define X 0
#define Y 1

int pointinpoly(double point[2], double pgon[MAXVERTS][2])
{
int i, numverts, inside_flag, xflag0;
int crossings;
double *p, *stop;
double tx, ty, y;

for (i = 0; pgon[i][X] != -1 && i < MAXVERTS; i++)
;
numverts = i;
crossings = 0;

tx = point[X];
ty = point[Y];
y = pgon[numverts - 1][Y];

p = (double *) pgon + 1;
if ((y >= ty) != (*p >= ty))
{
if ((xflag0 = (pgon[numverts - 1][X] >= tx)) ==
(*(double *) pgon >= tx))
{
if (xflag0)
crossings++;
}
else
{
crossings += (pgon[numverts - 1][X] - (y - ty) *
(*(double *) pgon - pgon[numverts - 1][X]) /
(*p - y)) >= tx;
}
}

stop = pgon[numverts];

for (y = *p, p += 2; p < stop; y = *p, p += 2)
{
if (y >= ty)
{
while ((p < stop) && (*p >= ty))
p += 2;
if (p >= stop)
break;
if ((xflag0 = (*(p - 3) >= tx)) == (*(p - 1) >= tx))
{
if (xflag0)
crossings++;
}
else
{
crossings += (*(p - 3) - (*(p - 2) - ty) *
(*(p - 1) - *(p - 3)) / (*p - *(p - 2))) >= tx;
}
}
else
{
while ((p < stop) && (*p < ty))
p += 2;
if (p >= stop)
break;
if ((xflag0 = (*(p - 3) >= tx)) == (*(p - 1) >= tx))
{
if (xflag0)
crossings++;
}
else
{
crossings += (*(p - 3) - (*(p - 2) - ty) *
(*(p - 1) - *(p - 3)) / (*p - *(p - 2))) >= tx;
}
}
}
inside_flag = crossings & 0x01;
return (inside_flag);
}
```

HTML+ Discussion Document - November 8, 1993