[comp.windows.x] A fast algorithm to find all closed regions in an image

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