package ij.process;
import ij.*;
import ij.gui.*;
import java.awt.Rectangle;


/** This class fills polygons using the scan-line filling algorithm 
	described at "http://www.cs.rit.edu/~icss571/filling/". */
public class PolygonFiller {
	int BLACK=0xff000000, WHITE=0xffffffff;
	int edges; // number of edges
	int activeEdges; // number of  active edges

	// the polygon
	int[] x; // x coordinates
	int[] y; // y coordinates
	int n;  // number of coordinates

	// edge table
	double[] ex;	// x coordinates
	int[] ey1;	// upper y coordinates
	int[] ey2;	// lower y coordinates
	double[] eslope;   // inverse slopes (1/m)

	// sorted edge table (indexes into edge table) (currently not used)
	int[] sedge;

	// active edge table (indexes into edge table)
	int[] aedge; 

	/** Constructs a PolygonFiller. */
	public PolygonFiller() {
	 }

	/** Constructs a PolygonFiller using the specified polygon. */
	public PolygonFiller(int[] x, int[] y, int n) {
		setPolygon(x, y, n);
	 }

	/** Specifies the polygon to be filled. */
	public void setPolygon(int[] x, int[] y, int n) {
		this.x = x;
		this.y = y;
		this.n = n;
	}

	 void allocateArrays(int n) {
		if (ex==null || n>ex.length) {
			ex = new double[n];
			ey1 = new int[n];
			ey2 = new int[n];
			sedge = new int[n];
			aedge = new int[n];
			eslope = new double[n];
		}
	}

	/** Generates the edge table. */
	void buildEdgeTable(int[] x, int[] y, int n) {
		int length, iplus1, x1, x2, y1, y2;
		edges = 0;
		for (int i=0; i<n; i++) {
			iplus1 = i==n-1?0:i+1;
			y1 = y[i];	y2 = y[iplus1];
			x1 = x[i];	x2 = x[iplus1];
			if (y1==y2)
				continue; //ignore horizontal lines
			if (y1>y2) { // swap ends
				int tmp = y1;
				y1=y2; y2=tmp;
				tmp=x1;
				x1=x2; x2=tmp;
			}
			double slope = (double)(x2-x1)/(y2-y1);
			ex[edges] = x1 + slope/2.0; 
			ey1[edges] = y1;
			ey2[edges] = y2;
			eslope[edges] = slope;
			edges++;   
		}
		for (int i=0; i<edges; i++)
			sedge[i] = i;
		activeEdges = 0;
		//quickSort(sedge);
	}


	/** Currently not used since searching the entire edge table
		does not seem to take a significant amount of time. */
	void addToSortedTable(int edge) {
		int index = 0;
		while (index<edges && ey1[edges]>ey1[sedge[index]]) {
			index++;
		}
		for (int i=edges-1; i>=index; i--) {
			sedge[i+1] = sedge[i];
			//IJ.log((i+1)+"="+i);
		}
		sedge[index] = edges;
	}

	/** Fills the polygon using the ImageProcessor's current drawing color. */
	public void fill(ImageProcessor ip, Rectangle r) {
		ip.fill(getMask(r.width, r.height));
	}

	/** Returns a byte mask containing a filled version of the polygon. */
	public ImageProcessor getMask(int width, int height) {
		allocateArrays(n);
		buildEdgeTable(x, y, n);
		//printEdges();
		int x1, x2, offset, index;
		ImageProcessor mask = new ByteProcessor(width, height);
		byte[] pixels = (byte[])mask.getPixels();
		for (int y=0; y<height; y++) {
			removeInactiveEdges(y);
			activateEdges(y);
			offset = y*width;
			for (int i=0; i<activeEdges; i+=2) {
				x1 = (int)(ex[aedge[i]]+0.5);
				if (x1<0) x1=0;
				if (x1>width) x1 = width;
				x2 = (int)(ex[aedge[i+1]]+0.5); 
				if (x2<0) x2=0; 
				if (x2>width) x2 = width;
				//IJ.log(y+" "+x1+"  "+x2);
				for (int x=x1; x<x2; x++)
					pixels[offset+x] = -1; // 255 (white)
			}			
			updateXCoordinates();
		}
		return mask;
	}	

	/** Updates the x coordinates in the active edges list and sorts the list if necessary. */
	void updateXCoordinates() {
		int index;
		double x1=-Double.MAX_VALUE, x2;
		boolean sorted = true;
		for (int i=0; i<activeEdges; i++) {
			index = aedge[i];
			x2 = ex[index] + eslope[index];
			ex[index] = x2;
			if (x2<x1) sorted = false;
			x1 = x2;
		}
		if (!sorted) 
			sortActiveEdges();
	}

	/** Sorts the active edges list by x coordinate using a selection sort. */
	void sortActiveEdges() {
		int min, tmp;
		for (int i=0; i<activeEdges; i++) {
			min = i;
			for (int j=i; j<activeEdges; j++)
				if (ex[aedge[j]] <ex[aedge[min]]) min = j;
			tmp=aedge[min];
			aedge[min] = aedge[i]; 
			aedge[i]=tmp;
		}
	}

	/** Removes edges from the active edge table that are no longer needed. */
	void removeInactiveEdges(int y) {
		int i = 0;
		while (i<activeEdges) {
			int index = aedge[i];
			if (y<ey1[index] || y>=ey2[index]) {
				for (int j=i; j<activeEdges-1; j++)
					aedge[j] = aedge[j+1];
				activeEdges--; 
			} else
				i++;		 
		}
	}

	/** Adds edges to the active edge table. */
	void activateEdges(int y) {
		for (int i=0; i<edges; i++) {
			int edge =sedge[i];
			if (y==ey1[edge]) {
				int index = 0;
				while (index<activeEdges && ex[edge]>ex[aedge[index]])
					index++;
				for (int j=activeEdges-1; j>=index; j--) 
					aedge[j+1] = aedge[j];
				aedge[index] = edge;
				activeEdges++;
			}
		}
	}

	/** Display the contents of the edge table*/
	void printEdges() {
		for (int i=0; i<edges; i++) {
			int index = sedge[i];
			IJ.log(i+"	"+ex[index]+"  "+ey1[index]+"  "+ey2[index] + "  " + IJ.d2s(eslope[index],2) );
		}
	}

	/** Display the contents of the active edge table*/
	void printActiveEdges() {
		for (int i=0; i<activeEdges; i++) {
			int index =aedge[i];
			IJ.log(i+"	"+ex[index]+"  "+ey1[index]+"  "+ey2[index] );
		}
	}

	/*
	void quickSort(int[] a) {
		quickSort(a, 0, a.length-1);
	}
	
	void quickSort(int[] a, int from, int to) {
		int i=from, j=to;
		int center = a[(from+to)/2];
		do {
			//while ( i < to && center.compareTo(a[i]) > 0 ) i++;
			while (i<to && ey1[center]>ey1[a[i]]) j--;
			//while ( j > from && center.compareTo(a[j]) < 0 ) j--;
			while (j>from && ey1[center]<ey1[a[j]]) j--;
			if (i < j) {int temp = a[i]; a[i] = a[j]; a[j] = temp;}
			if (i <= j) { i++; j--; }
		} while(i <= j);
		if (from < j) quickSort(a, from, j);
		if (i < to) quickSort(a,  i, to);
	}
	*/

}