/*
  geometry primitives
*/


#include <math.h>
#include "geometry.h"


/* test for counter-clock wise movement from p0 via p1 to p2 */
/* from: Sedgewick: Algorithms */

int ccw (POINT p0, POINT p1, POINT p2)
{
  int dx1, dx2, dy1, dy2, result;

  dx1 = p1.x - p0.x;    dy1 = p1.y - p0.y;
  dx2 = p2.x - p0.x;    dy2 = p2.y - p0.y;

  if (dx1 * dy2 > dy1 * dx2) result = 1;
  if (dx1 * dy2 < dy1 * dx2) result = -1;
  if (dx1 * dy2 == dy1 * dx2)
    {
      if ((dx1 * dx2 < 0) || (dy1 * dy2 < 0))
	result = -1;
      else
	{
	  if (dx1*dx1 + dy1*dy1 >= dx2*dx2 + dy2*dy2)
	    result = 0;
	  else
	    result = 1;
	} 
    }
  return result;
}


/* test for intersection of two lines */
/* from: Sedgewick: Algorithms */

int intersect (LINE l1, LINE l2)
{
  return ((ccw(l1.p1,l1.p2,l2.p1)*ccw(l1.p1,l1.p2,l2.p2))<=0) && 
	 ((ccw(l2.p1,l2.p2,l1.p1)*ccw(l2.p1,l2.p2,l1.p2))<=0);
}



/* test if point t is contained in polygon p */
/* points in p[1]..p[numpoints], p[0] and p[numpoints+1] must be available */
/* from: Sedgewick: Algorithms */

int ppcontains (POINT t, POINT *p, int numpoints)
{
  int count, i, j;
  LINE lt, lp;
  POINT comp;

  /* first make p[1] the point with lowest x among points with lowest y */

  i = 1; comp = p[1];
  for (j=2; j<=numpoints; j++)  /* search */
    if ((p[j].y < comp.y) || ((p[j].y == comp.y) && (p[j].x < comp.x)))
      {
	i = j;
	comp = p[j];
      }

  while (i > 1)    /* reorganie */
    {
      comp = p[1];
      for (j=1; j<numpoints; j++)
	p[j] = p[j+1];
      p[numpoints] = comp;
      i--;
    }

  count = 0; j = 0;
  p[0] = p[numpoints];
  p[numpoints+1] = p[1];

  lt.p1 = lt.p2 = t;   
  lt.p2.x += 9998;  /* make a very long line */
  lt.p2.y += 9991;

  for (i=1; i<=numpoints; i++)
    {
      lp.p1 = p[i]; lp.p2 = p[i];
      if (!intersect(lp,lt))
	{
	  lp.p2 = p[j]; j = i;
	  if (intersect (lp, lt))
	      count++;
	}
    }

  return count % 2;
}


