Find closed loops between a series of connected points

Question

So I've been trying work out how to approach what i initially was a simple problem - turns out i'm an idiot and have no idea what i'm doing.

Firstly my data structure is like this:

public class Points{
    public List<Points> connectsTo = new List<Points>();
    public Vector3 position;
}
// main script 
List<Points> allWorldPoints = new List<Points>();

The idea is the points are connectors that create walls and from that i need to find rooms. Here is an image of what i am trying to achieve:

Rooms are not necessarily square/rectangle shape, they could L or T shaped etc.

The problem is i don't know the logic of how to approach working this out, so am looking for advice as the logic is really confusing me.

Answer 1

1. Start at any point.
2. Traverse connected points till you get back the starting point. Select from all possible paths found the one with minimum number of points; you've just found a room.
3. Store the newly found room.
4. Take a new starting point that does not belong to any found room and repeat 2.
5. End when there is no points left not assigned to a room or no more closed paths are found.

By the way, your class should be named Point not Points.

UPDATE: I've added a working example.

OK, first let's get the necessary infrastructure. I'll implement a couple of classes: Point, Room and ImmutableStack<T> (the latter is used to make traversing paths easier):

public class ImmutableStack<T> : IEnumerable<T>
{
    private readonly T head;
    private readonly ImmutableStack<T> tail;
    public int Count { get; }
    public static readonly ImmutableStack<T> Empty = new ImmutableStack<T>();

    private ImmutableStack()
    {
        head = default(T);
        tail = null;
        Count = 0;
    }

    private ImmutableStack(T head, ImmutableStack<T> tail)
    {
        Debug.Assert(tail != null);
        this.head = head;
        this.tail = tail;
        Count = tail.Count + 1;
    }

    public ImmutableStack<T> Push(T item) => new ImmutableStack<T>(item, this);
    public T Peek()
    {
        if (this == Empty)
            throw new InvalidOperationException("Can not peek an empty stack.");

        return head;
    }

    public ImmutableStack<T> Pop()
    {
        if (this == Empty)
            throw new InvalidOperationException("Can not pop an empty stack.");

        return tail;
    }

    public IEnumerator<T> GetEnumerator()
    {
        var current = this;

        while (current != Empty)
        {
            yield return current.Peek();
            current = current.tail;
        }
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
    public override string ToString() => string.Join(" -> ", this);
}

public class Point: IEquatable<Point>
{
    private readonly List<Point> connectedPoints;
    public int X { get; }
    public int Y { get; }
    public IEnumerable<Point> ConnectedPoints => connectedPoints.Select(p => p);

    public Point(int x, int y)
    {
        X = x;
        Y = y;
        connectedPoints = new List<Point>();
    }

    public void ConnectWith(Point p)
    {
        Debug.Assert(p != null);
        Debug.Assert(!Equals(p));

        if (!connectedPoints.Contains(p))
        {
            connectedPoints.Add(p);
            p.connectedPoints.Add(this);
        }
    }

    public bool Equals(Point p)
    {
        if (ReferenceEquals(p, null))
            return false;

        return X == p.X && Y == p.Y;
    }

    public override bool Equals(object obj) => this.Equals(obj as Point);
    public override int GetHashCode() => X ^ Y;
    public override string ToString() => $"[{X}, {Y}]";
}

public class Room
{
    public IEnumerable<Point> Points { get; }
    public Room(IEnumerable<Point> points)
    {
        Points = points;
    }
}

Ok, now we just implement the steps enumerated above:

public static IEnumerable<Room> GetRooms(this IEnumerable<Point> points)
{
    if (points.Count() < 3) //need at least 3 points to build a room
        yield break;

    var startCandidates = points;

    while (startCandidates.Any())
    {
        var start = startCandidates.First();
        var potentialRooms = GetPaths(start, start, ImmutableStack<Point>.Empty).OrderBy(p => p.Count);

        if (potentialRooms.Any())
        {
            var roomPath = potentialRooms.First();
            yield return new Room(roomPath);
            startCandidates = startCandidates.Except(roomPath);
        }
        else
        {
            startCandidates = startCandidates.Except(new[] { start });
        }
    }
}

private static IEnumerable<ImmutableStack<Point>> GetPaths(Point start, Point current, ImmutableStack<Point> path)
{
    if (current == start &&
        path.Count > 2) //discard backtracking
    {
        yield return path;
    }
    else if (path.Contains(current))
    {
        yield break;
    }
    else
    {
        var newPath = path.Push(current);

        foreach (var point in current.ConnectedPoints)
        {
            foreach (var p in GetPaths(start, point, newPath))
            {
                yield return p;
            }
        }
    }
}

And sure enough, if we test your geometry:

    public static void Main(string[] args)
    {
        var p1 = new Point(0, 0);
        var p2 = new Point(0, 1);
        var p3 = new Point(0, 2);
        var p4 = new Point(1, 2);
        var p5 = new Point(1, 1);
        var p6 = new Point(1, 0);
        var p7 = new Point(2, 0);
        var p8 = new Point(2, 1);
        p1.ConnectWith(p2);
        p2.ConnectWith(p3);
        p3.ConnectWith(p4);
        p4.ConnectWith(p5);
        p5.ConnectWith(p6);
        p6.ConnectWith(p1);
        p6.ConnectWith(p7);
        p7.ConnectWith(p8);
        p8.ConnectWith(p5);
        var rooms = new[] { p1, p2, p3, p4, p5, p6, p7, p8 }.GetRooms();
    }

We get the expected two rooms.

Note that the algorithm can be made more performant changing the ImmtuableStack to an ImmutableHashSet for instance.