#include <stdio.h>
#include <math.h>
#include <malloc.h>

typedef struct point {
  double x,y,z;
} POINT;

typedef struct ray {
  POINT p,v;
} RAY;

typedef struct polygon {
  int n;
  POINT *v;
} POLYGON;

RAY *make_ray(int H, int W, int x, int y,
	      double left, double right, double top, double bot,
	      double near, double far);
POINT *ray_poly_intersect(RAY *ray, POLYGON *polygon);

POLYGON *readPolygon(FILE *fp) {
  int i,n;
  POLYGON *poly;

  fscanf (fp,"%d",&n);
  poly = (POLYGON *) malloc(sizeof (POLYGON));
  poly->n = n;
  poly->v = (POINT *) malloc (n * sizeof(POINT));
  for (i=0; i<n; i++) {
    fscanf(fp,"%lf%lf%lf",&(poly->v[i].x),&(poly->v[i].y),&(poly->v[i].z));
  }
  return poly;
}

/*
 * This function implements the Jordan-curve test.
 * It returns 1 if the point is inside the polygon,
 * and 0 if it is outside.
 */
int pointIsInside(POINT *pt, POLYGON *poly) {
  int i, j, c = 0;
  int n = poly->n;
  POINT *v = poly->v;
  double x = pt->x;
  double y = pt->y;

  for (i = 0, j = n-1; i < n; j = i++) {
    /*
     * Flip a bit for each edge that:
     *   straddles the x-axis (going up or going down), and
     *   intersects the x-axis at a positive value of x.
     */
    if ((((v[i].y <= y) && (y < v[j].y)) ||
	 ((v[j].y <= y) && (y < v[i].y))) &&
	(x < (v[j].x - v[i].x) * (y - v[i].y) / (v[j].y - v[i].y) + v[i].x))

      c = !c;
  }
  return c;
}

main (int argc, char *argv[]) {
  RAY *ray;
  POLYGON *poly;
  POINT *hitpoint;
  FILE *fp;
  int i,x,y;
  int H,W;
  double left,right,top,bot,near,far;

  if ((argc-2) % 3 != 0) {
    fprintf(stderr,"Usage:\n\
intersect [camera-file] [x1 y1 poly-file1] [x2 y2 poly-file2] ...\n");
    exit(1);
  }

  if ((fp=fopen(argv[1],"r")) == NULL) {
    fprintf(stderr,"Can't read camera file: %s\n",argv[1]);
    exit(1);
  }
  fscanf(fp,"%d%d",&W,&H);
  fscanf(fp,"%lf%lf%lf%lf%lf%lf",
	 &left,&right,&top,&bot,&near,&far);
  fclose(fp);

  for (i=2; i<argc; i += 3) {
    x = atoi(argv[i]);
    y = atoi(argv[i+1]);
    if ((fp=fopen(argv[i+2],"r")) == NULL) {
      fprintf(stderr,"Can't read polygon file: %s\n",argv[i+2]);
    }
    else {
      poly = readPolygon(fp);
      fclose(fp);
      ray = make_ray(H,W,x,y,left,right,top,bot,near,far);

      hitpoint = ray_poly_intersect(ray,poly);
      if (hitpoint == NULL)
	printf("no hit\n");
      else
	printf("hit at at (%8.3lf %8.3lf %8.3lf)\n",
	       hitpoint->x,hitpoint->y,hitpoint->z);
    }
  }
}

/**************************************************************
 * The code that you must change starts HERE.
 */

RAY *make_ray(int H, int W, int x, int y,
	      double left, double right, double top, double bot,
	      double near, double far) {
  RAY *ray = (RAY *)malloc(sizeof(RAY));

 /*
  * These are arbitrary values.
  *  You'll have to set all of them correctly yourself.
  */ 

  ray->p.x = 0.0;
  ray->p.y = 0.0;
  ray->p.z = 0.0;

  ray->v.x = 0.0;
  ray->v.y = 0.0;
  ray->v.z = 1.0;

  return ray;
}

/*
 * This is also incorrect.  You have to change it to return
 * NULL if there is no intersection, and to return a new hit point if
 * there IS an intersection.
 */
POINT *ray_poly_intersect(RAY *ray, POLYGON *polygon) {
  return NULL;
}