3

考虑一个Rectangle通过角定义区域的类：

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

可以说，如果两个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，即使这意味着递归地分组直到所有适当的组被组合？

4

2 回答 2

4

不，GroupBy需要一个可以通过查看一个实例来确定的属性，并且仅一个实例。

但是，有一个相对简单的解决方案：您可以使用不相交集数据结构（它比美化的链表多一点）及其相关union算法。整个算法只需几十行代码，理解和调试相对简单。

给你的矩形序列号，并在每对矩形上运行你的交集算法。当您检测到重叠时，对相应的不相交集合结构执行集合并集。完成后，每个成员将指向其集合的“根”号。您可以使用这些根号按 LINQ 中的列表进行分组。

于 2013-03-02T03:31:53.130 回答
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)];
    }
}

结果：

在此处输入图像描述

于 2019-10-17T07:17:21.107 回答