Find rectangles recursively

Question

I have a list of overlapping rectangles. I need find a list of lists in which all the overlapping rectangles are returned. For example, in a list of 7 rectangles, if 4 rectangles are overlapped and rest are separate then a list of lists should look like this:

[0]: r1, r2, r3, r4
[1]: r5
[2]: r6
[3]: r7

I know I have to perform a hit test. I am looking for an algorithm or an example to create chains please.

Thanks

I have tried this code: Sometimes it works, sometimes, it throws index out of bound kinda exception.

while (rects.Count != 0)
            {
                listOfRects.Add(joinRectangles(rects, new List<Rectangle>(), rects[rects.Count - 1]));
            }

        private List<Rectangle> joinRectangles(List<Rectangle> rects, List<Rectangle> tempRects, Rectangle curRect)
        {
            for (int j = rects.Count; j-- > 0; )
            {
                if (hitTest(curRect, rects[j]) == true)
                {
                    if (tempRects.Contains(rects[j]) == false)
                    {
                        tempRects.Add(rects[j]);
                        curRect = rects[j];
                        rects.Remove(rects[j]);

                        j--;

                        joinRectangles(rects, tempRects, curRect);
                    }
                }


            }


            return tempRects;
        }

If I supply these coordinates then I should get a list of 4 lists like this:

    [0]: 1 rectangle
    [1]: 3 rectangles
    [2]: 1 rectangle
    [3]: 1 rectangle


<?xml version="1.0" encoding="utf-16"?>
<rectangles>
  <rectangle>
    <X1>50.833333344375</X1>
    <Y1>100</Y1>
    <X2>53.833333344375</X2>
    <Y2>127.00000004975</Y2>
  </rectangle>
  <rectangle>
    <X1>136.500000033125</X1>
    <Y1>100</Y1>
    <X2>139.516666655625</X2>
    <Y2>127.00000004975</Y2>
  </rectangle>
  <rectangle>
    <X1>50.833333344375</X1>
    <Y1>130.647222172472</Y1>
    <X2>53.833333344375</X2>
    <Y2>157.647222222222</Y2>
  </rectangle>
  <rectangle>
    <X1>136.500000033125</X1>
    <Y1>130.647222172472</Y1>
    <X2>139.516666655625</X2>
    <Y2>157.647222222222</Y2>
  </rectangle>
  <rectangle>
    <X1>136.500000033125</X1>
    <Y1>100</Y1>
    <X2>139.516666655625</X2>
    <Y2>157.3333333830833</Y2>
  </rectangle>
  <rectangle>
    <X1>179.3333333775</X1>
    <Y1>100</Y1>
    <X2>182.3333333775</X2>
    <Y2>157.3333333830833</Y2>
  </rectangle>
</rectangles>

Answer 1

Written quicly from scratch before you posted your own code. You have a rectangleList, and want to group them by overlap groups.

You use this groupRectangles function

public List<List<Rectangle>> groupRectangles(List<Rectangle> rectangleList) {

List<List<Rectangle>> groupOverlappedRectangles = new List<List<Rectangle>>();

foreach (Rectangle r : rectangleList) {
    bool overLap = false;
    foreach (List<Rectangle> liste : groupOverlappedRectangles) {
        if (overlapsRectangleList(r,liste))
        {
                liste.add(r);
            overLap = true;
            break;
        }
    }
    if (!overLap) {
        List<Rectangle> newOverlapList = new List<Rectangle>();
        newOverlapList.add(r);
        groupOverlappedRectangles.add(newOverlapList);
    }
}
return groupOverlappedRectangles;
}

public bool overlapsRectangleList(Rectangle r, List<Rectangle> listeOver)
{
    foreach (Rectangle rOver : listeOver) {
        if (r.IntersectsWith(rOver)) {
            return true;
    }
    }
    return false;
}

Answer 2

Heres another approach using Rectangle.IntersectsWith and Linq's deferred execution:

var intersectingRectangles = new List<List<Rectangle>>();
var alreadyChecked = new HashSet<Rectangle>();
var toCheck = rectangles.Except(alreadyChecked);
while (alreadyChecked.Count != rectangles.Count)
{
    var intersections = toCheck.Where(r => r.IntersectsWith(toCheck.ElementAt(0)))
                               .ToList();
    intersectingRectangles.Add(intersections);
    foreach (var r in intersections)
        alreadyChecked.Add(r);
}
intersectingRectangles.Sort((rl1, rl2) => (-1) * rl1.Count.CompareTo(rl2.Count));

Maybe not the most readable way but one of the shortest :)

Edit: Here's a demo(difficult with mono without System.Drawing and Rectangles):

http://ideone.com/eOCMN

Answer 3

For each rectangle all earlier groups of rectangles has to be checked. For instance if A and C overlaps, and B and C, but not A and B. If the algorithm receives A, B, C, it will first put A in one list, then B in another list. But when C comes it has to merge both the list with A and the list with B, to the new list containing C. (That's what the other answers seem to have missed.)

public static List<List<Rectangle>> SortOverlap(Rectangle[] rectangles)
{
    var result = new List<List<Rectangle>>();
    for (int i = 0; i < rectangles.Length; i++) 
    {
        var newList = new List<Rectangle>();
        newList.Add(rectangles[i]);
        for (int j = 0; j < result.Count; j++) 
        {
            if(result[j].Any(r => r.Overlap(newList[0])))
            {
                newList.AddRange(result[j]);
                result[j] = null;
            }
        }
        result.Add(newList);
        result.RemoveAll(list => list == null);
    }
    return result;
}

Edit: The overlap check is rather simple to implement, so no need to use System.Drawing or similar only for that check...

public class Rectangle {
    ....
    public bool Overlap(Rectangle other)
    {
        return !(this.MinX >= other.MaxX || this.MaxX <= other.MinX ||
                 this.MinY >= other.MaxY || this.MaxY <= other.MinY);
    }
}