Topological Sorting, finding dependencies faster

I am working on a graph problem for months now and I am at a point where I am looking for new input from others.

I spend hours in the library and hit the books. I am pretty confident that I found a solution but maybe someone here can give me a new perspective.

Problem:

I have a 2d plane and rectangles on it. Rectangles can overlap each other and I have to find an order of these rectangles. To visualize imagine windows on your screen and you have to find an order so that it looks right.

To give you a picture of it this may be one output:

img - 1st option

Given:

A function that decides whether two rectangles overlap each other
```
public bool overlap(Rect a, Rect b) {...}
```

A function that given 2 rectangles overlap, decides which is has to be drawn first

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

Rectangle entities with
```
int x,y,width,height
```
Screen width and height
```
int screen.width, int screen.height
```

runtime complexity of these two functions can be neglected for the solution of this problem.

The problem can be abstracted to a dependency graph in which I want to find a correct evaluation order. The rectangles are nodes and the isBefore relation specifies arcs between the nodes. The graph can have multiple connected components as shown in the pictures. So just throwing Sort over all nodes will not do. Note: compare avoids circular dependencies, so the graph will remain acyclic. So the good news is : and order actually exists, yayy!

Now here comes the hard part:

How do I find the dependencies as fast as possible in order to build the graph and run a topological sorting algorithm on it.

The most naive and worst way to do it is to just execute compare for each object on each object thus ending up with O(n²) complexity. But this is just not acceptable here since I may have thousands of these rectangles on the screen.

So how do I minimize the number of nodes I have to compare a node with in oder to find all dependencies?

Now here is my solution. Maybe you should read this after finding something yourself in oder to avoid to be biased.

First of all the problem can be simplified by taking away 1 dimension. The problems will still be isomorphic but much easier to understand, at least for me. So let's just take lines(rectangles) on a big line(screen). A line has a position and a length. Lines that overlap build a connected component.

img - overlapping areas marked red

Since we have a finite amount of lines we can find the smallest line of our set of lines in O(n).
In order for 2 lines to overlap their maximum distance is just the length of our smallest line. Anything above can't overlap with us.
We divide the screen by the size of the smallest line and end up with discrete chunks. We create a HashMap and a bucket for each chunk. We can now sort a line into these buckets.
we run over the set again O(n) and can decide very easy in which buckets we have to put our line. position % smallest.length = i and (position + length) % smallest.length = j will give the indicies of our HashMap. We sort the line into our HashMap from bucket[i] to bucket[j].
We have now minimized the set of lines we have to compare a line with in order to find all its dependencies. After doing this for all lines we only have to compare a line with all other lines in bucket[i-1] to bucket[j+1]. Any other line would be fo far away from us to overlap anyways. The modulo operation is efficent. The additional memory for the buckets shouldn't be very much.

This is the best I came up with. Maybe someone here has a better solution.

Solution

Some observations:

dividing screen by size of smallest line would make the algorithm very unpredictable and is not even necessary. You can use any size of bucket and the algorithm would work.
inspecting bucket[i-1] to bucket[j+1] is not necessary, bucket[i] to bucket[j] is enough
Let A and B be rectangles, B is not wider than A. Then part of left or right edge of B lies on A or those rectangles do not overlap (will be used later).

So the algorithm I made:

For every rectangle calculate ranges of buckets it belongs to (bucketXFrom, bucketXTo, bucketYFrom, bucketYTo). This is class RectangleInBucket.
Sort them by (bucketXTo - bucketXFrom). As there are not so many buckets, it is basically one step radix sort.
For every rectangle, starting from those with smallest width, scan all buckets it belongs to. If there are rectangles, compare to them and save relations where exist. Save rectagle into buckets under left and right edge.

I made total number of buckets equal to number of rectangles, it seems to work best.

It is usually faster than naive algorithm, but not as much as one could expect. As rectagles can (and do) belong to many buckets, one relation is reexamined many times. This increases number of steps. Moreover it uses not so cheap structures for this deduplication. But number of compare calls is reduced easily by several folds. It pays off even when this call is dirt cheap and the difference increases when the compare fuction is not trivial. And finally the code:

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