Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!rpi!batcomputer!munnari.oz.au!metro!usage.csd.unsw.oz.au!usage.csd!lambert From: lambert@spectrum.cs.unsw.oz.au (Tim Lambert) Newsgroups: comp.graphics Subject: Re: Fast Flooding algorithm: anyone got one?. (want to find a centroid) Message-ID: Date: 16 Oct 90 01:00:03 GMT References: <1990Oct15.022751.10968@hades.ausonics.oz.au> Sender: news@usage.csd.unsw.oz.au Organization: EE & CS, Uni of NSW, Australia Lines: 19 In-reply-to: greyham@hades.ausonics.oz.au's message of 15 Oct 90 02:27:51 GMT >>>>> 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