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;
    }

    /** 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] );
        }
    }

}