c# - GroupByを使用して、重複する範囲で集合を分割します

Question

Rectangleコーナーで領域を定義するクラスについて考えてみます。

public class Rectangle {
    public int X1 { get; set; }
    public int Y1 { get; set; }
    public int X2 { get; set; }
    public int Y2 { get; set; }
}

共通の領域があれば2つのRectangleオブジェクトと言えます。ロジックOverlapを実装する簡単な方法は次のとおりです。Overlap

public bool Overlaps(Rectangle other) {
    return (this.X1 < other.X2 && this.X2 > other.X1 &&
        this.Y1 < other.Y2 && this.Y2 > other.Y1);
}

次に、オブジェクトのセットをRectangle重なり合う長方形のグループに分割します。欠点は、グループ内の一部の長方形が、他の重なり合う長方形を共有している限り、同じグループ内の他の長方形と必ずしも重ならない場合があることです。結果は常に明確に定義されていますが、長方形から最終的な重複グループへの直接マッピングはありません。

GroupBy重なり合う長方形のグループを構築するために使用できるはずだと直感的に思えます。ただし、長方形が同じグループに属するかどうかを定義する「キー」はありません。重要なのは、それらが重なっている場合です。GroupByこの問題は、すべての適切なグループが結合されるまで再帰的にグループ化することを意味する場合でも、を使用して解決できますか？

Answer 1

いいえ、GroupBy1つのインスタンスと1つのインスタンスのみを確認することで判別できるプロパティが必要です。

ただし、比較的簡単な解決策があります。Disjoint-SetData Structure（これは、栄光のリンクリストより少し多い）とそれに関連するunionアルゴリズムを使用できます。アルゴリズム全体は数十行でコード化でき、理解とデバッグは比較的簡単です。

長方形に連番を付け、長方形の各ペアに対して交差アルゴリズムを実行します。オーバーラップを検出したら、対応する互いに素な集合構造に対して集合和集合を実行します。完了すると、各メンバーはそのセットの「ルート」番号を指します。これらのルート番号を使用して、LINQのリストでグループ化できます。

Answer 2

誰かが実際の実装を探す場合に備えて。長方形用ではなく、時間範囲用です。DisjointSetの実装は、 http：//www.mathblog.dk/disjoint-set-data-structure/から取得されます。

public class Range {
    public DateTime Start { get; set; }
    public DateTime Stop { get; set; }
    public int Parent { get; set; }

    public Range(DateTime start, DateTime stop)
    {
        Start = start;
        Stop = stop;
    }
}

void Main()
{
    List<Range> ranges = new List<Range>();
    ranges.Add(new Range(new DateTime(2019, 10, 1), new DateTime(2019, 10, 2)));
    ranges.Add(new Range(new DateTime(2019, 10, 2), new DateTime(2019, 10, 3)));
    ranges.Add(new Range(new DateTime(2019, 10, 1), new DateTime(2019, 10, 3)));
    ranges.Add(new Range(new DateTime(2019, 10, 4), new DateTime(2019, 10, 5)));
    ranges.Add(new Range(new DateTime(2019, 10, 6), new DateTime(2019, 10, 8)));
    ranges.Add(new Range(new DateTime(2019, 10, 5), new DateTime(2019, 10, 7)));
    ranges.Add(new Range(new DateTime(2019, 10, 9), new DateTime(2019, 10, 9)));


    var set = new DisjointSet(ranges.Count());
    var IsOverlaping = new Func<Range, Range, bool>((a, b) => a.Start < b.Stop && b.Start < a.Stop  );

    for (var i = 0; i < ranges.Count; i++)
    {
        for (var j = 0; j < ranges.Count; j++)
        {
            if (IsOverlaping(ranges[i], ranges[j]))
            {
                set.Union(i,j);
            }
        }
    }


    for (int i = 0; i < set.Count; i++)
    {
        ranges[i].Parent = set.Parent[i];
    }
    ranges.GroupBy(x=> x.Parent);

}

/// <summary>
/// A Union-Find/Disjoint-Set data structure.
/// </summary>
public class DisjointSet {

    /// <summary>
    /// The number of elements in the universe.
    /// </summary>
    public int Count { get; private set; }

    /// <summary>
    /// The parent of each element in the universe.
    /// </summary>
    public int[] Parent;

    /// <summary>
    /// The rank of each element in the universe.
    /// </summary>
    private int[] Rank;

    /// <summary>
    /// The size of each set.
    /// </summary>
    private int[] SizeOfSet;

    /// <summary>
    /// The number of disjoint sets.
    /// </summary>
    public int SetCount { get; private set; }

    /// <summary>
    /// Initializes a new Disjoint-Set data structure, with the specified amount of elements in the universe.
    /// </summary>
    /// <param name='count'>
    /// The number of elements in the universe.
    /// </param>
    public DisjointSet(int count) {
        this.Count = count;
        this.SetCount = count;
        this.Parent = new int[this.Count];
        this.Rank = new int[this.Count];
        this.SizeOfSet = new int[this.Count];

        for (int i = 0; i < this.Count; i++) {
            this.Parent[i] = i;
            this.Rank[i] = 0;
            this.SizeOfSet[i] = 1;
        }
    }

    /// <summary>
    /// Find the parent of the specified element.
    /// </summary>
    /// <param name='i'>
    /// The specified element.
    /// </param>
    /// <remarks>
    /// All elements with the same parent are in the same set.
    /// </remarks>
    public int Find(int i) {
        if (this.Parent[i] == i) {
            return i;
        } else {
            // Recursively find the real parent of i, and then cache it for later lookups.
            this.Parent[i] = this.Find(this.Parent[i]);
            return this.Parent[i];
        }
    }

    /// <summary>
    /// Unite the sets that the specified elements belong to.
    /// </summary>
    /// <param name='i'>
    /// The first element.
    /// </param>
    /// <param name='j'>
    /// The second element.
    /// </param>
    public void Union(int i, int j)
    {

        // Find the representatives (or the root nodes) for the set that includes i
        int irep = this.Find(i),
            // And do the same for the set that includes j
            jrep = this.Find(j),
            // Get the rank of i's tree
            irank = this.Rank[irep],
            // Get the rank of j's tree
            jrank = this.Rank[jrep];

        // Elements are in the same set, no need to unite anything.
        if (irep == jrep)
            return;

        this.SetCount--;

        // If i's rank is less than j's rank
        if (irank < jrank)
        {

            // Then move i under j
            this.Parent[irep] = jrep;
            this.SizeOfSet[jrep] += this.SizeOfSet[irep];

        } // Else if j's rank is less than i's rank
        else if (jrank < irank)
        {

            // Then move j under i
            this.Parent[jrep] = irep;
            this.SizeOfSet[irep] += this.SizeOfSet[jrep];

        } // Else if their ranks are the same
        else
        {

            // Then move i under j (doesn't matter which one goes where)
            this.Parent[irep] = jrep;
            this.SizeOfSet[jrep] += this.SizeOfSet[irep];

            // And increment the the result tree's rank by 1
            this.Rank[jrep]++;
        }
    }

    /// <summary>
    /// Return the element count of the set that the specified elements belong to.
    /// </summary>
    /// <param name='i'>
    /// The element.
    /// </param>
    public int SetSize(int i)
    {
        return this.SizeOfSet[this.Find(i)];
    }
}

結果：