Thread: [Algorithms] floodfill

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

Where can I find a description of the floodfill algorithm, with some =
good C-source?

 / Per

Where can't you would be a better question. Google should pop this one =
out really quickly.

The flood fill algorithm is pretty simple. You pretty much do this per =
node - fill it, recurse to any neighbour node (or pixel) with the same =
value as the original (doing the same thing).

Ie, in pseudo C code

void Fill(Node* x,Colour* original,Colour* newc) {
    node->nodecol=3Dnewc; // Colour this node
    for all n neighbours of X    =20
        if (node->neighbour[n]->nodecol=3D=3Doriginal)
            Fill(node->neighbour[n],original,newc);
}

There is the scan line method, but that basically has a scanline run =
(ie, you calculate a vertical/horizontal length that is all the same =
colour), but it is essentially the same algorithm (with a bit of a speed =
up).=20

Conor Stokes

----- Original Message -----=20
  From: Per Jahn=20
  To: gda...@li...=20
  Sent: Saturday, September 08, 2001 3:17 PM
  Subject: [Algorithms] floodfill

  Where can I find a description of the floodfill algorithm, with some =
good C-source?
  =20
  =20
   / Per
  =20

>The flood fill algorithm is pretty simple. You pretty much do this per
node -
>fill it, recurse to any neighbour node (or pixel) with the same value as
the
>original (doing the same thing).
>Ie, in pseudo C code
>[code]

Of course, this method works, but it's a good recipe for stack overflows...

>There is the scan line method, but that basically has a scanline run
>(ie, you calculate a vertical/horizontal length that is all the same
colour),
>but it is essentially the same algorithm (with a bit of a speed up).

That one is a lot better, since it does not push values that will not be
used...

>Where can I find a description of the floodfill algorithm, with some good
>C-source?

You should consult the archives of comp.graphics.algorithms, and their
FAQ also, because the flood fill problem has been discussed numerous
time :) You will find source codes in C, Pascal, pseudo code, theorical
discussions about the probabilities of having a stack overflow when using
specific graphical patterns (try to use Windows paint to fill a picture made
of a patterns of dots regularly spaced...) and so on :)

http://www.faqs.org/faqs/graphics/algorithms-faq/
http://groups.google.com/groups?as_q=fill&as_oq=flood%20seed&as_ugroup=comp.
graphics.algorithms

Have fun.

    Mickael Pointier

> Of course, this method works, but it's a good recipe for stack
overflows...

Not if you make your own dynamic stack. Which is slower, but works.

It also depends what you want your flood fill algorithm for. Flood filling a
pregenerated portal-sector system so you can get rid of all useless geometry
for instance (ala the quake engines).

> That one is a lot better, since it does not push values that will not be
> used...

But it is a special case for a uniform grid really.

Conor Stokes

> Of course, this method works, but it's a good recipe for stack
> overflows...

I just don't understand people who code an algorithm with boundless
recursion. To me, re-doing it "iteratively" with a simple priority queue or
list-used-as-stack seems simpler than the recursion, and it often runs
faster, too (if you have a good allocator).

Seeing as flood fill has a vague likeness to A search (except for the cost
pruning part) this is actually moderately relevant to the implementation of
other algorithms, too.

Cheers,

				/ h+

> > Of course, this method works, but it's a good recipe for stack
> > overflows...
>
> I just don't understand people who code an algorithm with boundless
> recursion. To me, re-doing it "iteratively" with a simple priority queue
or
> list-used-as-stack seems simpler than the recursion, and it often runs
> faster, too (if you have a good allocator).

For me, real recursion (using the stack of the processor) and iterative
versions that use software managed stacks/lists are all recursive by nature.
You will run into the same problems, eventually later with the hand made
version since you do not have the processor stack frame pushed every
call.

Of course one should test for errors, but if you need a "flood fill", your
are not necesserily happy with a "non crashed but only half filled" result.

When I wrote "is a good recipe for stack overflow", I mean it's possible
to use methods that do not waste so much memory (and processor time)
thus giving you a chance to actually perform the requested operation.

    Mickael Pointier

Thread: [Algorithms] floodfill

gdalgorithms-list