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 boo开发者_Go百科lean matrix.

---

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).

---

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

---

You should take a look for the space-filling algorithms. Those algorithms are tyring to fill up a given space with some geometric figures. It should not be to hard to modify such algorithm to your needs.

Such algorithm is starting from scratch (empty space), so first you fill his internal data with boxes which you already have on the 2D plane. Then you let algorithm to do the rest - fill up the remaining space with another boxes. Those boxes are making a list of the inverted space chunks of your plane.

You keep those boxes in some list and then checking if a point is on the inverted plane is quite easy. You just traverse through your list and perform a check if point lies inside the box.

Here is a site with buch of algorithms which could be helpful .

---

I suspect you can get somewhere by ordering the rectangles by y-coordinate, and taking a scan-line approach. I may or may not actually contruct an implementation.

---

This is relatively simple because your rectangles are non-intersecting. The goal is basically a set of non-intersecting rectangles that fully cover the plane, some marked as original, and some marked as "inverse".

Think in terms of a top-down (or left-right or whatever) scan. You have a current "tide-line" position. Determine what the position of the next horizontal line you will encounter is that is not on the tide-line. This will give you the height of your next tide-line.

Between these tide-lines, you have a strip in which each vertical line reaches from one tide-line to the other (and perhaps beyond in both directions). You can sort the horizontal positions of these vertical lines, and use that to divide your strip into rectangles and identify them as either being (part of) an original rectangle or (part of) an inverse rectangle.

Progress to the end, and you get (probably too many too small) rectangles, and can pick the ones you want. You also have the option (with each step) of combining small rectangles from the current strip with a set of potentially-extendible rectangles from earlier.

You can do the same even when your original rectangles may intersect, but it's a little more fiddly.

Details left as an exercise for the reader ;-)