jackson@homxc.ATT.COM (B.JACKSON) (02/14/89)
Here's the problem: I've got a bitmapped display that has an image of a ragged-edged closed perimeter surrounding an open area. I need to know the area of the opening. The boundry of the area looks like someone spray-painted a circle of pixels on the screen -- I can guarentee a closed boundry of connected pixels, but there are some individual pixels (and groups of pixels) 'floating' around out in the area I want to measure (I don't want to count the 'floaters' in the area). The perimeter has, as you might guess, thousands of small inclusions. My first guess at how to measure the area is to perform a "fill" operation and count the number of pixels I generate to do the fill -- but I'm open to suggestions. (I can guarentee I can plant a seed pixel in a clear space within the circle if that helps.) If anyone has a recommended algorithm for finding the enclosed area (or for doing a fill on an arbitrarily-bounded region) please let me know. If you've got source code for solving such a problem (or can point me to a reference that does) I will be even more grateful! Thanks in advance, B. Scott Jackson Room 3D-418 AT&T Bell Laboratories Crawford's Corner Rd. Holmdel, NJ 07733 (201) 949-6495 homxc!jackson
glenn@eos.UUCP (Glenn Meyer) (02/19/89)
From article <5532@homxc.ATT.COM>, by jackson@homxc.ATT.COM (B.JACKSON): > Here's the problem: I've got a bitmapped display > that has an image of a ragged-edged closed perimeter surrounding an > open area. I need to know the area of the opening. The > boundry of the area looks like someone spray-painted a > circle of pixels on the screen -- I can guarentee a closed > boundry of connected pixels, but there are some individual > pixels (and groups of pixels) 'floating' around out in the > area I want to measure (I don't want to count the 'floaters' > in the area). The perimeter has, as you might > guess, thousands of small inclusions. How about a "scan-line fill" of the area? If you can define a simple geometric bounding primitive (box, circle or ellipse, for instance) that doesn't include other such bounded regions, then, for each pixel row, you should be able to count the number of pixels between the first and last perimeter pixel in that row, within the bounding primitive. Unlike the pixel or scan-line seed fill, this would count all interior pixels that are part of either the boundary or of a "floater". The sum of these pixel-row counts should give you the correct area, unless you're trying to exclude interior pixels with the same property (gray-scale?) as the outer perimeter pixels. In that case, count only the pixels that don't have the perimiter property. If, in addition, you're trying to exclude from the area calculation all holes ("floaters" that themselves form a region), look in the book "Computer Graphics: A Programming Approach" for the algorithm that scan-converts polygons with concave boundaries and holes. (Sorry, I don't have the complete reference for the algorithm.) -- Glenn Meyer (glenn%carma@{io,aurora,eos,pioneer}.arc.nasa.gov) CARMA, Sterling Software NASA-Ames, M.S. 233-14 Moffett Field, Ca. 94035