/* "boxify", is a simple filter for cleaning up quite general CIF
             and make it readable for "WOL"
   Copyright (C) 1990 Tor Sverre Lande
   Author's address: bassen@ifi.uio.no

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation (any version).

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; see the file COPYING.  If not, write to
the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */


#include <stdio.h>

#include <math.h>

#include "poly.h"

#include "trapes.h"


struct edge_head *new_head()
{
	struct edge_head *h;
	h=(struct edge_head *)malloc(sizeof(struct edge_head));
	h->first=NULL; h->last=NULL;
	return(h);
}

struct edge *new_edge()
{
	struct edge *e;
	e=(struct edge *)malloc(sizeof(struct edge));
	e->id=0; e->wind=0;
	e->next=NULL; e->mate=NULL;
	return(e);
}

#ifdef EDEBUG

displayedges(eh)
struct edge_head *eh;
{
	struct edge *e;
	e=eh->first;
	if (e==NULL)
		fprintf(stderr,"Empty list\n");
	else
	{
		while (e!=NULL)
		{
			fprintf(stderr,"Edge: %f,%f %f,%f x:%f\n",e->xl,e->yl,e->xh,e->yh,e->xx);
			fprintf(stderr,"Id: %d wind: %d\n",e->id,e->wind);
			e=e->next;
		}
	}
}

#endif

makeedges(eh)
struct edge_head *eh;
/**************************************************************\
* 							       *
*  Reads polygons from pl using global variable unread and  *
*  assumes unread always contains the next polygonhead.	       *
*  Transforms a polygon into a sorted list on y of edges.      *
*  Edges parallell to the x-axsis are dropped.		       *
*  ID and windingnumber are updated.			       *
*  Updates eh. returns value of read-statement		       *
* 							       *
\**************************************************************/

{				/* start of makeedges */
	extern struct polygon *unread;
	extern FILE *pfile;
	extern long id;
	extern int currentmin;
	struct polygon x1,x2,f;
	struct polygon *pl;
	struct edge *e,*q;
	int i,er;
	
#ifdef EDEBUG
fprintf(stderr,"makeedges: id:%d, #%d, min:%d\n",id,unread->a,unread->b);
#endif
     if (unread!=NULL)
     {
	id++;
	if ((-unread->a)<3)
		fprintf(stderr,"***Too few points in polygon < 3\n");
	else
	{			/* at least 3 points */
	    pl = unread+1;
	    x1 = *pl; pl++;
	    f.a=x1.a; f.b=x1.b;
	      for (i=1;i<=-(unread->a);i++)
	      {			/* for-loop */
		if (i==-(unread->a))
		{		/* first and last point */
		    x2.a=f.a; x2.b=f.b;
		} else
		{
		    x2 = *pl; pl++;
		}
#ifdef EDEBUG
fprintf(stderr,"insert %d,%d %d,%d\n",x1.a,x1.b,x2.a,x2.b);
#endif
	    
		if (x1.b!=x2.b)/* should it be dropped? */
		{
		    e=new_edge();
		    e->wind= x1.b<x2.b?1:-1;
		    e->id=id;
		    if (x1.b<x2.b)
		    {
			e->xl=x1.a; e->yl=x1.b;
			e->xh=x2.a; e->yh=x2.b;
		    } else
		    {
		       	e->xl=x2.a; e->yl=x2.b;
			e->xh=x1.a; e->yh=x1.b;
		    }
		    /* put into list */
		    if (eh->first==NULL)
		    {		/* first element */
		        eh->first=e;
			eh->last=e;
		    } else
		    { 		/* at least one element */
		    	q=eh->first;
			if (e->yl<=q->yl)
			{	/* put in first */
			    e->next=q;
			    eh->first=e;
			} else
			{	/* not first element */
			    while ((q->next!=NULL) && (q->next->yl<e->yl))
			    	q=q->next;
			    if (q->next==NULL)
			    {	/* last element */
				q->next=e;
				eh->last=e;
				e->next=NULL;
			    } else
			    {	/* in the middle */
				e->next=q->next;
				q->next=e;
			    }
			}
		    }
		}
		x1.a=x2.a; x1.b=x2.b;
	    }
	};
	return(0);
     } else 
     {
     	fprintf(stderr,"unread==NULL\n");
     	return(-1);
     }
}				/* end of makeedges */


mergeedges(e1,e2)
struct edge_head *e1,*e2;

/***********************************************************\
* 							    *
*  Merges two sorted lists (e1,e2) of edges into one (e1).  *
*  							    *
* 							    *
\***********************************************************/

{
	struct edge *a,*b,*n;
	
#ifdef EDEBUG
fprintf(stderr,"mergeedges\n");
#endif
	a=e1->first; b=e2->first;
	if (a == NULL) {
	    e1->first = b;
	    b = b->next;
	}
	/* put in elements first */
	if ((b!=NULL) && (b->yl<a->yl))
	{
#ifdef EDEBUG
fprintf(stderr,"inserting first\n");
#endif
		n=b->next;
		b->next=e1->first;
		e1->first=b;
		b=n;
	}
	a=e1->first;
	/* a.yl<=b.yl */
	while (b!=NULL)
	{
		n=b->next;
		while ((a->next!=NULL) && (a->next->yl<b->yl))
			a=a->next;
		if (e1->last==a)
		{
			e1->last=b;
			a->next=b;
			b->next=NULL;
		} else
		{
			b->next=a->next;
			a->next=b;
		}
		b=n;
	}
	e2->first=NULL; e2->last=NULL;
#ifdef EDEBUG
fprintf(stderr,"end mergeedges\n");
#endif
}

updateactive(ah,eh,alt)
struct edge_head *ah,*eh; 	/* ah - active, eh - edges */
double alt;
/*********************************************************\
* 							  *
*  Updates the active-list sorted on x by fetching edges  *
*  from the edge-list sorted on y.			  *
* 							  *
\*********************************************************/
{
	struct edge *a,*b;
	int i;
	
#ifdef EDEBUG
fprintf(stderr,"updateactive alt: %f ",alt );
#endif
	/* compute new crossing */
	a=ah->first;
	while (a!=NULL)
	{
		a->xx=(fabs(alt-a->yl)<LAMBDA)?a->xl:
		((a->xh-a->xl)*(alt-a->yl))/(a->yh-a->yl)+a->xl;
		a=a->next;
	}
	/* resorting not nessesary because edges are splitted in crossings */
	while ((eh->first!=NULL) && ((eh->first->yl<=alt) || (fabs(eh->first->yl-alt)<LAMBDA)))
	{
		a=eh->first;
		/* remove from eh */
		eh->first=eh->first->next;
		if (eh->first==NULL)
		{	/* empty list */
			eh->last=NULL;
		}
		
		/* compute x-value of crosspoint */
		a->xx=(fabs(a->yl-alt)<LAMBDA)?a->xl:
		((a->xh-a->xl)*(alt-a->yl))/(a->yh-a->yl)+a->xl;
		/* add to list sorted on xx */
		if (ah->first==NULL)
		{
#ifdef EDEBUG
fprintf(stderr,"first element in active\n");
#endif
			/* first element */
			ah->first=a; ah->last=a;
			a->next=NULL;
		} else
		{	/* at least one element */
		    b=ah->first;
#ifdef EDEBUG
if (a->xx == b->xx)
{
fprintf(stderr,"a->xh: %f b->xing:%f\n",a->xh,((b->xh-b->xl)*(a->yh-b->yl))/(b->yh-b->yl)+b->xl);
}
#endif

		    if ((a->xx < b->xx) || 
		        ((fabs(a->xx - b->xx)<LAMBDA) && 
			(a->xh<( ((b->xh-b->xl)*(a->yh-b->yl))/(b->yh-b->yl)
			+b->xl))))
		    {	/* insert first in list */
#ifdef EDEBUG
fprintf(stderr,"first el. in nonempty list\n");
#endif
			a->next=b;
			ah->first=a;
		    } else
		    {
			while ((b->next!=NULL) && (b->next->xx < a->xx))
			b=b->next;
#ifdef EDEBUG
/*if (a->xx == b->xx)
{
fprintf(stderr,"b->next->xh: %f a->xing:%f\n",b->next->xh,((a->xh-a->xl)*(b->next->yh-a->yl))/(a->yh-a->yl)+a->xl);
}*/
#endif

			while ((b->next!=NULL) && 
			       (b->next->xh<
			        ( ((a->xh-a->xl)*(b->next->yh-a->yl))/
				  (a->yh-a->yl)+a->xl)) && 
			       (fabs(b->next->xx-a->xx)<LAMBDA))
			{
#ifdef EDEBUG
fprintf(stderr,"b->next->xh: %f a->xing:%f\n",b->next->xh,((a->xh-a->xl)*(b->next->yh-a->yl))/(a->yh-a->yl)+a->xl);
#endif			
			b=b->next;
			}
			if (b->next==NULL)
			{/* last element */
#ifdef EDEBUG
fprintf(stderr,"lastelement i active\n");
#endif
				b->next=a; ah->last=a; a->next=NULL;
			} else
			{/* after b */
#ifdef EDEBUG
fprintf(stderr,"in the middle\n");
#endif
				a->next=b->next;
				b->next=a;
			}
		    }
		}
	}
#ifdef EDEBUG
fprintf(stderr,"end updateactive\n");
#endif
return(0);
}