Alex Rivera | Logout

a working non-recursive floodfill algorithm written in C?

Asked 2009-08-10T20:46:54.320
19

I've been 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 and they have all been exceptionally tempermental: either they leave gaps in strange places, or flood the whole area (when they should be enclosed).

Anyone has a NON-recursive floodfill working sourcecode written in C (or c++ that isn't too heavily OOP and I can disentangle easily enough)?

c algorithm flood-fill
Edit
Report

1 Answer

1

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.

answered 2009-08-11T02:18:49.727

Your Answer