// point_in_poly.java count number of edge crossing horizontal line from test
// even, c==0, is inside
//                        pvpoly uses vertical line from test

public class point_in_poly
{
  int pnpoly(int nvert, double vertx[], double verty[],
             double testx, double testy)
  {
    int j, c = 0;
    for(int i=0; i<nvert; i++)
    {
      j = i-1;
      if(j<0) j=nvert-1;
      if(((verty[i]>testy) != (verty[j]>testy)) &&
          (testx < (vertx[j]-vertx[i]) * 
          (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
        c = 1-c;
    }
    return c;
  } // end pnpoly

  int pvpoly(int nvert, double vertx[], double verty[],
             double testx, double testy)
  {
    int j, c = 0;
    for(int i=0; i<nvert; i++)
    {
      j = i-1;
      if(j<0) j=nvert-1;
      if(((vertx[i]>testx) != (vertx[j]>testx)) &&
          (testy < (verty[j]-verty[i]) * 
          (testx-vertx[i]) / (vertx[j]-vertx[i]) + verty[i]) )
        c = 1-c;
    }
    return c;
  }

  point_in_poly()
  {
    double testx = 3.0;
    double testy = 2.0;
    double vertx[] = {1.0, 3.0, 4.0, 2.0, 2.0}; // no repeat last vert
    double verty[] = {3.0, 4.0, 2.0, 1.0, 2.0};
    int c;
    char symb[] = {' ', '*'};
    char plot[][] = new char[50][60];
    double stestx = 0.0;
    double stesty = 0.0;
    double starx[] = { 0.00000,  1.12257,  4.75528,  1.81636,  2.93893,
                      -0.00000, -2.93893, -1.81636, -4.75528, -1.12257};
    double stary[] = { 5.00000,  1.54508,  1.54508, -0.59017, -4.04508,
	              -1.90983, -4.04508, -0.59017,  1.54508,  1.54508};

    System.out.println("point_in_poly running");
    c = pnpoly(5, vertx, verty, testx, testy);
    System.out.println("pnpoly c="+c);
    for(int iy=0; iy<25; iy++)
      for(int ix=0; ix<25; ix++)
        plot[iy][ix] = symb[pnpoly(5, vertx, verty,
                                   0.2*(double)ix, 0.2*(double)iy)];
    for(int iy=24; iy>=0; iy--)
    {
      for(int ix=0; ix<25; ix++) System.out.print(plot[iy][ix]);
      System.out.println(" ");
    }

    c = pvpoly(5, vertx, verty, testx, testy);
    System.out.println("pvpoly c="+c);
    System.out.println(" ");
    for(int iy=0; iy<25; iy++)
      for(int ix=0; ix<25; ix++)
        plot[iy][ix] = symb[pvpoly(5, vertx, verty,
                                   0.2*(double)ix, 0.2*(double)iy)];
    for(int iy=24; iy>=0; iy--)
    {
      for(int ix=0; ix<25; ix++) System.out.print(plot[iy][ix]);
      System.out.println(" ");
    }

    c = pnpoly(10, starx, stary, stestx, stesty);
    System.out.println(" ");
    System.out.println("pnpoly star c="+c);
    for(int iy=0; iy<50; iy++)
      for(int ix=0; ix<60; ix++)
        plot[iy][ix] = symb[pvpoly(10, starx, stary,
			    (-5.0+0.2*(double)ix), (-4.0+0.2*(double)iy))];
    for(int iy=49; iy>=0; iy--)
    {
      for(int ix=0; ix<60; ix++) System.out.print(plot[iy][ix]);
      System.out.println(" ");
    }

  } // end point_in_poly

  public static void main (String[] args)
  {
    new point_in_poly();
  }
}