Toxi's implementation is nice!
I played a bit with his code, dropping the old, synchronized Stack in favor of an ArrayList (would use a Deque but it is Java 1.6 so Mac users would be excluded), avoiding duplicate code (going left and right), perhaps at the cost of slight performance hit (not even sure) but being more readable (IMHO). In short, I rewrote it for fun and profit (ie. learning purposes, understanding how it works...).
Oh, and slightly generalized the implementation to accept any PImage (although I haven't tested this yet).
Here is my version:
ShowFloodFill.pde Code:boolean bWithBorder;
void setup()
{
size(800,800);
image(loadImage("FloodFillTest.png"), 0, 0);
loadPixels();
}
void draw()
{
}
void mouseReleased()
{
if (bWithBorder)
{
FloodFillWithBorder ff = new FloodFillWithBorder();
ff.DoFill(
mouseX, mouseY, // current mouse pos as point object
GetRandomColor(),
GetRandomColor()
);
}
else
{
FloodFill ff = new FloodFill();
ff.DoFill(
mouseX, mouseY, // current mouse pos as point object
GetRandomColor()
);
}
updatePixels();
}
void keyPressed()
{
if (key == 'b')
{
bWithBorder = true;
println("With border");
}
else if (key == 'n')
{
bWithBorder = false;
println("Plain");
}
}
color GetRandomColor()
{
return 0xFF000000 | (int) random(0x1000000); // random color (need to set alpha too)
}
I wrapped the function in a class, a bit wasteful but it was a way to share data between functions without passing lot of parameters...
The implementation itself:
FloodFill.pde Code:public class FloodFill
{
protected int iw; // Image width
protected int ih; // Image height
protected color[] imagePixels;
protected color backColor; // Color found at given position
protected color fillColor; // Color to apply
// Stack is almost deprecated and slow (synchronized).
// I would use Deque but that's Java 1.6, excluding current (mid-2009) Macs...
protected ArrayList stack = new ArrayList();
public FloodFill()
{
iw = width;
ih = height;
imagePixels = pixels; // Assume loadPixels have been done before
}
public FloodFill(PImage imageToProcess)
{
iw = imageToProcess.width;
ih = imageToProcess.height;
imagePixels = imageToProcess.pixels; // Assume loadPixels have been done before if sketch image
}
public void DoFill(int startX, int startY, color fc)
{
fillColor = fc;
backColor = imagePixels[startX + startY * iw];
// don't run if fill color is the same as background one
if (fillColor == backColor)
return;
stack.add(new PVector(startX, startY));
while (stack.size() > 0)
{
PVector p = (PVector) stack.remove(stack.size() - 1);
FillScanLine((int) p.x, (int) p.y, -1);
FillScanLine((int) p.x + 1, (int) p.y, 1);
}
}
protected void FillScanLine(int x, int y, int dir)
{
// compute current index in pixel buffer array
int idx = x + y * iw;
boolean inColorRunAbove = false;
boolean inColorRunBelow = false;
// fill until boundary in current scanline...
// checking neighbouring pixel rows
while (x >= 0 && x < iw && imagePixels[idx] == backColor)
{
imagePixels[idx] = fillColor;
if (y > 0) // Not on top line
{
if (imagePixels[idx - iw] == backColor)
{
if (!inColorRunAbove)
{
// The above pixel needs to be flooded too, we memorize the fact.
// Only once per run of pixels of back color (hence the inColorRunAbove test)
stack.add(new PVector(x, y-1));
inColorRunAbove = true;
}
}
else // End of color run (or none)
{
inColorRunAbove = false;
}
}
if (y < ih - 1) // Not on bottom line
{
if (imagePixels[idx + iw] == backColor)
{
if (!inColorRunBelow)
{
// Idem with pixel below, remember to process there
stack.add(new PVector(x, y + 1));
inColorRunBelow = true;
}
}
else // End of color run (or none)
{
inColorRunBelow = false;
}
}
// Continue in given direction
x += dir;
idx += dir;
}
}
}
The version with border comes in next message (out of space!).