一連の接続点の間にクローズドループを見つける

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とする必要があります。

更新日：実例を追加しました。

いいえ、まずは必要なインフラストラクチャを手に入れましょう。 [OK]を、今、私たちは上に列挙したステップを実装

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

Point、 Roomと ImmutableStack<T>（後者は簡単にパスを横断するために使用される）：私はクラスのカップルを実装します

そして、我々はあなたの幾何学テストする場合は、十分に確認してください：

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に変更することでより効果的にすることができます。