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; iy2) { // 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; iwidth) 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=ey2[index]) {
				for (int j=i; jex[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