next up previous contents index Search
Next: 0.8.4 Knapsack Problem Up: 0.8.3 Determining Whether a Previous: 0.8.3 Determining Whether a

0.8.3.1 Source Code


#include <iostream.h>
#include <math.h>
#include <stdlib.h>

//
//  Input parameters:
//     npol               : number of vertices
//     xp[npol], yp[npol] : x,y coord of vertices
//     x,y                : coord of point to test 
//
//  Return Value:
//     0 : test point is outside polygon
//     1 : test point is inside polygon
//
//  Notes:
//     if test point is on the border, 0 or 1 is returned.
//     If there exists an adiacent polygon, the point is
//     _in_ only in one of the two.
//

int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
    int i, j, c = 0;
    for (i = 0, j = npol-1; i < npol; j = i++) 
    {

        if (
             (
               ((yp[i]<=y) && (y<yp[j])) || 
               ((yp[j]<=y) && (y<yp[i]))
             ) &&
             (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
	  
          c = !c;
    }
    return c;
}

Scott Gasch
1999-07-09