3
\$\begingroup\$

I have a list of boxes, and wish to group them into unconnected sets of overlapping boxes. (Note that two boxes A and B may not overlap each other, but if they are both overlapped by a box C, they will still be grouped together).

The following works ok, but I feel like it could be made a lot more concise with LINQ, or possibly made faster.

private List<List<Box>> FindUnconnectedSets(List<Box> boxes)
{
    List<List<Box>> unconnectedSets = new List<List<Box>>();

    while (boxes.Count() != 0)
    {
        List<Box> set = new List<Box>();

        bool found = true;
        while (found)
        {
            found = false;

            foreach (Box newBox in boxes)
            {
                if (set.Count != 0)
                {
                    foreach (Box setBox in set)
                    {
                        if (newBox.Overlaps(setBox))
                        {
                            set.Add(newBox);
                            boxes.Remove(newBox);
                            found = true;
                            break;
                        }
                    }
                }
                else
                {
                    set.Add(newBox);
                    boxes.Remove(newBox);
                    found = true;
                }

                if (found)
                    break;
            }
        }

        unconnectedSets.Add(set);
    }

    return unconnectedSets;
}

Edit: added the Box class. It's not all that interesting really.

private class Box
{
    public Box(int xOrigin, int yOrigin, int size)
    {
        XOrigin = xOrigin;
        YOrigin = yOrigin;

        Size = size;
    }

    public int XOrigin;
    public int YOrigin;

    public int Size;

    public override string ToString()
    {
        string s = "Box: "
            + "(" + XOrigin.ToString() + ", " + YOrigin.ToString() + ")"
            + " " + Size.ToString();
        return s;
    }

    public bool Overlaps(Box b2)
    {
        if (XOrigin >= b2.XOrigin + b2.Size)
            return false;
        if (b2.XOrigin >= XOrigin + Size)
            return false;
        if (YOrigin >= b2.YOrigin + b2.Size)
            return false;
        if (b2.YOrigin >= YOrigin + Size)
            return false;

        return true;
    }
}

Comments welcome, both on the LINQifying side, and algorithm suggestions if you think I'm going about this the wrong way, as well as any other feedback. :)

\$\endgroup\$
  • 3
    \$\begingroup\$ Can you please add the Box implementation, and maybe a few examples of input and expected output? This could be quite helpful. \$\endgroup\$ – TeaDrivenDev Mar 1 '13 at 23:33
  • \$\begingroup\$ You call them sets but they are actually lists. You can use a HashSet<T> instead. Your function should accept a HashSet. Then write another function that accepts IEnumerable<T> and converts it to HashSet<T> and then calls the implementing function. \$\endgroup\$ – Leonid Mar 2 '13 at 0:29
  • \$\begingroup\$ @Leonid: I don't see how that adds any concrete value. \$\endgroup\$ – TeaDrivenDev Mar 2 '13 at 3:22
  • \$\begingroup\$ @GCATNM added the Box class - it's just x origin, y origin and a size value. \$\endgroup\$ – user673679 Mar 2 '13 at 11:21
  • \$\begingroup\$ @user673679 Thanks - I was just confused initially, but then realized the exact functionality didn't matter and I could just build something myself to use for testing. ;-) \$\endgroup\$ – TeaDrivenDev Mar 2 '13 at 11:48
1
\$\begingroup\$

I've made a first attempt at shortening and simplifying the code with LINQ. First, I created a helper method for moving items from one List to another based on this StackOverflow question.

private int MoveItemsWhere<T>(Func<T, bool> predicate, List<T> source, List<T> target)
{
    var selected = new HashSet<T>(source.Where(predicate));
    target.AddRange(selected);
    source.RemoveAll(selected.Contains);
    return selected.Count;
}

Then I modified the FindUnconnectedSets to use LINQ for finding overlapping boxes:

private List<List<Box>> FindUnconnectedSets(List<Box> boxes)
{
    var unconnectedSets = new List<List<Box>>();
    while (boxes.Count > 0)
    {
        var set = boxes.Take(1).ToList();
        boxes = boxes.Skip(1).ToList();

        int numAdded;
        do
        {
            numAdded = MoveItemsWhere(b => set.Any(s => s.Overlaps(b)), boxes, set);
        } while (numAdded > 0);

        unconnectedSets.Add(set);
    }
    return unconnectedSets;
}

Some notes on the above code:

  • I'm using implicit declarations with var. Personal preference, but I find it a little cleaner than repeating long types like List<List<Box>>.
  • I changed the criteria from a bool found to int numAdded because I think it's a little clearer about the purpose.
  • The core LINQ logic is b => set.Any(s => s.Overlaps(b)); this looks up every item from boxes where any item in set overlaps with the box.
\$\endgroup\$
  • 2
    \$\begingroup\$ boxes = boxes.Skip(1).ToList() Doing that in a loop is very inefficient (O(n²)). \$\endgroup\$ – svick Mar 2 '13 at 9:29
  • 1
    \$\begingroup\$ This works well. There also doesn't seem to be any difference in performance between boxes = boxes.Skip(1).ToList() and boxes.RemoveAt(0), which is surprising, but nice... \$\endgroup\$ – user673679 Mar 2 '13 at 12:58
  • \$\begingroup\$ Some of that actually makes me think this might be a good application for F#, from the examples I've seen of that language. Don't speak that myself, but it might be interesting. \$\endgroup\$ – TeaDrivenDev Mar 2 '13 at 17:27
2
\$\begingroup\$

Since we are talking about sets, it's probably better to use collection types that represent a set: HashSet<T> and ISet<T>.

Another improvement you can make is to keep track of the boxes you've added to current set at the last iteration (horizon of your expansion), and try to match candidate boxes only with them.

Note that resulting solution doesn't use the knowledge about box matching logic, so it might be a good idea to extract the interface that defines the connection between elements (i.e. a method that checks for the presence of link between nodes).

As a result I've got the following solution:

public interface IConnected<in T>
{
    bool IsConnectedTo(T other);
}

public class Box: IConnected<Box>
{
    ....

    public bool IsConnectedTo(Box other)
    {
        return Overlaps(other);
    }
}

And the FindUnconnectedSets:

public static List<ISet<T>> FindUnconnectedSets<T>(IEnumerable<T> boxes) where T : IConnected<T>
{
    var remainingBoxes = new HashSet<T>(boxes);
    var unconnectedSets = new List<ISet<T>>();

    while (remainingBoxes.Count > 0)
    {
        var newBoxes = new[] { remainingBoxes.First() }; //on each iteration will contain newly added boxes to current set
        var currentSet = new HashSet<T>();
        unconnectedSets.Add(currentSet);

        do
        {
            currentSet.UnionWith(newBoxes);
            remainingBoxes.ExceptWith(newBoxes);
            newBoxes = remainingBoxes
                .Where(remainingBox => newBoxes.Any(setBox => setBox.IsConnectedTo(remainingBox)))
                .ToArray();
        } while (newBoxes.Length > 0);
    }

    return unconnectedSets;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Shouldn't it be remainingBoxes.First() instead of Single()? Single()would throw an exception if there is more than one box left in the list. \$\endgroup\$ – TeaDrivenDev Mar 4 '13 at 13:17
1
\$\begingroup\$

The general approach seems fine; I couldn't think of a radically different algorithm - but LINQ does help indeed.

I used it to improve your code in two respects:

  • The distinction between an empty list and one that contains elements overlapping the current box at the innermost level was executing the same code in both cases; using LINQ for the checks (especially replacing the foreach) allowed me to write this in a much more concise manner and remove the code duplication.
  • The while-found-break kludge that was necessary because removing items from the target list of an iteration breaks the iterator was quite hard to fully wrap one's head around. This could be eliminated with a simple but effective trick: I iterate over a 'snapshot' copy of the boxes list while still removing the items from the original list. That prevents the iterator from breaking while still removing all the boxes from future checks that have already found their home (the ToList() call after the Select() query is very important for that to work). As a result, I only need to iterate through the current remaining boxes list once per set instead of needing to restart as many times as I find a box that belongs in the current set. Because I'm only removing items we've already left behind in the current iteration, that is not a problem for the correctness of the algorithm.

I also replaced the condition in the remaining while loop with a call to Any() instead of checking Count(); the effect is the same, but it has slightly better performance, especially on longer lists. It would be nice to get rid of the while completely in favor of another LINQ construct, but I don't see a way to do that.

public IList<IList<Box>> FindUnconnectedSets(IList<Box> boxes)
{
    IList<IList<Box>> unconnectedSets = new List<IList<Box>>();

    while (boxes.Any())
    {
        IList<Box> set = new List<Box>();

        foreach (Box newBox in boxes.Select(b => b).ToList())
        {
            if ((!set.Any()) || (set.Any(b => newBox.Overlaps(b))))
            {
                set.Add(newBox);
                boxes.Remove(newBox);
            }
        }

        unconnectedSets.Add(set);
    }

    return unconnectedSets;
}

Oh, and I replaced List<> with IList<> where possible, mainly out of a general preference for abstractions over concrete implementations; this changes nothing functionally.

By the way: If you use ReSharper, it will suggest pulling up the innermost if condition into a Where() call instead of the Select() in the foreach parameter; while that is technically correct and a more 'proficient' use of the possibilities of LINQ, it obscures the meaning of the condition and makes it harder to understand. Goes to show that shortest way to write something is not always the best.

\$\endgroup\$
  • \$\begingroup\$ Unfortunately this doesn't quite work. I should have explained the original code better: the "found" bool has another purpose too. When a box is added to the set, we have to restart iteration over the box list anyway, as the new box may add more area, and overlap with boxes we've already passed over. \$\endgroup\$ – user673679 Mar 2 '13 at 12:07
  • \$\begingroup\$ True, didn't think of that, and my test cases weren't unordered enough to catch it. That's what I meant when I said it was hard to get one's head around. Let's see what I can do about that. \$\endgroup\$ – TeaDrivenDev Mar 2 '13 at 12:23
  • \$\begingroup\$ This was my test case, sketched out on a napkin :) i.imgur.com/n1Rx7mm.jpg \$\endgroup\$ – mellamokb Mar 2 '13 at 17:23
1
\$\begingroup\$

Actually, your Box class itself interests me a bit. From the way it seems to be used, I'd make it immutable, as such:

public sealed class Box
{
    private readonly int xOrigin;
    private readonly int yOrigin;

    private readonly int size;

    public Box(int xOrigin, int yOrigin, int size)
    {
        this.xOrigin = xOrigin;
        this.yOrigin = yOrigin;

        this.size = size;
    }

    public int XOrigin { get { return this.xOrigin; } }
    public int YOrigin { get { return this.yOrigin; } }

    public int Size { get { return this.size; } }

    public override string ToString()
    {
        return "Box: "
            + "(" + this.xOrigin + ", " + this.yOrigin + ")"
            + " " + this.size;
    }

    public bool Overlaps(Box b2)
    {
        if (b2 == null)
            throw new ArgumentNullException("b2");
        if (this.xOrigin >= b2.XOrigin + b2.Size)
            return false;
        if (b2.XOrigin >= this.xOrigin + this.size)
            return false;
        if (this.yOrigin >= b2.YOrigin + b2.Size)
            return false;
        if (b2.YOrigin >= this.yOrigin + this.size)
            return false;

        return true;
    }
}

This may also be a decent candidate for being turned into a struct, if your Boxes can be happy with an XOrigin, YOrigin and Size of 0 by default.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.