Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!munnari.oz.au!metro!natmlab.dap.csiro.au!hades!greyham
From: greyham@hades.ausonics.oz.au (Greyham Stoney)
Newsgroups: comp.graphics
Subject: Fast Flooding algorithm: anyone got one?. (want to find a centroid)
Message-ID: <1990Oct15.022751.10968@hades.ausonics.oz.au>
Date: 15 Oct 90 02:27:51 GMT
Organization: Ausonics Pty Ltd, Sydney, Australia
Lines: 41

I have a 2D problem in which I need to find the centroid of an enclosed space
(an image of an object). One way I've thought of is via flooding (like flood-
fill); I have a rather dumb, slow algorithm I worked out, and I'm wondering if
there's a faster one.

My flooding algorithm uses a stack to hold the points that need to be visited,
and the region is bounded by points already marked as visited when it starts:

	pick any point in the object (x,y)
	push (x,y)
	while the stack's not empty
	{
		pop (x,y)
		if (x,y) has not been visited	/* optimisation */
		{
			mark (x,y) as visited

			area++; sigma_x += x; sigma_y += y;
				/* for centroid calculation */

			if (x,y+1) has not been visited: push(x,y+1)
			if (x+1,y) has not been visited: push(x+1,y)
			if (x,y-1) has not been visited: push(x,y-1)
			if (x-1,y) has not been visited: push(x-1,y)
		}
	}

One problem is that the stack grows very large since unvisited points get
entered several times (hence the "if (x,y) has not been visited" optimisation).
It's also not real speedy.

So; does anyone know how fast graphics packages do flood-fills? (yes, in
assembler, I know: but using what algorithm).

						thanks,
							Greyham.
-- 
/*  Greyham Stoney:                            Australia: (02) 428 6476
 *  greyham@hades.ausonics.oz.au - Ausonics Pty Ltd, Lane Cove, Sydney, Oz.
 *		Neurone Server: Brain Cell not Responding.
 */