/***************************************************************************
 *                                                                         *
 *   INPOLY.CXX                                                              *
 *                                                                         *
 *   Copyright (c) 1995-1996 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.           *
 *                                                                         *
 *   http://www.visibone.com/inpoly/inpoly.c                               *
 *                                                                         *
 *                                       6/19/95 - Bob Stein & Craig Yap   *
 *                                       stein@visibone.com                *
 *                                       craig@cse.fau.edu                 *
 *                                                                         *
 ***************************************************************************/

#define INPOLY_DLL


#include <QLinkedList>
#include <QVector2D>
#include "inpoly.h"

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

     if (npoints < 3) {
          return(0);
     }
     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);
}

int                                /*   1=inside, 0=outside                */
inpolyf(                           /* is target point inside a 2D polygon? */
float *poly,                   /*   polygon points, [2*n]=x, [2*n + 1]=y       */
int npoints,                       /*   number of points in polygon        */
float xt,                          /*   x (horizontal) of target point     */
float yt)                          /*   y (vertical) of target point       */
{
     float xnew,ynew;
     float xold,yold;
     float x1,y1;
     float x2,y2;
     int i;
     int inside=0;

     if (npoints < 3) {
          return(0);
     }
     xold=poly[2*npoints-2];
     yold=poly[2*npoints-1];
     for (i=0 ; i < npoints ; i++) {
          xnew=poly[2*i];
          ynew=poly[2*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 */
           && (yt-y1)*(x2-x1)
            < (y2-y1)*(xt-x1)) {
               inside=!inside;
          }
          xold=xnew;
          yold=ynew;
     }
     return(inside);
}



int                                /*   1=inside, 0=outside                */
inpolyp(                           /* is target point inside a 2D polygon? */
const QLinkedList<QVector2D> *poly,                   /*   polygon points, [0]=x, [1]=y       */
float xt,                          /*   x (horizontal) of target point     */
float yt)                          /*   y (vertical) of target point       */
{
	 QLinkedList<QVector2D>::const_iterator it;
     float xnew,ynew;
     float xold,yold;
     float x1,y1;
     float x2,y2;
     int inside=0;

     if (poly->count() < 3) {
          return(0);
     }
     xold=poly->last().x();//poly[npoints-1][0];
     yold=poly->last().y();//poly[npoints-1][1];
	
	 for (it = poly->begin(); it != poly->end(); it++) {
          xnew=it->x();//poly[i][0];
          ynew=it->y();//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 */
           && (yt-y1)*(x2-x1)
            < (y2-y1)*(xt-x1)) {
               inside=!inside;
          }
          xold=xnew;
          yold=ynew;
     }
     return(inside);
}


