CycleDetection.cs

// Detects cycles/shapes in a 2D grid.
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 the validation function
    Func<Point, bool> validator;

    // Initializes a new instance of the <see cref="T:OmniGraph.CycleDetection"/> class.
    public CycleDetection(Point origin, Func<Point, bool> validator) {
        this.validator = validator;

        this.Scan(origin);
    }

    // Activate a new scan.
    public void Scan(Point origin) {
        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);
            }
        }
    }
}