eric@eddie.MIT.EDU (Eric Van Tassell) (07/21/89)
Does anybody have a fast algorithm for taking an image (collection of pixel values) and determining the closed regions? See ascii pic below. |------------------------------------------------------------| | * * | | * 1 * | | * * | | **************** | | * * | | * 2 * | | * *********** | | * * * 3 * | | ******* ********** | | ** * | | ************ ******* | | * 4 * | | *************************** | | | | | |------------------------------------------------------------| What I want is an algorithm (fast) that will tell me that regions 2,3,4 are closed (and can be filled) but region 1 is not. By "telling me that they are closed I supposed I mean that the algorithm should return a list of lists of points representing the polygonal boundaries of all enclosed regions. I will be doing this under X11R3 but I am mostly concerned with a fast algorithm and dont really care if it is X specific. As a matter of fact since I will have to port this to PM, dependance on X would be a lose. But since I am asking for free advice I'll take anything. TIA! eric@eddie.mit.edu -- Eric Van Tassell(dlcdev!eric@eddie.mit.edu) Progress Software Corp. 22B Cotton Rd. Nashua, NH 03063 {603-882-2488}
rws@EXPO.LCS.MIT.EDU (07/21/89)
If it's really a bit image, you can look at some code in the R3 server: server/ddx/mfb/mfbclip.c, for converting a bitmap to a YX-banded region. If you have a complex polygonal outline, you can use XPolygonRegion().
NU113738@NDSUVM1.BITNET (07/25/89)
If you need an algorithm to determine if an area is enclosed and return the edge points, what you might want to do is dig up a flood fill algorithm and just do a flood fill somewhere in memory and not on the image. Remove the statements that would perform the actual fill in of pixels and just keep track in memory. If you find a good algorithm, it should be fairly quick, since the you wouldn't have to write to the display memory. If you want me to send you some algorithms that I've collected from others for flood fills, mail me. I couldn't directly replay via the news system. Jeff Bakke NU113738@NDSUVM1.BITNET