/***************************************************************************
 *                                                                         *
 *   INPOLY.C                                                              *
 *                                                                         *
 *   Copyright (c) 1995-1997 Galacticomm, Inc.  Freeware source code.      *
 *                                                                         *
 *   Please feel free to use this source code for any purpose, commercial  *
 *   or otherwise, as long as you don't restrict anyone else's use of      *
 *   this source code.  Please give credit where credit is due.            *
 *                                                                         *
 *   Point-in-polygon algorithm, created especially for World-Wide Web     *
 *   servers to process image maps with mouse-clickable regions.           *
 *                                                                         *
 *   Home for this file:  http://www.gcomm.com/develop/inpoly.c            *
 *                                                                         *
 *                                       6/19/95 - Bob Stein & Craig Yap   *
 *                                       stein@gcomm.com                   *
 *                                       craig@cse.fau.edu                 *
 *                                                                         *
 ***************************************************************************/

#include "gcomm.h"

#define FILREV "$Revision: 5 $"

GBOOL                              /*   TRUE=inside, FALSE=outside         */
inpoly(                            /* is target point inside a 2D polygon? */
UINT poly[][2],                    /*   polygon points, [0]=x, [1]=y       */
INT npoints,                       /*   number of points in polygon        */
UINT xt,                           /*   x (horizontal) of target point     */
UINT yt)                           /*   y (vertical) of target point       */
{
     UINT xnew,ynew;
     UINT xold,yold;
     UINT x1,y1;
     UINT x2,y2;
     INT i;
     GBOOL inside=FALSE;

     if (npoints < 3) {
          return(FALSE);
     }
     xold=poly[npoints-1][0];
     yold=poly[npoints-1][1];
     for (i=0 ; i < npoints ; i++) {
          xnew=poly[i][0];
          ynew=poly[i][1];
          if (xnew > xold) {
               x1=xold;
               x2=xnew;
               y1=yold;
               y2=ynew;
          }
          else {
               x1=xnew;
               x2=xold;
               y1=ynew;
               y2=yold;
          }
          if ((xnew < xt) == (xt <= xold)         /* edge "open" at left end */
           && ((long)yt-(long)y1)*(long)(x2-x1)
            < ((long)y2-(long)y1)*(long)(xt-x1)) {
               inside=!inside;
          }
          xold=xnew;
          yold=ynew;
     }
     return(inside);
}

