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:
- For the current valid point:
- add it to a "visited" list
- look for any valid neighbors (except for last point I visited, to avoid infinite loops)
- For each valid neighbor:
- clone the list of points which is our "trail" to this new point
- 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
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 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();
}
}
1s. Wouldn't it be easier to do it the other way around and find the0s and then detect their boundaries? \$\endgroup\$