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.
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:
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With