What's the best way to merge a set of rectangles in an image?

Question

This is not a homework question :)

I have a set of rectangles scattered across an image. I want to merge (create a union) of every group of intersected rectangles. If a rectangle doesn't intersect its neighbors, it remains untouched.

The problem is that merged rectangles can intersect rectangles that were previously not in consideration; merged rectangles can also intersect newly-merged rectangles. I want to catch those cases.

So, in my mind, it needs to be iterative (try each rect against every other rect in the set) and recursive (try each merged rect against the set again, including merged rects).

How can I go about this? I'm working in Java, but this is more of an algorithmic question than a language-oriented one.

Thanks!

Edit: added relevant code to better illustrate the poor way in which I'm handling it now.

public static List<BinaryRegion> mergeRegions(List<BinaryRegion> regions)
{
    List<BinaryRegion> merged = new ArrayList<BinaryRegion>();
    geoModel = new GeometryFactory();

    Polygon polys[] = new Polygon[regions.size()];
    for (int i = 0; i < regions.size(); i++)
    {
        Polygon p = convertRectangleToPolygon(regions.get(i)
                .getBoundingBox());
        polys[i] = p;
    }

    System.out.println("Converted " + regions.size() + " polys");

    for (int i = 0; i < regions.size(); i++)
    {
        System.out.println("Sending in poly " + i);
        ArrayList<Polygon> result = mergePoly(polys[i], polys);
        System.out.println("After run, size=" + result.size());
    }
    return merged;

}

private static ArrayList<Polygon> mergePoly(Polygon p, Polygon[] polys)
{
    ArrayList<Polygon> merges = new ArrayList<Polygon>();

    for (int i = 0; i < polys.length; i++)
    {
        if (p.equals(polys[i]))
            System.out.println("found the exact match at " + i);
        else if (p.intersects(polys[i]))
        {
            System.out.println("Found intersection at " + i);
            System.out.println("Other poly is area "+polys[i].getArea());
            Polygon u = (Polygon) p.union(polys[i]);
            System.out.println("Merge size="+u.getArea());
            merges.add(u);
        }
        else
            merges.add(polys[i]);
    }
    return merges;
}

Answer 1

Not entirely sure whether this nested iterative approach is really the way to go (especially since I don't see how exactly you're handling the merged regions after your call to mergePoly). Instead of working with one polygon at a time comparing to all other polygons, why don't you keep intermediate steps and rerun the merge until there are no more intersections? Something along the lines of:

private static ArrayList<Polygon> mergePoly(Polygon[] polys)
{
    List<Polygon> polygons = new ArrayList<Polygon>(Arrays.asList(polys));
    boolean foundIntersection = false;
    do
    {
        foundIntersection = false;
        for (int i = 0; i < polygons.size(); i++)
        {
            Polygon current = polygons.get(i);
            for (int j = i + 1; j < polygons.size(); j++)
            {
                if (current.intersects(polygons.get(j)))
                {
                    foundIntersection = true;
                    current = (Polygon)current.union(polygons.remove(j--));
                    System.out.println("Merge size="+u.getArea());
                }
            }
            polygons.set(i, current);
        }
    } while(foundIntersection);
    return polygons;
}

It's been a while since I've worked with Java, but the logic is pretty self-explanatory. You perform two iterations of the polygons. The outside iteration is your "current" polygon, that you will merge all the inner polygons with (removing them from the collection as you go along). After every outer iteration, you'll just set the element at that index with the (possibly) merged polygon, and move on to the next polygon in the series. You'll keep doing this until you no longer get anymore merges. Just keep in mind that this is a horribly naive implementation, and you might be better off breaking it off into "halves" and merging these smaller subsets (think of mergesort).

Answer 2

You can use the sweep line algorithm to find the intersections of rectangles (example1, example2) and the union-find algorithm to effectively merge sets of rectangles.