Recursive flood filling algorithm

Question

I am trying to create an algorithm that could populate an int array in C #. Basically, as a filling tool in MS Paint, I have a color, and if I select the (x, y) coordinates in the array, it will replace all the neighbors with the same initial color with the new color.

Example:

[0,0,0] [0,1,0] [1,1,0] 

If I put 3 in (0,0), the array will become:

 [3,3,3] [3,1,3] [1,1,3] 

So, I tried this in recursive mode, but it works, but not all the time. In fact, I sometimes have a "Stack Overflow" error (seems appropriate). Here is my code, it would be great if you could tell me what is wrong :)

 public int[,] fill(int[,] array, int x, int y, int initialInt, int newInt) { if (array[x, y] == initialInt) { array[x, y] = newInt; if (x < array.GetLength(0) - 1) array = fill(array, (x + 1), y, initialInt, newInt); if (x > 0) array = fill(array, (x - 1), y, initialInt, newInt); if (y < array.GetLength(1) - 1) array = fill(array, x, (y + 1), initialInt, newInt); if (y > 0) array = fill(array, x, (y - 1), initialInt, newInt); } return array; } 

Thanks!

Answer 1

How to use stack / queue to manage remaining work?

 public void Fill(int[,] array, int x, int y, int newInt) { int initial = array[x,y]; Queue<Tuple<int,int>> queue = new Queue<Tuple<int,int>>(); queue.Push(new Tuple<int, int>(x, y)); while (queue.Any()) { Tuple<int, int> point = queue.Dequeue(); if (array[point.Value1, point.Value2] != initial) continue; array[point.Value1, point.Value2] = newInt; EnqueueIfMatches(array, queue, point.Value1 - 1, point.Value2, initial); EnqueueIfMatches(array, queue, point.Value1 + 1, point.Value2, initial); EnqueueIfMatches(array, queue, point.Value1, point.Value2 - 1, initial); EnqueueIfMatches(array, queue, point.Value1, point.Value2 + 1, initial); } } private void EnqueueIfMatches(int[,] array, Queue<Tuple<int, int>> queue, int x, int y, int initial) { if (x < 0 || x >= array.GetLength(0) || y < 0 || y >= array.GetLength(1)) return; if (array[x, y] == initial) queue.Enqueue(new Tuple<int, int>(x, y)); } 

Answer 2

This is an example tutorial on why using recursion is not always appropriate. Recursion is great for traversing data structures that are essentially recursive (like trees), but your pixel data array is not.

I suggest adding a counter to your code for printing how often the fill() function is called. Each time the function is called, your computer must create a new frame on the stack in memory (so that it knows what position of memory it should return after the function completes). The recursive image filling algorithm calls the fill() function a huge number of times, so the stack will grow very quickly. It has a limited size, so it will overflow for large images.

The solution is to implement an iterative padding algorithm using loops instead of recursion to iterate through the pixels.

See Wikipedia for recursion and stack overflow , or “Computer Graphics, Principles, and Practice” by Foley et al. for a more detailed introduction to the basic algorithms of computer graphics.

Answer 3

As already mentioned, the problem is related to the number of recursive calls. On a 32-bit machine, you have 4 bytes for pointers, so if you have a 512 * 512 image and you want to fill it all, only function pointers will occupy 512 * 512 * 4 bytes = 1 MB of memory in your stack. And this is the default size for the stack . Regardless of the function pointers, you have 5 more links that you pass ( array , x , y , initialInt , newInt )) that are all copied with each call as temporary objects and are on the stack until the function call completes. In an image of the same size, this is still 512 * 512 * 5 * 4 bytes = 5 MB of memory.

To solve your problem, you can change (same link as above) stack size.

In addition, to save some space on the stack, you can consider transferring the parameters inside one object, in which case you will only have 4 bits of temporary memory for each call instead of 20.

However, as stated above, the best solution is to rewrite your algorithm iteratively.