Flood Fill Algorithm, non recursive, fixed memory usage

[angros47]

Usually, flood fill is achieved through a recursive algorithm: even FreeBasic graphic library uses the scanline method, that is an improvement of the standard method. An alternative is to use a queue based algorithm, that doesn't overload the stack, but still requires to allocate more and more memory depending on the size and complexity of the picture.

The subject, years ago, has already been discussed here: viewtopic.php?f=7&t=7728

An alternative is to mark the point that need to be evaluated in the picture itself, but this is not always possible (since it requires to reserve a color for that purpose, if the image is one bit this is not possible.

But actually, an algorithm that uses a fixed (and very small) amount of memory, and doesn't "cheat" by marking the image, exists: it is based on the right hand rule (used to solve mazes), and simulates a painter that tries not to get stuck in a corner.

The code is a port of this: https://github.com/DW0RKiN/Flood-fill, and it is described on wikipedia.

Code: Select all

dim shared Mask(7) as integer

dim shared direction as integer	'1=N 2=E 3=S 4=W
dim shared Now_X as integer
dim shared Now_Y as integer

dim shared loop_direction as integer
dim shared Loop_X as integer
dim shared Loop_Y as integer

dim shared Looping_mode as integer

sub SetMask
	if direction=1 then
		Mask(0)=point(Now_X-1, Now_Y-1)
		Mask(1)=point(Now_X, Now_Y-1)
		Mask(2)=point(Now_X+1, Now_Y-1)
		Mask(3)=point(Now_X-1, Now_Y)
		Mask(4)=point(Now_X+1, Now_Y)
		Mask(5)=point(Now_X-1, Now_Y+1)
		Mask(6)=point(Now_X, Now_Y+1)
		Mask(7)=point(Now_X+1, Now_Y+1)
	elseif direction=2 then
		Mask(0)=point(Now_X+1, Now_Y-1)
		Mask(1)=point(Now_X+1, Now_Y)
		Mask(2)=point(Now_X+1, Now_Y+1)
		Mask(3)=point(Now_X, Now_Y-1)
		Mask(4)=point(Now_X, Now_Y+1)
		Mask(5)=point(Now_X-1, Now_Y-1)
		Mask(6)=point(Now_X-1, Now_Y)
		Mask(7)=point(Now_X-1, Now_Y+1)
	elseif direction=3 then
		Mask(0)=point(Now_X+1, Now_Y+1)
		Mask(1)=point(Now_X, Now_Y+1)
		Mask(2)=point(Now_X-1, Now_Y+1)
		Mask(3)=point(Now_X+1, Now_Y)
		Mask(4)=point(Now_X-1, Now_Y)
		Mask(5)=point(Now_X+1, Now_Y-1)
		Mask(6)=point(Now_X, Now_Y-1)
		Mask(7)=point(Now_X-1, Now_Y-1)
	elseif direction=4 then
		Mask(0)=point(Now_X-1, Now_Y+1)
		Mask(1)=point(Now_X-1, Now_Y)
		Mask(2)=point(Now_X-1, Now_Y-1)
		Mask(3)=point(Now_X, Now_Y+1)
		Mask(4)=point(Now_X, Now_Y-1)
		Mask(5)=point(Now_X+1, Now_Y+1)
		Mask(6)=point(Now_X+1, Now_Y)
		Mask(7)=point(Now_X+1, Now_Y-1)
	end if
end sub

sub Fill_and_Step
	Looping_mode=0
	pset (Now_X, Now_Y)
	select case Direction
	case 1
		Now_Y=Now_Y-1
	case 2
		Now_X=Now_X+1
	case 3
		Now_Y=Now_Y+1
	case 4
		Now_X=Now_X-1
	end select

	SetMask
end sub

sub StepForward
	if Looping_mode<>0 then
		if Loop_X=Now_X andalso Loop_Y=Now_Y then
			if Loop_direction=direction then
				Fill_and_Step
				exit sub
			else
				Looping_mode=0
				direction=Loop_direction
			end if
		end if
		
	else 
		if (	(Mask(3)<>0 andalso Mask(4)=0 andalso Mask(6)=0) orelse _
			(Mask(3)=0 andalso Mask(4)<>0 andalso Mask(6)=0) orelse _
			(Mask(3)=0 andalso Mask(4)=0 andalso Mask(6)=0) orelse _
			(Mask(3)=0 andalso Mask(4)=0 andalso Mask(6)<>0) )=0 then

				Looping_mode=1
				Loop_X=Now_X: Loop_Y=Now_Y
				Loop_direction=direction

		end if


	end if


	select case Direction
	case 1
		Now_Y=Now_Y-1
	case 2
		Now_X=Now_X+1
	case 3
		Now_Y=Now_Y+1
	case 4
		Now_X=Now_X-1
	end select

	SetMask


end sub


sub fill (x as integer, y as integer)
	Now_X=x: Now_Y=y
	direction=1

	do
		if Mask(4)=0 then direction=(direction mod 4)+1:SetMask   'turn right
		if Mask(1)<>0 andalso Mask(3)<>0 andalso Mask(4)<>0 andalso Mask(6)<>0 then pset (Now_X, Now_Y): exit sub

		if Mask(3)<>0 andalso Mask(4)<>0 andalso Mask(6)<>0 then 
			Fill_and_Step
		elseif Mask(1)<>0 then
			direction=((direction+2) mod 4)+1
			SetMask
		elseif Mask(3)<>0 then
			StepForward
		elseif  (Mask(1)=0 andalso Mask(2)<>0 andalso Mask(4)=0) orelse _
			(Mask(0)<>0 andalso Mask(1)=0 andalso Mask(3)=0) orelse _
			(Mask(3)=0 andalso Mask(5)<>0 andalso Mask(6)=0) orelse _
			(Mask(4)=0 andalso Mask(6)=0 andalso Mask(7)<>0) then

			StepForward
		else
			Fill_and_Step
		end if


	loop
	

end sub



screenres 800,600


for x as integer=0 to 800 step 20
	for y as integer=0 to 600 step 20
		circle (x,y),9
	next
next

fill (107,107)

sleep

Compared with other methods, it is very slow. But the approach to the problem is instructive.

[counting_pine]

Pretty cool to see a fixed-memory algorithm. It would be interesting to know how fast it is in Big-O notation..

Unfortunately the example image becomes a lot slower if you draw a short-ish diagonal line across the screen:

Code: Select all

line (0,0)-(100,100)

I have a horrible feeling it's O(n^4) or something..

[angros47]

I guess this is the reason why recursive, or queue-based algorithm are usually preferred. This algorithm is very slow, and nowadays the stack space is usually enough to avoid issues (and since the used memory is released immediately, there is no real gain in reducing memory usage).

Also, in modern graphic often flood-filling is replaced by convex polygon filling.

[D.J.Peters]

Hello angros47 good algo
do you know FillBoundary from my gfx addon package ?
viewtopic.php?f=14&t=25058&p=236603

Joshy

[angros47]

Hello, D.J. Peters

I had a look at your algorithm... it is the standard one, based on pure recursion (often used as example, since it's the simplest), with a series of checks to protect it from stack overflow. It requires a big stack space. The algorithm used in the fbgfx library, instead, is the scanline based version of flood fill.

[D.J.Peters]

I had a look at your algorithm... it is the standard one, based on pure recursion (often used as example, since it's the simplest)

You are a pretty good coder but in this case you are blind.

Joshy

[angros47]

I examined it more: basically, as far as I understand, for small areas it uses the standard algorithm: if the area is too large, and takes too much stack space, it adds the points not yet processed to a queue, and iterates until the queue is emptied. A sort of hybrid approach between the recursive and non recursive one.