Finding all cycles/enclosed shapes in a 2D grid

Question

I have an "infinite" 2D grid and I want to detect closed/complete "structures" - areas of any shape which are enclosed on all sides. However, I need to identify each individual closed circuit - including the larger shape, if any.

In researching this, I've discovered the cycle detection algorithm, but I don't see a clean/efficient way to separate the larger circuit from the smaller ones.

For example given the following two "complete" structures:

0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 1 1
0 1 0 1 0 1
0 1 1 1 1 1

The first is a single cell enclosed by 8 "walls". The cycle detection makes it trivial to detect this.

The second example consists of two copies of example one but they share a wall. There are three separate circuits I care about - the left room, the right room, and the overall structure.

Multiple passes of a cycle algorithm might work, but I'd have to be sure I'm not retracing an already-found shape.

I've also looked at the flood fill algorithm, but it seems like it makes the assumption you already know a point inside the bounded area. With an infinite 2D grid I'd need a size limit to force it to give up if it's not in a valid structure.

Are there solutions I'm missing or have I missed something with my thinking?

I will only do this "check" when a boundary value is added. Using the example above, if I change any 0 -> 1, a new cycle has potentially been created and I'll run the logic. I do not care about identifying separate structures and will always have an origin coordinate.

I've been studying the solutions posted here but they're all based on already knowing which nodes are connected to other nodes. I've already toyed with logic that identifies each individual "line" and I can keep going from there, but it feels redundant.

Answer 1

It is a contours finding problem.

One of possible algorithms is described by Satoshi Suzuki and Keiichi Abe in their paper called Topological Structural Analysis of Digitized Binary Images by Border Following in 1985. And it is not trivial. But you can use OpenCV, it's cv2.findContours() function implements this algorithm.

If you choose to use OpenCV, the solution is easy. You extract contours alongside it's hierarchy. Contours that has at least one child (hole) and their child contours are objects that you are looking for. Example using managed OpenCV wrapper called OpenCvSharp:

byte[,] a = new byte[7, 6]
{
    { 0, 1, 1, 1, 0, 0 },
    { 0, 1, 0, 1, 0, 0 },
    { 0, 1, 1, 1, 0, 0 },
    { 0, 0, 0, 0, 0, 0 },
    { 0, 1, 1, 1, 1, 1 },
    { 0, 1, 0, 1, 0, 1 },
    { 0, 1, 1, 1, 1, 1 }
};
// Clone the matrix if you want to keep original array unmodified.
using (var mat = new MatOfByte(a.GetLength(0), a.GetLength(1), a))
{
    // Turn 1 pixel values into 255.
    Cv2.Threshold(mat, mat, thresh: 0, maxval: 255, type: ThresholdTypes.Binary);
    // Note that in OpenCV Point.X is a matrix column index and Point.Y is a row index.
    Point[][] contours;
    HierarchyIndex[] hierarchy;
    Cv2.FindContours(mat, out contours, out hierarchy, RetrievalModes.CComp, ContourApproximationModes.ApproxNone);
    for (var i = 0; i < contours.Length; ++i)
    {
        var hasHole = hierarchy[i].Child > -1;
        if (hasHole)
        {
            var externalContour = contours[i];
            // Process external contour.
            var holeIndex = hierarchy[i].Child;
            do
            {
                var hole = contours[holeIndex];
                // Process hole.
                holeIndex = hierarchy[holeIndex].Next;
            }
            while (holeIndex > -1);
        }
    }
}

Answer 2

I would do this like this:

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 1 0 1 0 1 0
0 1 1 1 1 1 0
0 0 0 0 0 0 0

1. fill the background with 2

   to determine if you are in background just cast a ray and count consequent zeores. Once you find location where the ray length is bigger then circuit size limit you got your start point.

   [0]0-0-0-0-0-0
    0 1 1 1 1 1 0
    0 1 0 1 0 1 0
    0 1 1 1 1 1 0
    0 0 0 0 0 0 0
   
    2 2 2 2 2 2 2
    2 1 1 1 1 1 2
    2 1 0 1 0 1 2
    2 1 1 1 1 1 2
    2 2 2 2 2 2 2
   

   Do not use unbound recursive flood fills for this !!! because for "infinite" area you will stack overflow. You can limit the recursion level and if reached instead of recursion add point to some que for further processing latter. This usually speeds thing up a lot and limits the stack usage...

2. find first 0

    2 2 2 2 2 2 2
    2 1 1 1 1 1 2
    2 1[0]1 0 1 2
    2 1 1 1 1 1 2
    2 2 2 2 2 2 2
   

3. flood fill it with 3

    2 2 2 2 2 2 2
    2 1 1 1 1 1 2
    2 1 3 1 0 1 2
    2 1 1 1 1 1 2
    2 2 2 2 2 2 2
   

4. select all 1 near 3

   this is your circuit. If you remember the bbox while filling #3 then you need to scan only area enlarged by one cell on each side... Selected cells are your circuit.

    2 2 2 2 2 2 2
    2 * * * 1 1 2
    2 * 3 * 0 1 2
    2 * * * 1 1 2
    2 2 2 2 2 2 2
   

5. flood fill 3 with 2

   this will avoid of usage already processed circuits

    2 2 2 2 2 2 2
    2 1 1 1 1 1 2
    2 1 2 1 0 1 2
    2 1 1 1 1 1 2
    2 2 2 2 2 2 2
   

6. loop #2 while any 0 found

7. change all 2 back to 0

    0 0 0 0 0 0 0
    0 1 1 1 1 1 0
    0 1 0 1 0 1 0
    0 1 1 1 1 1 0
    0 0 0 0 0 0 0