PolygonFiller.java

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


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; 

    public PolygonFiller() {
     }

    public PolygonFiller(int[] x, int[] y, int n) {
        setPolygon(x, y, n);
     }

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

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


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

    public void fill(ImageProcessor ip, Rectangle r) {
        ip.fill(getMask(r.width, r.height));
    }

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

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

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

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

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

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

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

}