does anyone have a working non-recursive floodfill algorithm written in C?

Question

over the last few days I've been desperately trying to find a working floodfill algorithm. Of the many algorithms i've tried only the 'recursive line fill' one behaves exactly as it should with the major caveat that it occasionally blows the stack. :(

I have tried many non-recursive implementations I've found on various websites and they have all been exceptionally tempermental: either they leave gaps in strange places, or flood the whole area (when they should be enclosed). I have also tried my hand at implementing a few of these algorithms myself but with limited success. I am at the point now where i really just need some working sourcecode! If anyone has a NON-recursive floodfill written in C (or c++ that isn't too heavily OOP and i can disentangle easily enough) can they PLEASE share it with me? I am at the stage now where I need it fairly urgently and certainly cannnot spend anymore time on this. :(

sorry to be a dork and ask for the sourcecode but I've hit a bit of a dead-end.

Thanks in advance if you can help!

Answer 1

Isn't there a proof somewhere that all recursive functions can be implemented as an iterative function by using local data to mimic a stack? You could probably use std::vector to create stack-like behavior of the algorithm without blowing the stack since it will use the heap.

EDIT: I noticed you are using C, so instead of std::vector, you could just implement similar behavior via realloc as you need to add more elements to your local "stack" of whatever data structure you would use.

Answer 2

You can convert any recursive algorithm to iterative by creating an explicit stack or queue and loading work onto it/pulling it off.

All you need is to choose a nice, compact representation of the work to be done. Worst case: create a struct holding the arguments you would normally pass to the recursive version...

Answer 3

A quick googling brings up the Wikipedia article on Flood Fill which includes pseudocode implementations which are not recursive. Below is some code that could help get you started, a basic queue implementation in C:

typedef struct queue_ { struct queue_ *next; } queue_t;
typedef struct ffnode_ { queue_t node; int x, y; } ffnode_t;

/* returns the new head of the queue after adding node to the queue */
queue_t* enqueue(queue_t *queue, queue_t *node) {
    if (node) {
        node->next = queue;
        return node;
    }
    return NULL;
}

/* returns the head of the queue and modifies queue to be the new head */
queue_t* dequeue(queue_t **queue) {
    if (queue) {
        queue_t *node = (*queue);
        (*queue) = node->next;
        node->next = NULL;
        return node;
    }
    return NULL;
}

ffnode_t* new_ffnode(int x, int y) {
    ffnode_t *node = (ffnode_t*)malloc(sizeof(ffnode_t));
    node->x = x; node->y = y;
    node->node.next = NULL;
    return node;
}

void flood_fill(image_t *image, int startx, int starty, 
                color_t target, color_t replacement) {
    queue_t *head = NULL;
    ffnode_t *node = NULL;

    if (!is_color(image, startx, starty, target)) return;

    node = new_ffnode(startx, starty);
    for ( ; node != NULL; node = (ffnode_t*)dequeue(&head)) {
        if (is_color(image, node->x, node->y, target)) {
            ffnode_t *west = node, *east = node;

            recolor(image, node->x, node->y, replacement);
            /* 1. move w to the west until the color of the node to the west
               no longer matches target */
            ...
        }
    }
}

Answer 4

Just implement a stack of int pairs with an array of some fixed size (maybe the size of the image in pixels or the square root of that, for example) for the stack and track the top with an int.

Here is some C# code that implements floodfill non-recursively:

private static void Floodfill(byte[,] vals, Point q, byte SEED_COLOR, byte COLOR)
{
    int h = vals.GetLength(0);
    int w = vals.GetLength(1);

    if (q.Y < 0 || q.Y > h - 1 || q.X < 0 || q.X > w - 1)
     return;

    Stack<Point> stack = new Stack<Point>();
    stack.Push(q);
    while (stack.Count > 0)
    {
     Point p = stack.Pop();
     int x = p.X;
     int y = p.Y;
     if (y < 0 || y > h - 1 || x < 0 || x > w - 1)
      continue;
     byte val = vals[y, x];
     if (val == SEED_COLOR)
     {
      vals[y, x] = COLOR;
      stack.Push(new Point(x + 1, y));
      stack.Push(new Point(x - 1, y));
      stack.Push(new Point(x, y + 1));
      stack.Push(new Point(x, y - 1));
     }
    }
}

Answer 5

Here's some C++ code that does what you want. It uses a queue, and is more efficient about insertions into the queue.

connectedRegion(const Point& source, RegionType& region, const Color target)
{
    Color src_color = color_of(source, region);
    if (region.count(source) == 0 || src_color == target)
     return;
    std::queue<Point> analyze_queue;
    analyze_queue.push(source);

    while (!analyze_queue.empty())
    {
     if (color_of(analyze_queue.front()) != src_color)
     {
      analyze_queue.pop();
      continue;
     }
     Point leftmost_pt = analyze_queue.front();
            leftmost_pt.col -= 1;
     analyze_queue.pop();
     Point rightmost_pt = leftmost_pt;
            rightmost_pt.col += 2;
     while (color_of(leftmost_pt, region) == src_color)
      --leftmost_pt.col;

     while (color_of(rightmost_pt, region) == src_color)
      ++rightmost_pt.col;

     bool check_above = true;
     bool check_below = true;
            Point pt = leftmost_pt;
            ++pt.col;
     for (; pt.col < rightmost_pt.col; ++pt.col)
     {
      set_color(pt, region, target);

      Point pt_above = pt;
                    --pt_above.row;
      if (check_above)
      {
       if (color_of(pt_above, region) == src_color)
       {
        analyze_queue.push(pt_above);
        check_above = false;
       }
      }
      else // !check_above
      {
       check_above = (color_of(pt_above, region) != src_color);
      }

      Point pt_below = pt;
                    ++pt_below.row;
      if (check_below)
      {
       if (color_of(pt_below, region) == src_color)
       {
        analyze_queue.push(pt_below);
        check_below = false;
       }
      }
      else // !check_below
      {
       check_below = (color_of(pt_below, region) != src_color);
      }
     } // for 
    } // while queue not empty
    return connected;
}

Answer 6

I have a non-recursive flood fill, but I won't post it because it's the solution to a homework assignment. But here's a hint: depth-first search, which is the natural algorithm, uses far more auxiliary space than a breadth-first search. Here's what I wrote at the time (suitably expurgated):

I dare not try depth-first search by simple recursion; the depth of recursion is limited only by REDACTED, and my experiments show that an PROBLEM REDACTED could nevertheless require a stack depth of over a million. So I put the stack in an auxiliary data structure. Using an explicit stack actually makes it easy to try breadth-first search as well, and it turns out that breadth-first search can use forty times less space than depth-first search.

For my data structure I used the Seq_T from Dave Hanson's C Interfaces and Implementations; changing from depth-first to breadth-first requires changing just one function call.

Answer 7

We noticed that our floodfill implementation on 3d volumes was consuming way much memory; so we modified the code in the following ways (there was a vast improvement):

1. Create a sphere of radius = 10 voxs around the starting point, and mark all the voxels within that radius as "to be visited"

2. If the current voxel > threshold, insert 1.

3. Go to the neighbors [+1, -1, 0] (also check that one doesn't revisit any voxel), if the neighbor.getVoxVal = 0 (the initialization value for the target volume), then it falls at the boundary of the sphere, insert the coordinates in a different stack. (this would be the starting point for our next sphere)

4. radius = radius + 10 (voxels)

So at a time, our floodfill is working on a concentric sphere and filling things up, which is a part of the entire volume, and as I said, this has reduced the memory consumption drastically, but I am still searching for an implementation/idea that would be better.

Answer 8

It's too bad that no one has an implementation of the fixed-memory flood fill algorithm mentioned in the Wikipedia entry on flood fill. That would be cool. :)