OT: Flood fill algorithm (Graphics)

From	nobody@example.org (Scott)
Newsgroups	comp.lang.c
Subject	OT: Flood fill algorithm (Graphics)
Date	2019-06-07 04:02 +0000
Organization	XMission http://xmission.com/
Message-ID	<5cf9d25b.2656172643@core> (permalink)

Show all headers | View raw

I'm messing around with a flood fill function I wrote a long time ago.

Flood fills can be seductively simple, until you find yourself
cornered with a recursive algorithm that chews through memory like
crazy. So I wrote mine to be non-recursive and use as little memory as
possible in the form of a simple queue.

In my notes I wrote that I'd never seen it need a queue bigger than
twice the width of the raster being painted. I recall the truth of
that, but I know more now than I did then. I have better ideas on
generating pathological test cases, and I can test with much larger
rasters than were feasible in the day.

Point is, I'm asking you guys for ideas on hard cases for testing a
flood fill. I've done the usual (backgammon board, A/B dots, random
dots) and found a number of test patterns on the web, and haven't
found one that gets anywhere near using 100% of the queue.

The best one I got so far is a one-pixel Hilbert curve, which pushes
queue utilization up really fast. At 512x512 it breaks the 2*width
limit by 7%, and at 8192x8192 it needs a queue of almost 11*width to
run. It seems to fall into a pattern of needing about 50% more queue
space for every doubling of width. It's an interesting result.

Back to comp.lang.c | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

OT: Flood fill algorithm (Graphics) nobody@example.org (Scott) - 2019-06-07 04:02 +0000
  Re: OT: Flood fill algorithm (Graphics) fir <profesor.fir@gmail.com> - 2019-06-06 23:54 -0700
    Re: OT: Flood fill algorithm (Graphics) Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-06-07 07:57 -0700
      Re: OT: Flood fill algorithm (Graphics) nobody@example.org (Scott) - 2019-06-07 16:06 +0000
      Re: OT: Flood fill algorithm (Graphics) jadill33@gmail.com - 2019-06-07 09:56 -0700
  Re: OT: Flood fill algorithm (Graphics) unidef <jon@unidef-systems.com> - 2019-06-10 02:47 -0500
  Re: OT: Flood fill algorithm (Graphics) Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> - 2019-06-13 00:25 +1000

csiph-web