Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Inverting a set of rectangles on a 2D plane

I have a rectangular plane of integer dimension. Inside of this plane I have a set of non-intersecting rectangles (of integer dimension and at integer coordinates).

My question is how can I efficiently find the inverse of this set; that is the portions of the plane which are not contained in a sub-rectangle. Naturally, this collection of points forms a set of rectangles --- and it is these that I am interested in.

My current, naive, solution uses a boolean matrix (the size of the plane) and works by setting a point i,j to 0 if it is contained within a sub-rectangle and 1 otherwise. Then I iterate through each element of the matrix and if it is 1 (free) attempt to 'grow' a rectangle outwards from the point. Uniqueness is not a concern (any suitable set of rectangles is fine).

Are there any algorithms which can solve such a problem more effectively? (I.e, without needing to resort to a boolean matrix.

like image 666
Freddie Witherden Avatar asked Nov 21 '10 19:11

Freddie Witherden


2 Answers

Yes, it's fairly straightforward. I've answered an almost identical question on SO before, but haven't been able to find it yet.

Anyway, essentially you can do this:

  • start with an output list containing a single output rect equal to the area of interest (some arbitrary bounding box which defines the area of interest and contains all the input rects)
  • for each input rect
    • if the input rect intersects any of the rects in the output list
      • delete the old output rect and generate up to four new output rects which represent the difference between the intersection and the original output rect

Optional final step: iterate through the output list looking for pairs of rects which can be merged to a single rect (i.e. pairs of rects which share a common edge can be combined into a single rect).

like image 186
Paul R Avatar answered Sep 17 '22 14:09

Paul R


Alright! First implementation! (java), based of @Paul's answer:

List<Rectangle> slice(Rectangle r, Rectangle mask)
{
        List<Rectangle> rects = new ArrayList();

        mask = mask.intersection(r);

        if(!mask.isEmpty())
        {
                rects.add(new Rectangle(r.x, r.y, r.width, mask.y - r.y));
                rects.add(new Rectangle(r.x, mask.y + mask.height, r.width, (r.y + r.height) - (mask.y + mask.height)));
                rects.add(new Rectangle(r.x, mask.y, mask.x - r.x, mask.height));
                rects.add(new Rectangle(mask.x + mask.width, mask.y, (r.x + r.width) - (mask.x + mask.width), mask.height));

                for (Iterator<Rectangle> iter = rects.iterator(); iter.hasNext();)
                        if(iter.next().isEmpty())
                                iter.remove();
        }
        else rects.add(r);

        return rects;
}

List<Rectangle> inverse(Rectangle base, List<Rectangle> rects)
{
        List<Rectangle> outputs = new ArrayList();
        outputs.add(base);

        for(Rectangle r : rects)
        {
                List<Rectangle> newOutputs = new ArrayList();

                for(Rectangle output : outputs)
                {
                        newOutputs.addAll(slice(output, r));
                }

                outputs = newOutputs;
        }
        return outputs;
}

Possibly working example here

like image 41
Eric Avatar answered Sep 21 '22 14:09

Eric