/* Following structures describe map for GA route finding problem. Map is 20x20,
origin (0,0) is at bottom left corner.
start point = (2,18)
end point = (17,5)
Simplified situation used; all illegal zones bounded by 4 sided polygons.

Illegal zones are held  in the array `map'  of poly4 structures. The  function
ncrosses(double,double,double double)  takes the  x and  y coordinates  of the  end
points of a line segment (x1,y1) and (x2,y2). It returns the number of illegal
zones the line segment crosses or partially crosses. This map is a fairly easy
one, you can try designing  a more challenging one for  the GA to find  routes
through.

NB NB NB:
before any of these functions can be used, poly4toline4() MUST BE CALLED ONCE
TO INITIALISE THE MAP FORMAT
-- this translates  map from a  simple format suitable  for use with  graphics
routines (the array map) to a format more suited to the functions for  testing
for zone crosses (the array lmap)

NB2: ncrosses()  as it  stands returns  the  number of  times a  line  segment
completely crosses an illegal zone or crosses into or out of an illegal  zone,
it does not pick up the situation where a line segment is completely contained
within an illegal zone --- i.e. a path would be penalised for crossing  into a
zone but not for staying in it. See if you can work out how to modify the code
to make  it  sensitive  to this  information.  CLUE:  it only  needs  a  small
modification; whether or not a line  completely crosses a zone depends on  the
number of sides of the zone polygon it crosses.
*/
/********************************************************************************/
/* YOU WILL NEED TO INCORPORATE THE FOLLOWING INTO YOUR CODE. THIS CAN BE
ACHIEVED BY COPYING THE FUNCTIONS AND STRUCTURE DEFINITIONS INTO YOUR PROGRAM
FILE, OR BY LINKING THIS MODULE INTO YOUR PROGRAM*/

#include <stdlib.h>
#include <stdio.h>

#define MSIZE 7   /* number of forbidden zones in map */
#define NSIDES 4  /* num sides to illegal zone polygons */
#define NCOORDS 2*NSIDES   /* 2*num points in polygons describing forbidden zones*/

struct Vector{
	double i;    /* i and j components of a 2D vector */
	double j;};

/* line segment described by vectors of each end point */

struct lineSeg{
	struct Vector r1;
	struct Vector r2;
};

/* simple structure to hold coords of points on the polygon in a 1D array
x1,y1,x2,y2 ...etc         */

struct poly4{
	double points[NCOORDS];
};

/* this structure holds  same info, but  in terms of an  array of pointers  to
lineSegs. Can translate from poly4 to line4 by using poly4toline4() */

struct line4{
	struct lineSeg *ln[NSIDES];
};

/* map in coord form */

struct poly4 map[MSIZE] = {{5,19,10,19,10,15,5,15}
						  ,{0,13,3,13,3,10,0,10}
						  ,{7,13,11,13,11,4,7,4}
						  ,{4,7,6,4,5,0,2,4}
						  ,{13,15,17,18,15,9,13,11}
						  ,{12,7,15,7,15,1,12,1}
						  ,{17,7,18,10,19,5,16,6}};



/* global array to hold map in lineSeg form for use with crosses functions */

static struct line4 lmap[MSIZE];

/* function prototype forward declarations */

int crosses(struct lineSeg *l1, struct lineSeg *l2);
struct lineSeg *coords2lineSeg(double x1,double y1,double x2, double y2);
int ncrosses(double x1, double y1, double x2, double y2g);
void poly4toline4(void);
int between(double, double , double);
#endif

/********************************************************************************************************/

/***************************************************/
/* this function should  be run (once) before  using ncrosses(). Converts  map
into a format more suitable for cross checking via vector equations */

void poly4toline4(void)
{
int i,j,j2;

	for(i=0;i<MSIZE;i++)
	{
		for(j=0;j<NSIDES-1;j++){
			j2=2*j;
			lmap[i].ln[j]=coords2lineSeg(map[i].points[j2],map[i].points[j2+1],map[i].points[j2+2],map[i].points[j2+3]);
		}
		lmap[i].ln[NSIDES-1]=coords2lineSeg(map[i].points[NCOORDS-2],map[i].points[NCOORDS-1],
		 map[i].points[0],map[i].points[1]);  /* last pnt to first point */
	}

}

/***********************************************************************************/

/* returns number of illegal zones crossed, or partially crossed, by the  line
segment whose end point coords are x1,y1 and x2,y2 */

int ncrosses(double x1,double y1,double x2,double y2)
{
	lineSeg *l1=NULL;
	int i,j,count=0;
	l1=coords2lineSeg(x1,y1,x2,y2);
	for(i=0;i<MSIZE;i++){
		for(j=0;j<NSIDES;j++){
			if(crosses(l1,lmap[i].ln[j])){
				count++;
					  /*printf("hit %d ",i); */   /* only need to know about one line
				      crossed to know zone crossed or partially
				      crossed, could modify to get more info.*/
				break;
			}
		}
	}
	delete l1;
	return count;
}

/*********************************************************************************/
/* takes coords  of ends of  a line segment,  returns a pointer  to a  lineSeg
ure */

lineSeg *coords2lineSeg(double x1,double y1,double x2,double y2)
{
	 lineSeg *p=NULL;
	/* set up memory, fill it, return pointer to it */

	p= new  lineSeg;

	p->r1.i=x1;
	p->r1.j=y1;
	p->r2.i=x2;
	p->r2.j=y2;

	return(p);

}

/***************************************************************************************/
/* check to  see if  2 line  segs cross, returns  1 if  do, 0  if don't.  Line
segment end points described by vectors r1  and r2, hence pnt on line  segment
described by parametric equation p =  r1 + A(r2-r1); 0<=A<=1. Equate two  such
descriptions to see if segments cross */

int crosses( lineSeg *l1,  lineSeg *l2)
{
double A,B,k,x1diff,y1diff,x2diff,y2diff;

	x1diff = (l1->r2.i - l1->r1.i);
	y1diff = (l1->r2.j - l1->r1.j);
	x2diff = (l2->r2.i - l2->r1.i); /* x2diff and y2diff cannot be zero at
same time*/
	y2diff = (l2->r2.j - l2->r1.j);


/*  boundary cases   ****************************************************/

	if((x1diff ==0 && x2diff==0 && l1->r1.i != l2->r1.i )
|| (y1diff==0 && y2diff==0 && l1->r1.j != l2->r1.j))
		return 0;  /*parallel */

	if(x1diff ==0 && x2diff==0 && l1->r1.i == l2->r1.i)
	 {if((between(l1->r1.j,l2->r1.j,l2->r2.j) ||
	       between(l1->r2.j,l2->r1.j,l2->r2.j)))
	     return 1; /*parallel but touching */
	  else return 0;
	 }


	if(y1diff==0 && y2diff==0 && l1->r1.j == l2->r1.j)
	{if((between(l1->r1.i,l2->r1.i,l2->r2.i) ||
	       between(l1->r2.i,l2->r1.i,l2->r2.i)))
		{return 1;} /*parallel but touching*/
	 else return 0;
	}


	if(x1diff==0 && y1diff==0)  /* actually a point */
	{A=(l1->r1.i - l2->r1.i)/x2diff;
		if(0<=A && A<=1 && A== ((l1->r1.j - l2->r1.j)/y2diff))
			{return 1;}
		else return 0;
	}


	if(x1diff==0)
	{ B=(l1->r1.i - l2->r1.i)/x2diff;
		if(0<=B && B<=1)
		{A=(l2->r1.j + B*(y2diff) - l1->r1.j)/y1diff;
		   if(0<=A && A<=1)
		   {
		    return 1;
		  }
		   else return 0;
		}
	       else return 0;
	}
	if(x2diff==0)
	{A=(l2->r1.i - l1->r1.i)/x1diff;
		if(0<=A && A<=1)
		{B=(l1->r1.j + (A*y1diff) - l2->r1.j)/y2diff;
			if(0.0 <= B && B <= 1.0)
			{
			  return 1;
			}
			else return 0;
		}
		else return 0;
	}
	if(y1diff==0)
	{B=(l1->r1.j - l2->r1.j)/y2diff;
		if(0<=B && B<=1)
		{A=(l2->r1.i + B*x2diff - l1->r1.i)/x1diff;
			if(0<=A && A<=1)
			{
			  return 1;
			}
			else return 0;
		}
		else return 0;
	}
	if(y2diff==0)
	{A=(l2->r1.j - l1->r1.j)/y1diff;
		if(0<=A && A<=1)
		{B=(l1->r1.i + A*x1diff  - l2->r1.i)/x2diff;
			if(0<=B && B<=1)
			{
			 return 1;
			}
			else return 0;
		}
		else return 0;
	}



/* standard cases   ********************************************/


/* else see if values between 0 and 1 for A and B for vector eqn.
r1 + A(r2-r1) = R1 + B(R2-R1), wher r1,r2 and R1,R2 are vectors of end pnts of
line segments */
	if(y1diff != 0 && y2diff != 0)
	{k=((x2diff*y1diff/x1diff) - y2diff);
	   if(k==0)  /* parallel, singularity  */
	   {A=(l1->r1.i - l2->r1.i)/x2diff;
		if(0<=A && A<=1 && A== ((l1->r1.j - l2->r1.j)/y2diff))
			{ return 1;} /*2 lines coincident*/
		else
		{A=(l1->r2.i - l2->r1.i)/x2diff;
		if(0<=A && A<=1 && A== ((l1->r2.j - l2->r1.j)/y2diff))
			{ return 1;} /*2 lines coincident*/

		else return 0; /* parallel */
		}
	}


	   else
	    {B=((l2->r1.j) + ((l1->r1.i)*y1diff/x1diff) - (l1->r1.j + ((l2->r1.i)*y1diff/x1diff)))/k;
		if(0<=B && B<=1)
		{A = ((l2->r1.i/x1diff) + B*(x2diff/x1diff)-((l1->r1.i)/x1diff));
			if(0<=A && A<=1)
			  {  return 1;}
			else return 0;
		}
		else return 0;
	   }
	}

	return 0;
}

/****************************************************************************************/

int between(double x, double y1, double y2)
{
int ans=0;

	if(y1>y2)
	{if(y2 <= x && x <= y1)
		ans=1;
	}
	else
	{if(y1<=x && x <= y2)
		ans=1;
	}
	return ans;
}