拓扑排序，更快找到依赖关系

Question

几个月来我一直在研究图形问题，现在我正在寻找其他人的新意见。

我在图书馆里呆了几个小时，看书。我非常有信心我找到了解决方案，但也许这里有人可以给我一个新的视角。

问题：

我有一个二维平面和上面的矩形。矩形可以相互重叠，我必须找到这些矩形的顺序。要在您的屏幕上想象 windows，您必须找到一个顺序，使其看起来正确。

给你一张图片，这可能是一个输出：

给定：

判断两个矩形是否重叠的函数

public bool overlap(Rect a, Rect b) {...}

给定 2 个矩形重叠的函数，决定先绘制哪个矩形

//returns [1 => a before b, -1 => b before a, 0 => a & b have no "before (<)" relation]
public int compare(Rect a, Rect b) {...}

具有
的矩形实体
```
int x,y,width,height
```
屏幕宽度和高度
```
int screen.width, int screen.height
```

运行这两个函数的时间复杂度对于本题的求解可以忽略

这个问题可以抽象为一个依赖图，我想在其中找到正确的评估顺序。矩形是 nodes 并且 isBefore 关系指定节点之间的 arcs。该图可以有多个连接的组件，如图所示。所以仅仅将 Sort 扔到所有节点上是不行的。注意：compare避免循环依赖，因此图形将保持非循环。所以好消息是：订单确实存在，耶！

难点来了:

如何尽可能快地找到依赖关系以便构建图形和运行其上的拓扑排序算法。

最天真和最糟糕的方法是只对每个对象执行 compare ，从而以 O(n²) 复杂度结束。但这在这里是不可接受的，因为我的屏幕上可能有数千个这样的矩形。

那么，如何最大限度地减少我必须与节点进行比较以查找所有依赖项的节点数？

现在这是我的解决方案。也许你应该在自己找到一些东西后阅读这篇文章，以免产生偏见。

首先问题可以通过去掉一维来简化。这些问题仍然是同构的，但更容易理解，至少对我而言。所以让我们在大线（屏幕）上取行（矩形）。一条线有 position 和 length。重叠的线构成一个连通分量。

由于我们有有限数量的线，我们可以找到最小的线我们在 O(n).
为了让2条线重叠，它们的最大距离就是我们最小线的长度。以上任何内容都不能与我们重叠。
我们将屏幕除以最小行的大小，最后得到离散的块。我们为每个块创建一个 HashMap 和一个桶。我们现在可以将一行排序到这些桶中。
我们运行再次 O(n) 并且可以很容易地决定我们必须把我们的线放在哪个桶里。 position % smallest.length = i 和 (position + length) % smallest.length = j 将给出我们的 HashMap 的索引。我们将行从 bucket[i] 到 bucket[j].
我们现在已经最小化了为了找到它的所有依赖项而必须与之比较的行集。对所有行执行此操作后，我们只需将行与 bucket[i-1] 至 bucket[j+1] 中的所有其他行进行比较。无论如何，任何其他线都会离我们很远而重叠。模运算是有效的。桶的额外内存不应该很多。

这是我想到的最好的。也许这里有人有更好的解决方案。

Answer 1

一些观察：

按最小行的大小划分屏幕会使算法变得非常不可预测，甚至没有必要。您可以使用任何大小的桶，该算法将起作用。
不需要检查 bucket[i-1] 到 bucket[j+1]，bucket[i] 到 bucket[j] 就足够了
设A和B为矩形，B不比A宽，则B的左边缘或右边缘的一部分位于A上或这些矩形不重叠（稍后会用到）。

所以我做的算法：

对于每个矩形计算它所属的桶的范围 (bucketXFrom, bucketXTo, bucketYFrom, bucketYTo)。这是 class RectangleInBucket。
按 (bucketXTo - bucketXFrom) 对它们进行排序。由于没有那么多桶，基本上是一步基数排序。
对于每个矩形，从宽度最小的矩形开始，扫描它所属的所有桶。如果有矩形，则与它们进行比较并在存在的地方保存关系。将矩形保存到左右边缘下的桶中。

我让桶的总数等于矩形的数量，这似乎效果最好。

它通常比朴素算法快，但不如人们预期的那么快。由于矩形可以（并且确实）属于多个桶，所以一个关系会被多次重新检查。这增加了步骤数。此外，它使用不太便宜的结构来进行重复数据删除。但是 compare 调用的次数很容易减少几倍。即使这个调用非常便宜并且当 compare 函数不是微不足道的时候差异会增加，它也会得到回报。最后是代码：

   public class Rectangle
    {
        public int x;
        public int y;
        public int width;
        public int height;
    }

    /// <summary>
    /// Creates array of objects
    /// </summary>
    protected T[] InitializeArray<T>(int length) where T : new()
    {
        T[] array = new T[length];
        for (int i = 0; i < length; ++i)
        {
            array[i] = new T();
        }

        return array;
    }

    /// <summary>
    /// Creates array of objects
    /// </summary>
    protected T[,] InitializeArray<T>(int length, int width) where T : new()
    {
        T[,] array = new T[length, width];
        for (int i = 0; i < length; ++i)
        {
            for (int j = 0; j < width; ++j)
            {
                array[i, j] = new T();
            }
        }

        return array;
    }

    protected class RectangleInBucket
    {
        public readonly Rectangle Rect;
        public readonly int RecNo;
        public readonly int bucketXFrom;
        public readonly int bucketXTo;
        public readonly int bucketYFrom;
        public readonly int bucketYTo;
        public RectangleInBucket(Rectangle rectangle, int recNo, int bucketSizeX, int bucketSizeY)
        {
            Rect = rectangle;
            RecNo = recNo;// arbitrary number unique for this rectangle
            bucketXFrom = Rect.x / bucketSizeX;
            bucketXTo = (Rect.x + Rect.width) / bucketSizeX;
            bucketYFrom = Rect.y / bucketSizeY;
            bucketYTo = (Rect.y + Rect.height) / bucketSizeY;
        }
    }

    /// <summary>
    /// Evaluates rectagle wrapped in RectangleInBucket object against all rectangles in bucket.
    /// Saves result into tmpResult.
    /// </summary>
    protected void processBucket(Dictionary<long, int> tmpResult, List<RectangleInBucket> bucket, RectangleInBucket rib)
    {
        foreach (RectangleInBucket bucketRect in bucket)
        {
            if (bucketRect.RecNo < rib.RecNo)
            {
                long actualCouple = bucketRect.RecNo + (((long)rib.RecNo) << 32);
                if (tmpResult.ContainsKey(actualCouple)) { continue; }
                tmpResult[actualCouple] = overlap(bucketRect.Rect, rib.Rect) ? compare(bucketRect.Rect, rib.Rect) : 0;
            }
            else
            {
                long actualCouple = rib.RecNo + (((long)bucketRect.RecNo) << 32);
                if (tmpResult.ContainsKey(actualCouple)) { continue; }
                tmpResult[actualCouple] = overlap(rib.Rect, bucketRect.Rect) ? compare(rib.Rect, bucketRect.Rect) : 0;
            }
        }
    }

    /// <summary>
    /// Calculates all couples of rectangles where result of "compare" function is not zero
    /// </summary>
    /// <param name="ra">Array of all rectangles</param>
    /// <param name="screenWidth"></param>
    /// <param name="screenHeight"></param>
    /// <returns>Couple of rectangles and value of "compare" function</returns>
    public List<Tuple<Rectangle, Rectangle, int>> GetRelations(Rectangle[] ra, int screenWidth, int screenHeight)
    {
        Dictionary<long, int> tmpResult = new Dictionary<long, int>();
        // the key represents couple of rectangles. As index of one rectangle is int,
        // two indexes can be stored in long. First index must be smaller than second,
        // this ensures couple can be inserted only once. Value of dictionary is result 
        // of "compare" function for this couple.

        int bucketSizeX = Math.Max(1, (int)Math.Sqrt(screenWidth * screenHeight / ra.Length));
        int bucketSizeY = bucketSizeX;

        int bucketsNoX = (screenWidth + bucketSizeX - 1) / bucketSizeX;
        int bucketsNoY = (screenHeight + bucketSizeY - 1) / bucketSizeY;

        List<RectangleInBucket>[,] buckets = InitializeArray<List<RectangleInBucket>>(bucketsNoX, bucketsNoY);
        List<RectangleInBucket>[] sortedRects = InitializeArray<List<RectangleInBucket>>(bucketsNoX);

        for (int i = 0; i < ra.Length; ++i)
        {
            RectangleInBucket rib = new RectangleInBucket(ra[i], i, bucketSizeX, bucketSizeY);
            sortedRects[rib.bucketXTo - rib.bucketXFrom].Add(rib);// basically radix sort
        }

        foreach (List<RectangleInBucket> sorted in sortedRects) // start with most narrow rectangles
        {
            foreach (RectangleInBucket rib in sorted) // all of one width (measured in buckets)
            {
                for (int x = rib.bucketXFrom; x <= rib.bucketXTo; ++x)
                {
                    for (int y = rib.bucketYFrom; y <= rib.bucketYTo; ++y)
                    {
                        processBucket(tmpResult, buckets[x, y], rib);
                    }
                }

                for (int y = rib.bucketYFrom; y <= rib.bucketYTo; ++y)
                {
                    buckets[rib.bucketXFrom, y].Add(rib); // left edge of rectangle
                    if (rib.bucketXFrom != rib.bucketXTo)
                    {
                        buckets[rib.bucketXTo, y].Add(rib); // right edge of rectangle
                    }
                }
            }
        }

        List<Tuple<Rectangle, Rectangle, int>> result = new List<Tuple<Rectangle, Rectangle, int>>(tmpResult.Count);
        foreach (var t in tmpResult) // transform dictionary into final list
        {
            if (t.Value != 0)
            {
                result.Add(Tuple.Create(ra[(int)t.Key], ra[(int)(t.Key >> 32)], t.Value));
            }
        }

        return result;
    }

拓扑排序，更快找到依赖关系

Topological Sorting, finding dependencies faster

c#

graph-theory

topological-sort

问题：

给定：