/* "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"

double findnext(ah,eh,alt,resa,resb,Xoffset,Yoffset)
struct edge_head *ah,*eh;	/* ah - active, eh - edges */
double alt;			/* current altitude */
int resa,resb;
long Xoffset,Yoffset;
/******************************************************************\
* 								   *
*       find next altitude by min of				   *
*  1) smallest yh in active					   *
*  2) edges->first->yl						   *
*  3) unread							   *
*  4) lowest instesection in which case listes have to be updated  *
* 								   *
\******************************************************************/

{
	extern struct polygon *unread;
	extern struct edge *new_edge();
	extern gentrapes();
	double my,iy,ix,t1,t2;
	struct edge *e,*f,*p,*t;
	int newy,err;
	struct edge_head ne;
	
#ifdef FDEBUG
fprintf(stderr,"findnext\n");
#endif
    if (ah->first != NULL)
    {
	/* min yh in active */
	e=ah->first;
	my=e->yh; e=e->next;
	for (e=ah->first;e!=NULL;e=e->next)
		my = (e->yh < my) ? e->yh :my;
#ifdef FDEBUG
fprintf(stderr,"my: %f\n",my);
#endif
		
	if (eh->first!=NULL)
	{
#ifdef FDEBUG
fprintf(stderr,"first element in edges? %f - %f\n",my,eh->first->yl);
#endif
		/* edges->first->yl? */
		my=(eh->first->yl < my) ? eh->first->yl : my;
	}
	/* Check against unread */
	if (unread!=NULL)
		my=(unread->b < my) ? unread->b : my;
	/* check for intersection */
#ifdef FDEBUG
fprintf(stderr,"my: %f\n",my);
#endif
	newy=TRUE;
	while (newy) {
	    newy=FALSE;
	    p=ah->first;
	    for (e=ah->first; (e!=NULL); e=e->next)  {
		if ((f=e->next)!=NULL)	{
			/* compute x-value for my */
			ix=((e->xh-e->xl)/(e->yh-e->yl))*(my-e->yl)+e->xl;
			iy=((f->xh-f->xl)/(f->yh-f->yl))*(my-f->yl)+f->xl;
			if ( (ix > iy) && (fabs(ix-iy)>LAMBDA))
			{	/* out of sort */
#ifdef FDEBUG
fprintf(stderr,"out of sort\n");
fprintf(stderr,"1:%f x:%f\n",e->xx,ix);
fprintf(stderr,"2:%f x:%f\n",f->xx,iy);
displayedges(ah);
#endif
				if (((e->yh-e->yl)*(f->xh-f->xl)
				    -(f->yh-f->yl)*(e->xh-e->xl))==0)
				{
				fprintf(stderr,"***Impossible to cross parallell lines!?!\n");
				} else
				{
				ix=((e->xh-e->xl)*
				    (f->xh*f->yl-f->yh*f->xl)-
				    (f->xh-f->xl)*
				    (e->xh*e->yl-e->yh*e->xl))
				   /(((e->yh-e->yl)*(f->xh-f->xl))
				    -((f->yh-f->yl)*(e->xh-e->xl)));
				}
				if (fabs(e->xh-e->xl)>LAMBDA)
				iy=((e->yh-e->yl)/(e->xh-e->xl))*(ix-e->xl)+e->yl;
				else
				iy=((f->yh-f->yl)/(f->xh-f->xl))*(ix-f->xl)+f->yl;
#ifdef FDEBUG
fprintf(stderr,"ix:%f iy:%f\n",ix,iy);
#endif

				if (my<iy)
				fprintf(stderr,"***intersection:%f > miny:f?!?\n",iy,my);
				if (fabs(iy-alt)<LAMBDA) {
				    /* crossing on old altitude */
				    if ((fabs(e->yl-alt)>LAMBDA) && (e->mate!=NULL)) {
				        /* generate trapezoide */
					if (e->xl < e->mate->xl)
					    gentrapes(e,e->mate,alt,resa,resb,Xoffset,Yoffset);
					else
					    gentrapes(e->mate,e,alt,resa,resb,Xoffset,Yoffset);
					/* update coordinates */
					e->xl=(((e->xh-e->xl)/(e->yh-e->yl))*(alt-e->yl)+e->xl);
					e->yl=alt;
					e->mate->xl=(((e->mate->xh-e->mate->xl)/(e->mate->yh-e->mate->yl))*(alt-e->mate->yl)+e->mate->xl);
					e->mate->yl=alt;
				        e->mate->mate=NULL;
					e->mate=NULL;
				    };
				    if ((fabs(f->yl-alt)>LAMBDA) && (f->mate!=NULL)) {
				        /* generate trapezoide */
					if (f->xl < f->mate->xl)
					    gentrapes(f,f->mate,alt,resa,resb,Xoffset,Yoffset);
					else
					    gentrapes(f->mate,f,alt,resa,resb,Xoffset,Yoffset);
					/* update coordinates */
					f->xl=(((f->xh-f->xl)/(f->yh-f->yl))*(alt-f->yl)+f->xl);
					f->yl=alt;
					f->mate->xl=(((f->mate->xh-f->mate->xl)/(f->mate->yh-f->mate->yl))*(alt-f->mate->yl)+f->mate->xl);
					f->mate->yl=alt;
				        f->mate->mate=NULL;
					f->mate=NULL;
				    };
				    /* Now rearrange list */
				    if (p==e) {
				        /* first in list */
					ah->first=f;
					e->next=f->next;
					f->next=e;
					e=f;
					f=p;
					p=e;
				    } else {
				        /* in list */
					p->next=f;
					e->next=f->next;
					f->next=e;
					if (ah->last==f) ah->last=e;
					t=e;
					e=f;
					f=t;
				    }
				    newy=TRUE;
				} else { /* correct */
				if (fabs(iy-e->yh)>LAMBDA) {
				    /* Generate new edge */
				    ne.first=new_edge();
				    ne.last=ne.first;
				    ne.first->wind=e->wind;
				    ne.first->id=e->id;
				    ne.first->xl=ix;
				    ne.first->xh=e->xh;
				    ne.first->yl=iy;
				    ne.first->yh=e->yh;
				    /* update old edges */
				    e->xh=ix; e->yh=iy;
				    /* merge new edge back to old list */
				    mergeedges(eh,&ne);
				    newy=TRUE;
				    my=iy;/* asserts new altitude */
#ifdef FDEBUG
fprintf(stderr,"after merging:\n");
#endif
				};
				/* else no change! */
				if (fabs(iy-f->yh)>LAMBDA) {
				    /* Generate new edge */
				    ne.first=new_edge();
				    ne.last=ne.first;
				    ne.first->wind=f->wind;
				    ne.first->id=f->id;
				    ne.first->xl=ix;
				    ne.first->xh=f->xh;
				    ne.first->yl=iy;
				    ne.first->yh=f->yh;
				    /* update old edges */
				    f->xh=ix; f->yh=iy;
				    /* merge new edge back to old list */
				    mergeedges(eh,&ne);
				    newy=TRUE;
				    my=iy;/* asserts new altitude */
#ifdef FDEBUG
fprintf(stderr,"after merging:\n");
#endif
				};
				/* else no change! */
				};
				break;/* and try again */
			}
		};
	        p=e; /* p points at pior */
	    }
	}
#ifdef FDEBUG
fprintf(stderr,"end findnext %f\n",my);
#endif
	return(my);
    } else return(eh->first->yl);
}