找到一系列連接點之間的閉環

Question

所以我一直在努力解決如何處理我最初的一個簡單問題 - 事實證明，我是一個白癡，不知道我在做什麼。

首先我的數據結構是這樣的：

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

的想法是點是創造牆壁的連接器和從我需要找到房間。這裏是什麼，我想實現的圖像：

房間不一定是正方形/長方形形狀，它們可以L或T字型等

的問題是我不知道如何解決這個問題的邏輯，所以我正在尋找建議，因爲邏輯真的讓我感到困惑。

Answer 1

1. 從任何點開始。
2. 遍歷連接點，直到你回到起點。從所有可能的路徑中選擇一個點數最少的路徑;你剛剛找到一個房間。
3. 存放新找到的房間。
4. 創建一個新的起點，它不屬於任何找到的房間並重復2.
5. 當沒有剩餘的點沒有分配給房間或沒有找到閉合的路徑時結束。

順便說一下，你的班級應該被命名爲Point而不是Points。

UPDATE：我已經添加了一個工作示例。好吧，首先讓我們獲得必要的基礎設施。我將實現幾個類：Point，Room和ImmutableStack<T>（後者是用來做運行軌跡，更容易）：

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

好了，現在我們只是執行上面列舉的步驟：

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

當然，如果我們測試幾何：

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

我們得到預期的兩個房間。

請注意，算法可以更高效，例如將ImmtuableStack更改爲ImmutableHashSet。