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

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
   

Answer 2

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 3

Coming from a graph-theoretic view of the problem, you can interpret every 0 of your map as a node, neighboring 0s are connected with an edge. It sounds to me like what you want to do is compute the connected components of this graph (and maybe their connectivity by 1 values, to find 'neighboring rooms' of the same structure)

If you only want to compute this information once, a straightforward approach using a union-find data structure should suffice, where you apply union once per edge.

If you want to edit your map dynamically, the best approach based on the graph model would probably be some dynamic data structure that supports split or de-union operations, see for example here or here

Answer 4

You can try a list of points and verify the ones that are linked.

class PointList : List<Point>
{
    /// <summary>
    /// Adds the point to the list and checks for perimeters
    /// </summary>
    /// <param name="point"></param>
    /// <returns>Returns true if it created at least one structure</returns>
    public bool AddAndVerify(Point point)
    {
        this.Add(point);

        bool result = LookForPerimeter(point, point, point);
        Console.WriteLine(result);
        return result;
    }

    private bool LookForPerimeter(Point point, Point last, Point original)
    {
        foreach (Point linked in this.Where(p => 
            (p.X == point.X -1 && p.Y == point.Y)
            || (p.X == point.X + 1 && p.Y == point.Y)
            || (p.X == point.X && p.Y == point.Y - 1)
            || (p.X == point.X && p.Y == point.Y + 1)
        ))
        {
            if (!linked.Equals(last))
            {
                if (linked == original) return true;

                bool subResult = LookForPerimeter(linked, point, original);
                if (subResult) return true;
            }
        }

        return false;
    }
}

This code is intentended as a starting point, it probably has bugs and does not account for perimeters without 0 inside

Example of use:

class Program
{
    static void Main(string[] args)
    {
        PointList list = new PointList();

        list.AddAndVerify(new Point() { X = 0, Y = 0 }); //returns false
        list.AddAndVerify(new Point() { X = 0, Y = 1 }); //returns false
        list.AddAndVerify(new Point() { X = 0, Y = 2 }); //returns false
        list.AddAndVerify(new Point() { X = 1, Y = 2 }); //returns false
        list.AddAndVerify(new Point() { X = 2, Y = 2 }); //returns false
        list.AddAndVerify(new Point() { X = 2, Y = 1 }); //returns false
        list.AddAndVerify(new Point() { X = 2, Y = 0 }); //returns false
        list.AddAndVerify(new Point() { X = 1, Y = 0 }); //returns True
    }
}

Answer 5

I had a similar problem trying to find all circles inside a 2D street map graph (given as a SVG file). As you state I too could not find an algorithm for that.

I found the following solution though.

Assumptions

Grid Layout: Each '1' in the grid is in one of the following states (or an homomorphism of that):

1.   0      2.   0      3.   0      4.   0      5.   0      6.   1
   0 1 0       1 1 0       1 1 0       1 1 1       1 1 1       1 1 1
     0           0           1           0           1           1

But only example 3 to 6 make a sense for a connected wall, as in a connected wall each '1' has at least two '1's in its neighborhood.

• Example 3 indicates a corner. This corner holds at most one structure.
• Example 4 indicates a straight line. It can be the wall of zero, one or two structures.
• Example 5 indicates a t-wall. It can be the wall of zero, one, two or three structures.
• Example 6 indicates a cross-wall. It can be the corner of zero, one, two, three or four structures.

The Algorithm

The idea

Assuming the above, the algorithm works by finding a '1' and doing a depth first search, to mark all connected '1's. The traversed '1's are only marked, if the depth first search arrives at the starting position or at an already marked position.

The implementation

I will post an implementation the next few days for that one.

Answer 6

Re-posting my solution with an explanation and some code.

It took a few days before any answers were posted I tried to find a solution and believe I've found one that works very well for my needs.

Since I always have a starting point, I walk the edges from that point and fork the list of visited points each time the path "branches" off - allowing me to find multiple cycles.

Given a 2D grid with either a 1 or 0 in a cell:

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

Starting from a cell I already know is a 1, I begin my search:

1. For the current valid point:
   1. add it to a "visited" list
   2. look for any valid neighbors (except for last point I visited, to avoid infinite loops)
2. For each valid neighbor:
   1. clone the list of points which is our "trail" to this new point
   2. call step 1 with the neighbor point

Cloning allows each "branch" to become a unique cycle without mixing points.

I haven't run any performance profiling, but it works very well given the examples I've thrown at it.

It's possible to give me two copies of a cycle. For example, if I start in the NW corner, cells to the east and south both have valid paths to follow. They're both treated as new paths and followed, but they're just mirror images of the same cycle. For now, I just prune cycles like these - they have exactly the same points, as long as you ignore their order.

There's also a bit of filtering involved - like for problem #1 and trimming points if the end point matches a visited point that wasn't where we started. I think that's pretty much unavoidable and isn't a big deal but if there was a clean way to avoid that I would. I can't know what "begins" a new cycle until I've found it though, so you know, linear time flow strikes again.

public class CycleDetection {
    // Cache found cycles
    List<Cycle> cycles = new List<Cycle>();

    // Provide public readonly access to our cycle list
    public ReadOnlyCollection<Cycle> Cycles {
        get { return new ReadOnlyCollection<Cycle>(cycles); }
    }

    // Steps/slopes that determine how we iterate grid points
    public Point[] Steps = new Point[] {
        new Point(1, 0),
        new Point(0, 1),
        new Point(-1, 0),
        new Point(0, -1)
    };

    // Cache our starting position
    Point origin;

    // Cache the validation function
    Func<Point, bool> validator;

    public CycleDetection(Point origin, Func<Point, bool> validator) {
        this.origin = origin;
        this.validator = validator;

        this.Scan();
    }

    // Activate a new scan.
    public void Scan() {
        cycles.Clear();

        if (validator(origin)) {
            Scan(new List<Point>(), origin);
        }
    }

    // Add a cycle to our final list.
    // This ensures the cycle doesn't already exist (compares points, ignoring order).
    void AddCycle(Cycle cycle) {
        // Cycles have reached some existing point in the trail, but not necessarily
        // the exact starting point. To filter out "strands" we find the index of
        // the actual starting point and skip points that came before it
        var index = cycle.Points.IndexOf(cycle.Points[cycle.Points.Count - 1]);

        // Make a new object with only the points forming the exact cycle
        // If the end point is the actual starting point, this has no effect.
        cycle = new Cycle(cycle.Points.Skip(index).ToList());

        // Add unless duplicate
        if (!cycles.Contains(cycle)) {
            cycles.Add(cycle);
        }
    }

    // Scan a new point and follow any valid new trails.
    void Scan(List<Point> trail, Point start) {
        // Cycle completed?
        if (trail.Contains(start)) {
            // Add this position as the end point
            trail.Add(start);

            // Add the finished cycle
            AddCycle(new Cycle(trail));

            return;
        }

        trail.Add(start);

        // Look for neighbors
        foreach (var step in Steps) {
            var neighbor = start + step;

            // Make sure the neighbor isn't the last point we were on... that'd be an infinite loop
            if (trail.Count >= 2 && neighbor.Equals(trail[trail.Count - 2])) {
                continue;
            }

            // If neighbor is new and matches
            if (validator(neighbor)) {
                // Continue the trail with the neighbor
                Scan(new List<Point>(trail), neighbor);
            }
        }
    }
}

I've posted the full source here: https://github.com/OutpostOmni/OmniGraph (includes some unrelated graph utils as well)