greyham@hades.ausonics.oz.au (Greyham Stoney) (10/15/90)
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.
*/lambert@spectrum.cs.unsw.oz.au (Tim Lambert) (10/16/90)
>>>>> On 15 Oct 90 02:27:51 GMT, greyham@hades.ausonics.oz.au (Greyham Stoney) said: > 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. The centroid only depends on the boundary of the object, so unless you shapes are only a few pixels in size, it would be faster to follow the boundary of the object and use the formula that calculates the centroid of a polygon from its vertices. > [Straight forward recursive 4-connected flood fill algorithm deleted] Faster methods involve filling in "spans" (rows of interior pixels). Most computer graphics books will give more description. (In particular Foley, van Dam, Feiner and Hughes) Tim
ph@miro.Berkeley.EDU (Paul Heckbert) (10/16/90)
In article <1990Oct15.022751.10968@hades.ausonics.oz.au> greyham@hades.ausonics.oz.au (Greyham Stoney) writes: > So; does anyone know how fast graphics packages do flood-fills? Most people use a stack of horizontal line segments, I believe. Most of the fill algorithms in the literature are based on this idea. C source for a simple fill algorithm is available in the book "Graphics Gems" from Academic Press. You can buy the book and read the articles by Ken Fishkin and myself discussing the algorithms, or if all you want is code, it's available via ftp (does that work from Australia?) Here's how to get Graphics Gems source via ftp: All C source files in the book are available via anonymous ftp from site 'weedeater.math.yale.edu'. To download the files, connect to this site with an ftp program. For user name type the word 'anonymous'; for password enter your last name. When you are logged in, type 'cd pub/GraphicsGems/src'. Each program from the book is stored in its own plaintext file. I suggest you first download the file README (type 'get README', then quit ftp and open the file with any text editor); among other things it describes how to download the rest of the directory, identifies the administrator of the site (who will collect bug reports, etc.), and provides a table of contents so you can identify the source files with their corresponding Gems. After you get all the files, look at SeedFill.c; that may help you with your problem. Paul Heckbert, Computer Science Dept. 570 Evans Hall, UC Berkeley INTERNET: ph@miro.berkeley.edu Berkeley, CA 94720 UUCP: ucbvax!miro.berkeley.edu!ph
bernie@ecr.mu.oz.au (Bernie Kirby) (10/16/90)
In article <28839@pasteur.Berkeley.EDU>, ph@miro.Berkeley.EDU (Paul Heckbert) writes: > In article <1990Oct15.022751.10968@hades.ausonics.oz.au> > greyham@hades.ausonics.oz.au (Greyham Stoney) writes: >> [..] > or if all you want is code, it's available via ftp (does that work > from Australia?) Sure does. > > Here's how to get Graphics Gems source via ftp: The GraphicsGems source code is also available from within Australia from "gondwana.ecr.mu.oz.au" [128.250.1.63]. For ACSnet sites use: "fetchfile -dgondwana.ecr.mu.oz -LV ." for more info.