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

[Top] [Up] [Next] [Previous]