/* @(#)ag_fill.c	17.1.1.1 (ES0-DMD) 01/25/02 17:33:30 */
/*===========================================================================
  Copyright (C) 1995 European Southern Observatory (ESO)
 
  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; either version 2 of 
  the License, or (at your option) any later 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; if not, write to the Free 
  Software Foundation, Inc., 675 Massachusetss Ave, Cambridge, 
  MA 02139, USA.
 
  Corresponding concerning ESO-MIDAS should be addressed as follows:
	Internet e-mail: midas@eso.org
	Postal address: European Southern Observatory
			Data Management Division 
			Karl-Schwarzschild-Strasse 2
			D 85748 Garching bei Muenchen 
			GERMANY
===========================================================================*/

/* @(#)ag_fill.c	17.1.1.1  (OAA-ASTRONET) 01/25/02 17:33:30   */
/*
 * HEADER : ag_fill.c      - Vers 3.6.001  - Sep 1993 -  L. Fini, OAA
 *                         - Vers 3.6.000  - Nov 1991 -  L. Fini, OAA
 */

#include <aglenvr.h>

#define MAXCROSS 50

#define LN2I 1.442695022                /* 1/ln(e) */
#define TINY 1e-5


static void sort(vec,dim)		/* sort a vector of float values   */
float vec[];				/* array of vectors to sort */
int dim;				/* dimension of vector */
{
float temp;
int i,j,m,n;				/* counters */
int lognb2;				/* (int)(log_2(dim)) */

if(dim <= 0) 
	return;

lognb2 = log((double)dim)*LN2I + TINY;     /* ~ log_2(dim) */
m = dim;

for(n = 0;n < lognb2;n++) {
	m /= 2;
	for(j = m;j < dim;j++) {
		i = j - m;
		temp = vec[j];
		while(i >= 0 && temp < vec[i]) {
			vec[i + m] = vec[i];
			i -= m;
		}
		vec[i + m] = temp;
	}
}
}

static int cross(yy,a,b,npoint,thexcross,theycross,maxcross)
float yy;
float *a, *b;
int npoint;
float thexcross[],theycross[];
int maxcross;
{
int i,i1,j;

for(i = j = 0;i < npoint;i++) {
	i1 = (i + 1)%npoint; 			/* wrap start onto end */
	if((b[i1] - yy) == 0.0) {
		int i2 = (i1+1)%npoint;
		if((b[i2]-b[i1])*(b[i1]-b[i]) > 0) /* deal with non convex  */
			i++;
		continue;
	}
	if((b[i] - yy)*(b[i1] - yy) <= 0) { 	/* this is a crossing */
		theycross[j]=yy;
		if((yy - b[i]) == 0.0)
			thexcross[j++] = a[i];
		else 
			thexcross[j++]=a[i]+(a[i1]-a[i])/(b[i1]-b[i])*(yy-b[i]);
			if(j >= maxcross)
				break;
	}
}

sort(thexcross,j);
return j;
}

static void minmax(v,n,min,max)
float *v;
int n;
double *min, *max;
{
*max = *v;
*min = *v++;

while(--n>0) {
	register double val = *v++;

	if(val>*max)
		*max=val;
	else if(val<*min)
		*min=val;
}
}
	

/*****************************************************************************/
/*++                         AG_FILL (User callable)                         */

/* AG_FILL    Polygon filling routine                                        */


/* This module will draw a pattern of lines within a polygon of specified    */
/* vertexes. The contour of the polygon itself is not drawn and if desired   */
/* It may be drawn explicitly by a call to AG_GPLG.                          */

/* The coordinate values are referred to the current graphic mode (either    */
/* NORMALIZED, USER or SPECIAL) and mapped accordingly.  Graphic mode is     */
/* affected by: AG_WDEF, AG_TRNS, and AG_SSET items "NORMAL","USER" and      */
/* "SPECIAL". Anyway the "SPECIAL" coordinate mode will NOT produce a proper */
/* drawing because the routine assumes that the sides of the polygon are     */
/* straight lines.                                                           */
				   

void AG_FILL(x,y,n,space,angle,sset)

float x[],y[];            /* Coordinate arrays                               */
int   n;                  /*                                                 */
double space;             /* Spacing between filling lines. Lines of pattern */
                          /* will be spaced "spacing" times the basic char   */
	                  /* width. if Spacing = 0.0, the spacing will be    */
	                  /* set so that the polygon is filled completely.   */
                          /* Note: filling with double line width will       */
                          /* usually prodice best results. Also note that    */
                          /* this feature may be pretty slow.                */
double angle;             /* Angle of filling lines with respect to X-axis   */
char *sset;               /* A command string which will be used in a call to*/
                          /* AG_SSET prior of drawing. It may be used to     */
                          /* set various items such as line width and style, */
                          /* colours and so on. This argument is placed here */
                          /* for convenience in that it has exactly the same */
                          /* effect as calling AG_SSET(sset) before calling  */
                          /* AG_FILL. See AG_SSET for specifications.        */
                                                                         /*--*/
{
static char *modnam="FILL";
float *XV, *YV;
double min,max;
float crossx[MAXCROSS], crossy[MAXCROSS];
double yy;
float ndy;
int ncross,i;

AG_DMSG(modnam,(char *)0);

XV = (float *)calloc((size_t)n,sizeof(float));
YV = (float *)calloc((size_t)n,sizeof(float));

if((XV==NULL)||(YV==NULL)) {
	AG_GERR(350,"Memory allocation");
	if(XV!=NULL)
		free((void *)XV);
	if(YV!=NULL)
		free((void *)YV);
	return;
}

AGL_push(modnam);

AG_RGET("angf",crossx);

angle *= crossx[0];		/* Convert angle into radians              */


if(space<=0.0) {
	float rslt[2];
	AG_RGET("resol",rslt);
	ndy=rslt[1]*0.5;
} else {
	AG_TGET("X",crossx,crossy);	/* Use crossx,crossy as spares     */
	ndy = space*crossy[1];
}


for(i=0;i<n;i++) 			/* We work in normalized space     */
	AG_VU2N(x[i],y[i],XV+i,YV+i);	/* because we want a line spacing  */
					/* computed with respect to device */

AG_TSET(0.0,0.0,(-angle),3);
AG_TROT(XV,YV,n);

AG_TSET(0.0,0.0,angle,2);

AG_SSET(sset);

minmax(YV,n,&min,&max);

min += ndy;

for(yy=min;yy<max;yy += ndy) {
	ncross=cross(yy,XV,YV,n,crossx,crossy,MAXCROSS);
	AG_TROT(crossx,crossy,ncross);
	if(ncross>1) {
		for(i=0;i<ncross;i++) 		/* Convert back to user    */
			AG_VN2U(crossx[i],	/* coordinates because we  */
			        crossy[i],	/* want the right clipping */
			        crossx+i,	/* mode to apply.          */
			        crossy+i);

		for(i=0;i<ncross;i +=2) 
			AG_GPLL(crossx+i,crossy+i,2);
	}
}
AGL_pop();
}