|
FloodFiller |
|
package ij.process; import ij.*; import ij.gui.Toolbar; import java.awt.Rectangle; /** This class, which does flood filling, is used by the floodFill() macro function and by the particle analyzer The Wikipedia at "http://en.wikipedia.org/wiki/Flood_fill" has a good description of the algorithm used here as well as examples in C and Java. */ public class FloodFiller { int maxStackSize = 500; // will be increased as needed int[] stack = new int[maxStackSize]; int stackSize; ImageProcessor ip; int max; boolean isFloat; public FloodFiller(ImageProcessor ip) { this.ip = ip; isFloat = ip instanceof FloatProcessor; } public boolean fill(int x, int y) { int width = ip.getWidth(); int height = ip.getHeight(); int color = ip.getPixel(x, y); ip.drawLine(x, y, x, y); int newColor = ip.getPixel(x, y); ip.putPixel(x, y, color); if (color==newColor) return false; stackSize = 0; push(x, y); while(true) { int coordinates = pop(); if (coordinates ==-1) return true; x = coordinates&0xffff; y = coordinates>>16; int x1 = x; int x2 = x; while (ip.getPixel(x1,y)==color && x1>=0) x1--; // find start of scan-line x1++; while (ip.getPixel(x2,y)==color && x2<width) x2++; // find end of scan-line x2--; ip.drawLine(x1,y, x2,y); // fill scan-line boolean inScanLine = false; for (int i=x1; i<=x2; i++) { // find scan-lines above this one if (!inScanLine && y>0 && ip.getPixel(i,y-1)==color) {push(i, y-1); inScanLine = true;} else if (inScanLine && y>0 && ip.getPixel(i,y-1)!=color) inScanLine = false; } inScanLine = false; for (int i=x1; i<=x2; i++) { // find scan-lines below this one if (!inScanLine && y<height-1 && ip.getPixel(i,y+1)==color) {push(i, y+1); inScanLine = true;} else if (inScanLine && y<height-1 && ip.getPixel(i,y+1)!=color) inScanLine = false; } } } int count=0; /** This method is used by the particle analyzer to remove interior holes from particle masks. */ public void particleAnalyzerFill(int x, int y, double level1, double level2, ImageProcessor mask, Rectangle bounds) { //if (count>100) return; int width = ip.getWidth(); int height = ip.getHeight(); mask.setColor(0); mask.fill(); mask.setColor(255); stackSize = 0; push(x, y); while(true) { int coordinates = pop(); if (coordinates ==-1) return; x = coordinates&0xffff; y = coordinates>>16; int x1 = x; int x2 = x; while (inParticle(x1,y,level1,level2) && x1>=0) x1--; // find start of scan-line x1++; while (inParticle(x2,y,level1,level2) && x2<width) x2++; // find end of scan-line x2--; mask.drawLine(x1-bounds.x,y-bounds.y, x2-bounds.x,y-bounds.y); // fill scan-line i mask ip.drawLine(x1,y, x2,y); // fill scan-line in image boolean inScanLine = false; if (x1>0) x1--; if (x2<width-1) x2++; for (int i=x1; i<=x2; i++) { // find scan-lines above this one if (!inScanLine && y>0 && inParticle(i,y-1,level1,level2)) {push(i, y-1); inScanLine = true;} else if (inScanLine && y>0 && !inParticle(i,y-1,level1,level2)) inScanLine = false; } inScanLine = false; for (int i=x1; i<=x2; i++) { // find scan-lines below this one if (!inScanLine && y<height-1 && inParticle(i,y+1,level1,level2)) {push(i, y+1); inScanLine = true;} else if (inScanLine && y<height-1 && !inParticle(i,y+1,level1,level2)) inScanLine = false; } } } final boolean inParticle(int x, int y, double level1, double level2) { if (isFloat) return ip.getPixelValue(x,y)>=level1 && ip.getPixelValue(x,y)<=level2; else return ip.getPixel(x,y)>=level1 && ip.getPixel(x,y)<=level2; } final void push(int x, int y) { //IJ.log("push: "+x+" "+y); //if (count++>100) return; stackSize++; if (stackSize==maxStackSize) { int[] newStack = new int[maxStackSize*2]; System.arraycopy(stack, 0, newStack, 0, maxStackSize); stack = newStack; maxStackSize *= 2; } //if (stackSize>max) max = stackSize; stack[stackSize-1] = x + (y<<16); } final int pop() { //IJ.log("pop "); if (stackSize==0) return -1; else { int value = stack[stackSize-1]; stackSize--; return value; } } }
|
FloodFiller |
|