How can I find all chains of intersected rectangles

Question

I have an array of rectangles. Some of them might intersect, forming a pair:

While others might intersect, forming a chain:

And, of course, some of them might be alone.

I want to form a list that will include all chains, pairs and single rectangles. For example, if we have an array of rectangles that looks like that:

I want to get following list:

    { { A, B, C, D, E },
    { F },
    { G },
    { H, J },
    { K, L },
    { M, N, O } }

where A, B, C, D, E, etc. are corresponding Rectangles.

So far I tried forming all possible permutations with this code:

var rectangles = new Rectangle[] { ..., ..., ... }; // my rectangles
var rectanglePermutations = new IEnumerable<IEnumerable<Rectangle>>();
// make all permutations with 2, 3, 4 (and so on) elements
for (var i = 2; i < rectangles.Length; i++)
{
    rectanglePermutations.AddRange(GetPermutations(rectangles, i));
}

IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> items, int count)
{
    var i = 0;
    foreach (var item in items)
    {
        if (count == 1)
        {
            yield return new T[] { item };
        }
        else
        {
            foreach (var result in GetPermutations(items.Skip(i + 1), count - 1))
            {
                yield return new T[] { item }.Concat(result);
            }
        }

        i++;
    }
}

Then I was trying to find if all rectangles inside each enumerable in rectanglePermutations can form a chain:

var result = new List<List<Rectangle>>();
foreach (var permutations in rectanglePermutations)
{
    var chain = new List<Rectangle>(permutations);
    var canFormNewRectangles = true;
    
    do
    {
        var newlyFormedRectanglesCount = 0;
        // get all possible pairs
        var pairs = GetPermutations(chain.Distinct(), 2);
        chain.Clear();
        
        foreach (var pair in pairs)
        {
            // if rectangles in pair intersect
            var union = Rectangle.Union(pair.First(), pair.Last());
            if (union.Width * union.Height > 0)
            {
                // replace them with a new rectangle
                chain.Add(new Rectangle(pair.Min(r => r.Left), pair.Min(r => r.Top), pair.Max(r => r.Right) - pair.Min(r => r.Left), pair.Min(r => r.Top) - pair.Max(r => r.Bottom)));
                newlyFormedRectanglesCount++;
            }
        }
        
        // if we can't make any more new rectangles
        if (newlyFormedRectanglesCount == 0)
        {
            canFormNewRectangles = false;
        }
    }
    while (canFormNewRectangles);
    
    // if all rectangles made a single chain
    if (chain.Count == 1)
    {
        result.Add(permutation.ToList());
    }
}

// add single rectangles to result that are not used in any chains
var usedRectangles = chains.SelectMany(chain => chain).Distinct();
result.AddRange(rectangles.Except(usedRectangles).ToList());

The problem is that code above is ineffective and slow. For example, if we have a 5-rectangle-chain, a 3-rectangle-chain and 2 separate rectangles (10 in total), we'll get 1013 possible permutations from first part of code, and at least 11160 iterations from second part of code (in fact, we'll be getting twice as much for given example). Using that to find only 2 suitable combinations is inefficient. I'm pretty sure there's a better approach and need some help with that.

Answer 1

The first step to solve this should be to figure out what rectangles intersect with each other. I think the fast solution should be an R-Tree, but as long as the number of triangles is limited an exhaustive check should work well enough. To store all the intersections we can use a Microsoft.Collections.Extensions.MultiValueDictionary, another alternative would be a matrix.

var rectangles = new Rectangle[]{...};
var graph = new MultiValueDictionary<int, int>();
for (int i = 0; i < rectangles.Length; i++)
{
    for (int j = i+1; j < rectangles.Length; j++)
    {
        if (rectangles[i].IntersectsWith(rectangles[j]))
        {
            graph.Add(i, j);
            graph.Add(j, i);
        }
    }
}

We can view all the rectangles as a graph, so to figure out all the rectangles connected to one rectangle we need a way to traverse this graph, for example by using depth first iteration. I like to use a generic iterator block for this, but some prefer recursive solutions:

public static IEnumerable<T> IterateDepthFirst<T>(T self, Func<T, IEnumerable<T>> selector, HashSet<T> visited)
{
    var stack = new Stack<T>();
    stack.Push(self);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        if(!visited.Add(current)) continue;
        yield return current;
        foreach (var child in selector(current))
        {
            if (!visited.Contains(child))
            {
                stack.Push(child);
            }
        }
    }
}

The visited set ensures rectangles are only returned once, even if there is loops in the graph. To find all the groups of rectangles we simply need to call this method repetedly:

public static IEnumerable<T[]> Segment<T>(
    IEnumerable<T> nodes,
    Func<T, IEnumerable<T>> selector)
{
    var visited = new HashSet<T>(EqualityComparer<T>.Default);
    foreach (T currentNode in nodes)
    {
        if (!visited.Contains(currentNode))
        {
            yield return IterateDepthFirst(currentNode, selector, visited).ToArray();
        }        
    }
}

Note that we keep the same visited set, so that we do not worry about including a rectangle twice.

This would then be called like

var rectangleGroups = Segment(Enumerable.Range(0, rectangles.Length), i => graph[i]);

Answer 2

One basic approach to get all the "chains" of rectangles (i.e. all groups of rectangles that intersect each other) is to create a List<List<Rectangle>>, where each inner list is a "chain". Then loop through the original List<Rectangle> and, for each item, see if that item intersects with any item in any of the chains we've discovered so far. If it does, add it to that chain. If not, add a new chain containing just this item.

For example:

static List<List<Rectangle>> GetChains(List<Rectangle> rectangles)
{
    if (rectangles == null) return null;
    if (rectangles.Count < 2) return new List<List<Rectangle>> { { rectangles } };

    var chains = new List<List<Rectangle>>();

    foreach(var rectangle in rectangles)
    {
        var chained = false;

        foreach(var chain in chains)
        {
            if (chain.Any(r => r.IntersectsWith(rectangle)))
            {
                chain.Add(rectangle);
                chained = true;
                break;
            }
        }

        if (!chained)
        {
            chains.Add(new List<Rectangle> { rectangle });
        }
    }

    return chains;
}

Answer 3

I suggest breaking this down into two 1-dimensional problems.

First, take the x-axis. Parse your rectangles and put every pair of x-coordinates in an array, noting whether a coordinate left or right, and which rectangle it goes with.

Next, sort this array.

Next, parse the array in order. Keep track of the count of rectangles currently in-scope, as well as which particular rectangles are in-scope (in-scope meaning your current position in the array is between their left and right endpoints).

maintain a map of rectangle_id => potential_overlapping_rectangle_ids.

While parsing the array, each time you encounter a right endpoint, update the map with the key being the rectangle associated with the right endpoint, and the value being the set of in-scope rectangle ids. Also the reverse (each in-scope rectangle id is a key, and the departing rectangle gets added to the associated set).

Next, do the same for the y-axis, except this time when you encounter an endpoint (top endpoint in this case), take the intersection of the current in-scope ids with the value from the map. These are all the rectangles that are in-scope on both axes for that rectangle, so intersect with it.

Now you have all intersecting pairs of rectangles.

Answer 4

A rectangle is a node in a graph. If a rectangle overlaps another rectangle then we'll define a corresponding undirected edge in that graph. Let's define the following rules about our chains: (remember degree is the number of neighbours a node has)

• any node with degree 0 is a trivial chain.
• any node with degree 1 is potentially a start/end of a chain.
• any node with degree 2 is potentially a middle-link of a chain.
• any node with degree 3 or higher is not part of a chain.

We can find the non-trivial chains by locating all the nodes of degree 1 and beginning a depth-first search for the other end of the chain (another node with degree 1). Along the way, we permit nodes with degree 2 only.

This implementation has the side-effect that chains are uniquely ordered such that the chains appear in order according to the index of their start node, and the nodes of each chain are ordered such that its start node has a lower index than its end node.

The output of this function is a list of chains. Each chain is a list of indices of the rectangles that form that chain.

public static List<List<int>> FindChains(Rectangle[] rectangles)
{
    List<List<int>> chains = new List<List<int>>();
            
    int N = rectangles.Length;
    List<int>[] neighbours = new List<int>[N];
    for (int i = 0; i < N; ++i) {
        neighbours[i] = new List<int>();
    }
            
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            if (rectangles[i].IntersectsWith(rectangles[j])) {
                neighbours[i].Add(j);
                neighbours[j].Add(i);
            }
        }
    }

    bool[] visited = new bool[N];
    for (int i = 0; i < N; ++i) {
        if (!visited[i]) {
            int degree = neighbours[i].Count;
            if (degree == 0) {
                chains.Add(new List<int>() { i });
            } else if (degree == 1) {
                // start the chain
                List<int> chain = new List<int>() { i };
                int prev = i;
                int cur = neighbours[i][0];
                // Follow the chain
                while (neighbours[cur].Count == 2) {
                    chain.Add(cur);
                    int temp = cur;
                    // Get the "other" neighbour
                    cur = neighbours[cur][0] + neighbours[cur][1] - prev;
                    prev = temp;
                }
                // verify that we ended at a node with degree 1
                if (neighbours[cur].Count == 1) {
                    chain.Add(cur);
                    chains.Add(chain);
                    // Stop this end from being used as the start of the same chain but in reverse.
                    visited[cur] = true;
                }
            }
        }
    }

    return chains;
}

Some interesting test cases appear below. Red lines join the centroids of the chained rectangles. Rectangles that are connected in a non-chain-like manner are not marked.