| Wand |

    package ij.gui;

    import java.awt.*;
    import ij.*;
    import ij.process.*;

    /** This class implements ImageJ's wand (tracing) tool. */
    public class Wand {
        static final int UP=0, DOWN=1, UP_OR_DOWN=2, LEFT=3, RIGHT=4, LEFT_OR_RIGHT=5, NA=6;

        /** The number of points in the generated outline. */
        public int npoints;
        private int maxPoints = 1000; // will be increased if necessary
        /** The x-coordinates of the points in the outline. */
        public int[] xpoints = new int[maxPoints];
        /** The y-coordinates of the points in the outline. */
        public int[] ypoints = new int[maxPoints];

        private ImageProcessor ip;
        private byte[] bpixels;
        private int[] cpixels;
        private short[] spixels;
        private float[] fpixels;
        private int width, height;
        private float lowerThreshold, upperThreshold;

        /** Constructs a Wand object from an ImageProcessor. */
        public Wand(ImageProcessor ip) {
            if (ip instanceof ByteProcessor)
                bpixels = (byte[])ip.getPixels();
            else if (ip instanceof ColorProcessor)
                cpixels = (int[])ip.getPixels();
            else if (ip instanceof ShortProcessor)
                spixels = (short[])ip.getPixels();
            else if (ip instanceof FloatProcessor)
                fpixels = (float[])ip.getPixels();
            width = ip.getWidth();
            height = ip.getHeight();
        }

        private float getColorPixel(int x, int y) {
            if (x>=0 && x<width && y>=0 && y<height)
                return cpixels[y*width + x];
            else
                return Float.MAX_VALUE;
        }

        private float getBytePixel(int x, int y) {
            if (x>=0 && x<width && y>=0 && y<height)
                return bpixels[y*width + x] & 0xff;
            else
                return Float.MAX_VALUE;
        }

        private float getShortPixel(int x, int y) {
            if (x>=0 && x<width && y>=0 && y<height)
                return spixels[y*width + x] & 0xffff;
            else
                return Float.MAX_VALUE;
        }

        private float getFloatPixel(int x, int y) {
            if (x>=0 && x<width && y>=0 && y<height)
                return fpixels[y*width + x];
            else
                return Float.MAX_VALUE;
        }

        private float getPixel(int x, int y) {
            if (bpixels!=null)
                return getBytePixel(x,y);
            else if (spixels!=null)
                return getShortPixel(x,y);
            else if (fpixels!=null)
                return getFloatPixel(x,y);
            else
                return getColorPixel(x,y);
        }

        private boolean inside(int x, int y) {
            float value;
            if (bpixels!=null)
                value = getBytePixel(x,y);
            else if (spixels!=null)
                value = getShortPixel(x,y);
            else if (fpixels!=null)
                value = getFloatPixel(x,y);
            else
                value = getColorPixel(x,y);
            return value>=lowerThreshold && value<=upperThreshold;
        }

        /* Are we tracing a one pixel wide line? */
        boolean isLine(int xs, int ys) {
            int r = 5;
            int xmin=xs;
            int xmax=xs+2*r;
            if (xmax>=width) xmax=width-1;
            int ymin=ys-r;
            if (ymin<0) ymin=0;
            int ymax=ys+r;
            if (ymax>=height) ymax=height-1;
            int area = 0;
            int insideCount = 0;
            for (int x=xmin; (x<=xmax); x++)
                for (int y=ymin; y<=ymax; y++) {
                    area++;
                    if (inside(x,y))
                        insideCount++;
                }
            if (IJ.debugMode)
                IJ.log((((double)insideCount)/area>=0.75?"line ":"blob ")+insideCount+" "+area+" "+IJ.d2s(((double)insideCount)/area));
            return ((double)insideCount)/area>=0.75;
        }

        /** Traces the boundary of an area of uniform color, where
            'startX' and 'startY' are somewhere inside the area. The
            boundary points are stored in the public xpoints and ypoints
            fields. A 16 entry lookup table is used to determine the
            direction at each step of the tracing process. Note that
            the four argument version [autoOutline(x, y, lower, upper)]
            works more reliably. */
        public void autoOutline(int startX, int startY) {
            int x = startX;
            int y = startY;
            int direction;
            lowerThreshold = upperThreshold = getPixel(startX, startY);
            do {x++;} while (inside(x,y));
            if (isLine(x, y)) {
                lowerThreshold = upperThreshold = getPixel(x, y);
                direction = UP;
            } else {
                if (!inside(x-1,y-1))
                    direction = RIGHT;
                else if (inside(x,y-1))
                    direction = LEFT;
                else
                    direction = DOWN;
            }
            traceEdge(x, y, direction);
        }

        /** Traces an object defined by lower and upper threshold values. The
            boundary points are stored in the public xpoints and ypoints fields.
            This verson works more reliably than autoOutline(x, y). */
        public void autoOutline(int startX, int startY, double lower, double upper) {
            //IJ.log(startX+"  "+startY+"  "+lower+"  "+upper);
            npoints = 0;
            int x = startX;
            int y = startY;
            int direction;
            lowerThreshold = (float)lower;
            upperThreshold = (float)upper;
            if (inside(x,y)) {
                do {x++;} while (inside(x,y));
                if (!inside(x-1,y-1))
                    direction = RIGHT;
                else if (inside(x,y-1))
                    direction = LEFT;
                else
                    direction = DOWN;
            } else {
                do {x++;} while (!inside(x,y) && x<width);
                    direction = UP;
                if (x>=width) return;
            }
            traceEdge(x, y, direction);
        }

        /** This is a variation of autoOutline that uses int threshold arguments. */
        public void autoOutline(int startX, int startY, int lower, int upper) {
            autoOutline(startX, startY, (double)lower, (double)upper);
        }

        void traceEdge(int xstart, int ystart, int startingDirection) {
            int[] table = {
                            // 1234, 1=upper left pixel,  2=upper right, 3=lower left, 4=lower right
                NA,         // 0000, should never happen
                RIGHT,      // 000X,
                DOWN,       // 00X0
                RIGHT,      // 00XX
                UP,         // 0X00
                UP,         // 0X0X
                UP_OR_DOWN, // 0XX0 Go up or down depending on current direction
                UP,         // 0XXX
                LEFT,       // X000
                LEFT_OR_RIGHT, // X00X  Go left or right depending on current direction
                DOWN,       // X0X0
                RIGHT,      // X0XX
                LEFT,       // XX00
                LEFT,       // XX0X
                DOWN,       // XXX0
                NA,         // XXXX Should never happen
                };
            int index;
            int newDirection;
            int x = xstart;
            int y = ystart;
            int direction = startingDirection;

            boolean UL = inside(x-1, y-1);  // upper left
            boolean UR = inside(x, y-1);    // upper right
            boolean LL = inside(x-1, y);    // lower left
            boolean LR = inside(x, y);      // lower right
            //xpoints[0] = x;
            //ypoints[0] = y;
            int count = 0;
        //IJ.write("");
        //IJ.write(count + " " + x + " " + y + " " + direction + " " + insideValue);
            do {
                index = 0;
                if (LR) index |= 1;
                if (LL) index |= 2;
                if (UR) index |= 4;
                if (UL) index |= 8;
                newDirection = table[index];
                if (newDirection==UP_OR_DOWN) {
                    if (direction==RIGHT)
                        newDirection = UP;
                    else
                        newDirection = DOWN;
                }
                if (newDirection==LEFT_OR_RIGHT) {
                    if (direction==UP)
                        newDirection = LEFT;
                    else
                        newDirection = RIGHT;
                }
                if (newDirection!=direction) {
                    xpoints[count] = x;
                    ypoints[count] = y;
                    count++;
                if (count==xpoints.length) {
                    int[] xtemp = new int[maxPoints*2];
                    int[] ytemp = new int[maxPoints*2];
                    System.arraycopy(xpoints, 0, xtemp, 0, maxPoints);
                    System.arraycopy(ypoints, 0, ytemp, 0, maxPoints);
                    xpoints = xtemp;
                    ypoints = ytemp;
                    maxPoints *= 2;
                }
            //if (count<10) IJ.write(count + " " + x + " " + y + " " + newDirection + " " + index);
                }
                switch (newDirection) {
                    case UP:
                        y = y-1;
                        LL = UL;
                        LR = UR;
                        UL = inside(x-1, y-1);
                        UR = inside(x, y-1);
                        break;
                    case DOWN:
                        y = y + 1;
                        UL = LL;
                        UR = LR;
                        LL = inside(x-1, y);
                        LR = inside(x, y);
                        break;
                    case LEFT:
                        x = x-1;
                        UR = UL;
                        LR = LL;
                        UL = inside(x-1, y-1);
                        LL = inside(x-1, y);
                        break;
                    case RIGHT:
                        x = x + 1;
                        UL = UR;
                        LL = LR;
                        UR = inside(x, y-1);
                        LR = inside(x, y);
                        break;
                }
                direction = newDirection;
            } while ((x!=xstart || y!=ystart || direction!=startingDirection));
            npoints = count;
        }

    }

| Wand |