2
\$\begingroup\$

Preface

I've spent some time recently looking into methods to detect complete "shapes" in a 2D grid. Cycle detection works well for this - you iterate valid points and if you reach a point you've already been to, a "cycle" exists.

However, trouble arises when you have multiple, connected shapes. Think of a house - you have multiple rooms which are usually discrete shapes inside of the overall house. I needed cycle detection that can see them all - individual room boundaries, and the overall house boundary.

Unfortunately, I couldn't find any existing examples of how to do this so I've brainstormed and come up with the following.

What the code does

The TL;DR is it follows the edges but clones 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 does work given the examples I've thrown at it.

Example Use

// Mock tile map, with a "two-room house" (1s are walls, 0 is empty space)
var map = new int[][] {
    new int[] {0, 0, 0, 0, 0},
    new int[] {1, 1, 1, 1, 1},
    new int[] {1, 0, 1, 0, 1},
    new int[] {1, 1, 1, 1, 1},
    new int[] {0, 0, 0, 0, 0}
};

// Call the cycle detection class with a starting point,
// custom function to validate the cell contents
var d = new CycleDetection(new Point(1, 0), (p) => {
    // Index sanity check
    if (p.x >= 0 && p.x < map.Length && p.y >= 0 && p.y < map[p.x].Length) {
        return map[p.x][p.y] == 1;
    }

    return false;
});

// Quick debug of the final cycles found
foreach (var cycle in d.Cycles) {
    Console.WriteLine("final cycle: " + cycle);
}

right square: 
    {3,2} -> {3,3} -> {3,4} -> 
    {2,4} -> {1,4} -> {1,3} -> 
    {1,2} -> {2,2} -> {3,2}

whole shape:
    {1,0} -> {2,0} -> {3,0} ->
    {3,1} -> {3,2} -> {3,3} ->
    {3,4} -> {2,4} -> {1,4} ->
    {1,3} -> {1,2} -> {1,1} ->
    {1,0}

left square:
    {1,0} -> {2,0} -> {3,0} ->
    {3,1} -> {3,2} -> {2,2} ->
    {1,2} -> {1,1} -> {1,0}

Problems

  1. 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.

  2. There's 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.

The CycleDetection class:

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);
            }
        }
    }
}

The Cycle class:

public sealed class Cycle : IEquatable<Cycle> {
    public readonly ReadOnlyCollection<Point> Points;

    public Cycle(IList<Point> points) {
        this.Points = new ReadOnlyCollection<Point>(points);
    }

    public bool Equals(Cycle c) {
        foreach (var p in Points) {
            if (!c.Points.Contains(p)) {
                return false;
            }
        }

        return true;
    }

    public override int GetHashCode() {
        int hash = 17;
        foreach (var p in Points) {
            hash += p.GetHashCode();
        }

        return hash;
    }

    public override string ToString() {
        StringBuilder result = new StringBuilder();

        for (var i = 0; i < Points.Count; i++) {
            result.Append(Points[i].ToString());

            if (i != Points.Count - 1) {
                result.Append(" -> ");
            }
        }

        return result.ToString();
    }
}

The Point class (note: I use my own because this is for a Unity project and the existing C# Point classes aren't available)

public class Point : IEquatable<Point> {
    public readonly int x;
    public readonly int y;

    public static Point operator +(Point a, Point b) {
        return new Point(a.x + b.x, a.y + b.y);
    }

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public double Distance(Point end) {
        return Math.Pow(x - end.x, 2) + Math.Pow(y - end.y, 2);
    }

    public bool Equals(Point p) {
        return p.x == x && p.y == y;
    }

    public Point Inverse() {
        return new Point(x * -1, y * -1);
    }

    public override int GetHashCode() {
        int hash = 13;
        hash = (hash * 7) + x;
        hash = (hash * 7) + y;

        return hash;
    }

    public override string ToString() {
        var result = new StringBuilder();

        result.Append("{");
        result.Append(x);
        result.Append(",");
        result.Append(y);
        result.Append("}");

        return result.ToString();
    }
}
\$\endgroup\$
  • \$\begingroup\$ You follow the edges, this means the 1s. Wouldn't it be easier to do it the other way around and find the 0s and then detect their boundaries? \$\endgroup\$ – t3chb0t Jul 12 '17 at 4:27
  • \$\begingroup\$ @t3chb0t Maybe with the provided example, but that won't scale. In my real use-case I'll have a procedurally generated 2D tile map, so effectively infinite "zeros" but only a limit set of "ones". \$\endgroup\$ – helion3 Jul 12 '17 at 5:04
1
\$\begingroup\$

Let us begin with @t3chb0t comment

You follow the edges, this means the 1s. Wouldn't it be easier to do it the other way around and find the 0s and then detect their boundaries?

which would be a good advice but you answered

@t3chb0t Maybe with the provided example, but that won't scale. In my real use-case I'll have a procedurally generated 2D tile map, so effectively infinite "zeros" but only a limit set of "ones".

So what about making the best out of it ? Just start with a "default" Shape detection where you are only interested in finding the overall shape. Given your input

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

would result in the output of

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

and then using @t3chb0t advice split this into the left and right shape.

That beeing said, let's focus on the code in question.....

Point

  • I would expect this to be a struct just like the System.Drawing.Point.
  • It's immutable which is good
  • bool Equals(Point p) here you have a potentially problem. Assume the passed in Point p is null then this method will blow in your face. Either change the class to a struct or add at the beginning of the method if (p == null) { return false; }.

  • Distance(Point end) I would rename the methodparameter to other because maybe you will pass a start instead of an end. If this method is used a lot, you should consider to remove the use of Math.Pow() like so

    public double Distance(Point other)
    {
        int distanceX = x - other.x;
        int distanceY = y - other.y;
    
        return distanceX * distanceX + distanceY * distanceY;
    }  
    

    This will be faster.

  • Point Inverse() although the compiler maybe will optimize this anyway, a much simpler version would be

    public Point Inverse()
    {
        return new Point(-x, -y);
    }   
    
  • override string ToString() here you should tale advantage of the fluent style of the StringBuilder. The Append() method is returning its StringBuilder so you could rewrite it like so

    public override string ToString()
    {
        var result = new StringBuilder();
    
        result.Append("{")
              .Append(x)
              .Append(",")
              .Append(y)
              .Append("}");
    
        return result.ToString();
    }  
    

    But because there are only 5 "strings" to concat, I would just go with a simple string.Format() although it looks a little less readable like so

    return string.Format("{{{0},{1}}}", x, y);
    

Cycle

  • Its sealed which is a good thing if you don't want to inherit from it.
  • override string ToString() could be simplified by using string.Join() like so

    return string.Join(" -> ", Points);
    
\$\endgroup\$
  • \$\begingroup\$ return string.Format("{{{0},{1}}}", x, y); can be replaced with return $"{{{x}}},{{{y}}}"; as an expression based body: public override string ToString() => $"{{{x}}},{{{y}}}"; \$\endgroup\$ – downrep_nation Jul 12 '17 at 6:19
  • \$\begingroup\$ correct, but since I am still < C# 6 I am just used to string.Format \$\endgroup\$ – Heslacher Jul 12 '17 at 6:21
  • 1
    \$\begingroup\$ ;) get the new compiler then! its beautiful and still compiles to the same .NET version \$\endgroup\$ – downrep_nation Jul 12 '17 at 6:22
  • \$\begingroup\$ @Heslacher Thanks for input! Several of these changes I'll make! I'm unclear how walking the zeros is better. In order to find the overall shape like you suggest, I need cycle detection, but in order to know which path is truly the "exterior wall" I have to walk all paths and pick the longest. That's literally what I do now and it gives me the info I want. It's also more efficient. Given a square 10 tiles long, that's walking just under 40 "wall" tiles. If I also look at the interior zeros, I'd walk 64 extra tiles. That's roughly 150% more tiles to look at. \$\endgroup\$ – helion3 Jul 12 '17 at 15:19
  • \$\begingroup\$ Also, with string.Join(" -> ", Points);, it can't quite be that simple since Points isn't a string[]. I could iterate it and make a string array, but at that point it feels less beneficial over what I have. \$\endgroup\$ – helion3 Jul 12 '17 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.