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

    Note that by ImageJ convention, outline and pixel coordinates are shifted by 0.5:
    Pixel (0,0) is enclosed by the rectangle between (0,0) and (1,1); thus all 0.5
    is added to all polygon coordinates when comparing to pixel coordinates.

    After applying this offset, rounding is done such that points
    exactly on the left boundary are considered outside, points
    exactly on the right boundary inside.
    Points exactly on a horizontal boundary are considered ouside for
    the boundary with lower y and inside for the boundary with the higher y.
    (actually, the boundary is slightly shifted to the left (in x) to ensure
    correct rounding in spite of the final numeric accuracy)
*/
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 of polygon vertices (null when using float values)
    int[] y;                // y coordinates
    float[] xf, yf;         // floating-point coordinates, may be given instead of integer 'x'
    float xOffset, yOffset; // offset that has to be added to xf, yf
    int n;                  // number of coordinates (polygon vertices)

    // 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 with integer coordinates. */
    public PolygonFiller(int[] x, int[] y, int n) {
        setPolygon(x, y, n);
    }

    /** Constructs a PolygonFiller using the specified polygon with floating-point coordinates. */
    public PolygonFiller(float[] xf, float[] yf, int n, float xOffset, float yOffset) {
        setPolygon(xf, yf, n, xOffset, yOffset);
    }

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

    /** Specifies the polygon to be filled in case of float coordinates.
     *  In this case, multiple polygons separated by one set of NaN coordinates each.
     */
    public void setPolygon(float[] xf, float[] yf, int n, float xOffset, float yOffset) {
        x = y = null;
        this.xf = xf;
        this.yf = yf;
        this.n = n;
        this.xOffset = xOffset;
        this.yOffset = yOffset;
    }

     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 for all non-horizontal lines:
     *  ey1, ey2: min & max y value
     *  eslope: inverse slope dx/dy
     *  ex: x value at ey1, corrected for half-pixel shift between outline&pixel coordinates
     *  sedge: list of sorted edges is prepared (not sorted yet) */
    void buildEdgeTable() {
        edges = 0;
        int polyStart = 0;    //index where the polygon has started (i.e., 0 unless we have multiple ploygons separated by NaN)
        for (int i=0; i<n; i++) {
            int iplus1 = i==n-1 ? polyStart : i+1;
            if (x != null) {  //using int arrays
                int y1 = y[i];  int y2 = y[iplus1];
                int x1 = x[i];  int x2 = x[iplus1];
                if (y1==y2)
                    continue; //ignore horizontal lines
                if (y1>y2) {  //swap ends to ensure y1<y2
                    int tmp = y1;
                    y1 = y2;  y2 = tmp;
                    tmp = x1;
                    x1 = x2;  x2 = tmp;
                }
                double slope = (double)(x2 - x1)/(y2 - y1);
                ex[edges] = x1 + 0.5*slope + 1e-8;  // x at the y1 pixel coordinate
                ey1[edges] = y1;
                ey2[edges] = y2;
                eslope[edges] = slope;
            } else {          //using float arrays
                if (Float.isNaN(xf[iplus1])) //after the last point, close the polygon
                    iplus1 = polyStart;
                if (Float.isNaN(xf[i])) {    //when a new polygon follows, remember the start point for closing it
                    polyStart = i + 1;
                    continue;
                }
                double y1f = yf[i] + yOffset;  double y2f = yf[iplus1] + yOffset;
                double x1f = xf[i] + xOffset;  double x2f = xf[iplus1] + xOffset;
                int y1 = (int)Math.ceil(y1f - 0.5f);
                int y2 = (int)Math.ceil(y2f - 0.5f);
                if (y1==y2 || (y1<=0 && y2<=0))
                    continue; //ignore horizontal lines or lines that don't reach the first row of pixels
                if (y1>y2) {  //swap ends to ensure y1<y2
                    int tmp = y1;
                    y1 = y2;  y2 = tmp;
                    double ftmp = y1f;
                    y1f = y2f;  y2f = ftmp;
                    ftmp = x1f;
                    x1f = x2f;  x2f = ftmp;
                }
                double slope = (x2f - x1f)/(y2f - y1f);
                ex[edges] = x1f + (y1 - y1f + 0.5)*slope + 1e-8; // x at the y1 pixel coordinate
                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();
        //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+" x1edge="+(ex[aedge[i]]+0.5)+" x2edge="+(ex[aedge[i+1]]+0.5)+" slope1="+eslope[aedge[i]]+" slope1="+eslope[aedge[i+1]]+" offs="+xOffset+","+yOffset);
                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] );
        }
    }

}