# Good algorithm for flood fill?

Hey all, Ive got this algorithm for flood fill:

``````function floodFill(x,y,fillColor,interiorColor)
local colour = screen:get(x,y)
if (colour==interiorColor) then
screen:set(x,y,fillColor)
floodFill(x+1,y,fillColor,interiorColor)
floodFill(x-1,y,fillColor,interiorColor)
floodFill(x,y+1,fillColor,interiorColor)
floodFill(x,y-1,fillColor,interiorColor)
end
end
``````

It works in small spaces but due to the huge amount of image:get use a stack overflow occurs, how is this preventable or is there another algorithm I can use that is less memory consuming than this one?

I know there’s one in Spritely, maybe you could check that out?

cant find one on there

Probably not of any use to you, but was fun to do:

``````
function setup()
displayMode(FULLSCREEN)
w,h = WIDTH,HEIGHT
img = image(w,h)
imga = image(w,h)
setContext(img)
noSmooth()
background(255, 255, 255, 255)
local x,y,rw,rh,c
local colours = {
color(255, 0, 0, 255),
color(0, 255, 0, 255),
color(0,0,255,255),
color(0,255,255,255),
color(255,0,255,255),
color(255,255,0,255),
color(0,127,255,255),
color(255,0,127,255),
color(127,255,0,255)
}
for n=1,100 do
x = math.random(1,w)
y = math.random(1,h)
rw = math.random(10,100)
rh = math.random(10,100)
c = math.random(1,9)
fill(colours[c])
rect(x,y,rw,rh)
end
setContext()
m = mesh()
m.texture = img
m.shader.fillFrom = color(0, 0, 0, 0)
m.shader.fillTo = color(115, 123, 50, 255)
end

function draw()
background(0, 0, 0, 255)
noSmooth()
setContext(imga)
background(0, 0, 0, 255)
if pt then
blendMode(ONE,ZERO,ZERO,ONE)
else
blendMode(ONE,ZERO,ONE,ZERO)
end
m:draw()
setContext()
img,imga = imga,img
m.texture = img
spriteMode(CORNER)
sprite(img,(WIDTH-w)/2,(HEIGHT-h)/2)
if pt then
local x = math.floor(pt.x - (WIDTH-w)/2)
local y = math.floor(pt.y - (HEIGHT-h)/2)
local r,g,b,a = img:get(x,y)
img:set(x,y,r,g,b,0)
pt = false
end
end

function touched(t)
if t.state == ENDED then
pt = vec2(t.x,t.y)
end
end

return [[
//
//

//This is the current model * view * projection matrix
// Codea sets it automatically
uniform mat4 modelViewProjection;

//This is the current mesh vertex position, color and tex coord
// Set automatically
attribute vec4 position;
attribute vec4 color;
attribute vec2 texCoord;

//This is an output variable that will be passed to the fragment shader
varying lowp vec4 vColor;
varying highp vec2 vTexCoord;

void main()
{
//Pass the mesh color to the fragment shader
vColor = color;
vTexCoord = texCoord;

//Multiply the vertex position by our combined transform
gl_Position = modelViewProjection * position;
}
]],[[
//
//

//Default precision qualifier
precision highp float;

//This represents the current texture on the mesh
uniform lowp sampler2D texture;
uniform float width;
uniform float height;
float rw = 1./width;
float rh = 1./height;
uniform lowp vec4 fillFrom;
lowp vec4 fillFromA = vec4(fillFrom.xyz,0.);
uniform lowp vec4 fillTo;
//The interpolated vertex color for this fragment
varying lowp vec4 vColor;

//The interpolated texture coordinate for this fragment
varying highp vec2 vTexCoord;

void main()
{
//Sample the texture at the interpolated coordinate
lowp vec4 col = texture2D( texture, vTexCoord );
lowp float a;
if (col == fillFromA) {col = fillTo;} else {
if (col == fillFrom) {
a = texture2D(texture, vTexCoord + vec2(rw,0.)).a;
if (a < .5) {
col.a = 0.;
} else {
a = texture2D(texture, vTexCoord + vec2(-rw,0.)).a;
if (a < .5) {
col.a = 0.;
} else {
a = texture2D(texture, vTexCoord + vec2(0.,rh)).a;
if (a < .5) {
col.a = 0.;
} else {
a = texture2D(texture, vTexCoord + vec2(0.,-rh)).a;
if (a < .5) {
col.a = 0.;
}
}
}
}
}
}
//Set the output color to the texture color
gl_FragColor = col;
}
]]
end
``````

This is a simple and successful approach I used. You can’t run out of memory this way.

You need two tables, A=squares to fill, B=squares already examined

1. Find a starting square x,y, add to A eg table.insert(A,vec2(x,y))
2. Take the first square in A
3. Look at all neighbours. Add to A if they meet the conditions and aren’t in B
4. Fill the square we are in, mark it as examined in table B
5. Delete the first square in table A
6. Repeat from step 2 until A is empty

Well ignatz I tried what you said but I interpreted it atleast 5 different ways, ended up with this:

``````     function setup()
local x,y = 0,0
dir = {vec2(x+1,y),
vec2(x-1,y),
vec2(x,y+1),
vec2(x,y-1),
vec2(x+1,y+1),
vec2(x+1,y-1),
vec2(x-1,y+1),
vec2(x-1,y-1)}
end
if tool == "fill" then
if t.state == BEGAN then
filla = {vec2(t.x,t.y)}
fillpos = vec2(t.x,t.y)
fillx = t.x
filly = t.y
fillcol = col
intcol = screen:get(t.x,t.y)
if fillcol ~= intcol then
filling = true
end
end
end
--algorithm 1
if filling and (1/DeltaTime) > 10 then
for k,v in pairs(filla) do
for i=1,4 do
local dx,dy = dir[i].x,dir[i].y
if screen:get(v.x+dx,v.y+dy) == intcol then
screen:set(v.x+dx,v.y+dy,fillcol)
table.insert(filla,vec2(v.x+dx,v.y+dy))
end
end
if filla[k] then table.remove(filla,k) end
end
oldfilla = #filla
if oldfilla == 0 then
filling = false
end
end
``````

@Luatee - Try this. You can include the diagonal neighbours as well if you wish, just check you don’t fall off the edge of the image. You can make it faster if you check whether the neighbours have already been processed, but this will require another table to keep track of them.

``````function setup()
floodFill(img,1,1,color(255,255,0,255),color(0,0,0,0))
end

function draw()
background(220)
sprite(img,WIDTH/2,HEIGHT/2)
end

function floodFill(img,startX,startY,fillColor,interiorColor)
tbl={}
tbl[1]=vec2(startX,startY)
--just compare r,g,b and not a
local c1=(interiorColor.r*256+interiorColor.g)*256+interiorColor.b
while #tbl>0 do
local x,y=tbl[1].x,tbl[1].y
local r,g,b,a = img:get(x,y)
local c2=(r*256+g)*256+b
if (c1==c2) then
img:set(x,y,fillColor)
if x<img.width then tbl[#tbl+1]=vec2(x+1,y) end
if x>1 then tbl[#tbl+1]=vec2(x-1,y) end
if y>1 then tbl[#tbl+1]=vec2(x,y-1) end
if y<img.height then tbl[#tbl+1]=vec2(x,y+1) end
end
table.remove(tbl,1)  -- remove the item we've just processed
end
end
``````

This version is more efficient, it keeps track of used pixels as I suggested just above

``````function setup()
floodFill(img,1,1,color(255,255,0,255),color(0,0,0,0))
end

function draw()
background(220)
sprite(img,WIDTH/2,HEIGHT/2)
end

function floodFill(img,startX,startY,fillColor,interiorColor)
tbl={}
tbl2={}
tbl[1]=vec2(startX,startY)
local c1=(interiorColor.r*256+interiorColor.g)*256+interiorColor.b
while #tbl>0 do
local x,y=tbl[1].x,tbl[1].y
tbl2[x*3000+y]=1
local r,g,b,a = img:get(x,y)
local c2=(r*256+g)*256+b
if (c1==c2) then
img:set(x,y,fillColor)
if x<img.width and tbl2[(x+1)*3000+y]==nil then tbl[#tbl+1]=vec2(x+1,y) end
if x>1 and tbl2[(x-1)*3000+y]==nil then tbl[#tbl+1]=vec2(x-1,y) end
if y>1 and tbl2[x*3000+y-1]==nil then tbl[#tbl+1]=vec2(x,y-1) end
if y<img.height and tbl2[x*3000+y+1]==nil then tbl[#tbl+1]=vec2(x,y+1) end
end
table.remove(tbl,1)
end
end
``````

Just tried that second one ignatz, works about twice as fast as my original one thanks, im guessing you dont mind if I use it anyway? Im guessing when the code is run in its raw format in xcode and not run in an IDE it will be faster aswell?

Sure, use the code.

Just make the two tables local, I forgot that!

Ah right, well seeming as I dont own a mac I wont be able to test this, but has anyone else noticed a speed difference in stuff like indexing tables and raw values when changed to xcode, mainly a positive speed increase Id guess.

Thanks, ive done that now

Well exactly but if running a code through an ide it has to be converted first, so heavy use of image functions and such I’m guessing would slow it down whereas if it were converted to xcode and run through that then it would be faster as it isn’t going through the IDE, just logical thinking in guessing that it does so… Correct me if Im wrong.

On the other hand here is an algorithm I thought up earlier, I assume its been thought of before it is quite simple, anyway: http://youtu.be/plN745WuoN4

I think it just has to convert the code when you first start it, not the whole time it’s running. And, of course, in 1.5.3 TLL made sprite() almost as fast as mesh.

I found the flood fill algorithm in Spritely. It’s a little bit down in the EditGrid tab. Code:

``````function EditGrid:testPix(x, y, c, img)
local r, g, b, a
test =false
if x >= 1 and x <= img.width then
if y >= 1 and y <= img.height then
r, g, b, a = img:get(x, y)
if a == c.a and b == c.b and g == c.g and r == c.r then
test = true
end
end
end
return test
end

function EditGrid:floodFill()
local x, y, c, i, spots, timg
local spot = {}
img = self.img:copy()
-- find the color that was touched
r, g, b, a = img:get(self.cx, self.cy)
c = color(r, g, b, a)
-- if touched = color to use, then exit
if c == self.clr then
return nil
end
-- use the initial location as first candidate spot
spots = 1
spot[1] = vec2(self.cx, self.cy)
img:set(spot[1].x, spot[1].y, self.clr)
oldspots = 1
searching = true
-- keep going until there are no new spots found
while searching do
for i = 1, oldspots do
-- find candidates
x = spot[i].x
y = spot[i].y

-- check down
if self:testPix(x, y - 1, c, img) then
img:set(x, y - 1, self.clr)
spots = spots + 1
spot[spots] = vec2(x, y - 1)
end
-- check left
if self:testPix(x - 1, y, c, img) then
img:set(x - 1, y, self.clr)
spots = spots + 1
spot[spots] = vec2(x - 1, y)
end
-- check right
if self:testPix(x + 1, y, c, img) then
img:set(x + 1, y, self.clr)
spots = spots + 1
spot[spots] = vec2(x + 1, y)
end
-- check up
if self:testPix(x, y + 1, c, img) then
img:set(x, y + 1, self.clr)
spots = spots + 1
spot[spots] = vec2(x, y + 1)
end
end
if spots > 1024 then
searching = false
end
if spots == oldspots then -- no new pixels to change found
searching = false
end
oldspots = spots
end
spot = nil
self.img = img:copy()
end
``````

but how long does it take if you fill an area half the size of the screen?

@Luatee - maybe you should use a shader, if you are converting every pixel of a certain colour. You could draw to an image with setContext and a shader.

But why are you flood filling such a big image anyway?

I’m making a drawing app, I’ve never properly looked at shaders i meant to but I never got round to it so i can’t help myself there

A shader can flood fill the entire image, but not just part of the image (it would replace EVERy matching pixel in the whole image), so it wouldn’t work in a drawing app.

@Luatee - if you can’t make flood fill any faster, you can at least entertain the user while it is happening (after all, that’s why splash screens were invented!). This version of the code fills progressively so the user can see how it’s going, using coroutines.

``````function setup()
flood=coroutine.create(floodFill)
coroutine.resume(flood,img,1,1,color(255,255,0,255),color(0,0,0,0))
end

function draw()
background(220)
sprite(img,WIDTH/2,HEIGHT/2)
if flooding then coroutine.resume(flood) end
end

function floodFill(img,startX,startY,fillColor,interiorColor)
local tbl={}
local tbl2={}
local counter=0
flooding=true
tbl[1]=vec2(startX,startY)
local c1=(interiorColor.r*256+interiorColor.g)*256+interiorColor.b
while #tbl>0 do
local x,y=tbl[1].x,tbl[1].y
tbl2[x*3000+y]=1
local r,g,b,a = img:get(x,y)
--local c2=(r*256+g)*256+b
--if (c1==c2) then
if interiorColor.r==r and interiorColor.g==g and interiorColor.b==b then
img:set(x,y,fillColor)
if x<img.width and tbl2[(x+1)*3000+y]==nil then tbl[#tbl+1]=vec2(x+1,y) end
if x>1 and tbl2[(x-1)*3000+y]==nil then tbl[#tbl+1]=vec2(x-1,y) end
if y>1 and tbl2[x*3000+y-1]==nil then tbl[#tbl+1]=vec2(x,y-1) end
if y<img.height and tbl2[x*3000+y+1]==nil then tbl[#tbl+1]=vec2(x,y+1) end
end
table.remove(tbl,1)
counter = counter + 1
if counter%10000==0 then coroutine.yield() end
end
flooding=false
end
``````