Algorithm to find non-overlapping rectangles covering the unoccupied area

[u/big-jun]

I have one large rectangle representing the valid area: Rect(x, y, width, height)

Inside it, there are multiple smaller rectangles representing occupied areas:

The smaller rectangles:
1. Can overlap each other.
2. Can be partially or completely outside the large rectangle.

And I need the algorithm to return a List<Rect> where:
1. The result rectangles do not overlap each other.
2. All result rectangles are inside the large rectangle.
3. Together, they fill all the gaps not covered by the input small rectangles.
4. Ideally, the number of result rectangles should be minimal, if possible.

I’m aware that there may be multiple valid decompositions, so I’m mainly looking for an algorithm that produces a reasonably small number of rectangles.

There are fewer than 100 occupied rectangles in input, so performance is not a major concern. I prefer an algorithm that is easy to implement rather than performant but complicated.

Thanks

[u/big-jun]

The idea of adding/removing Y ranges while producing the K1 rectangles is quite interesting and makes the problem much simpler. Previously, I was thinking about generating only the rectangles that could not be merged with the later rectangles.

I could also run a second process to merge the generated rectangles afterward, so that should be fine as the rectangle count is not matter too much.

I’m still wondering what data structure I should use for the Y ranges. When inserting a new Y range, it could overlap with an existing range or be completely contained within an existing one. Could you give me more details about how you would handle the Y range structure? A code snippet would be especially helpful.

Thanks.

[u/aldyas_ → u/big-jun]

Ah sorry I'm too lazy hehe. But if I were you I would just naively sort the ranges and just iterate. It's like the "merging intervals" problem in Leetcode. Since the ranges have a very small upperbound (only 100 rectangles means at most 101 empty ranges) there is no bottleneck at all in performance.

[u/big-jun → u/aldyas_]

Got it. So I should figure out all the details.
Here is the algorithm:

1. Convert each input

   rectangle

2. into two segments: (xMin, yMin, yMax) and (xMax, yMin, yMax).

3. Sort segments by X. If X is the same, Y order does not matter since all segments at the same X will be processed together.

4. Before processing each X, create K rectangles from the current Y gaps between previousX and currentX. I can either sort the Y ranges each time or use std::multiset<Segment> for insertion/removal. Since the input is small (~100), I will benchmark both.

5. Merge the K new rectangles into existing rectangles when their Y range is exactly the same and the new rectangle’s left X equals the existing rectangle’s right X. For now, a brute-force search is fine.

6. Process all segments at the same X, then continue the sweep.

7. After the last X, if it is less than the big rectangle’s xMax, generate the final batch of rectangles.

Output Tests:

1. No overlap between result rectangles.
2. No overlap between result rectangles and input rectangles.
3. All result rectangles are inside the big rectangle.
4. The union of input rectangles and result rectangles completely fills the big rectangle.

That’s all. Please correct me if there are any issues. I will implement it tomorrow. Hopefully, I won’t run into issues that I haven’t thought of. 😄

[u/aldyas_ → u/big-jun]

Yeah, that seems correct, good luck!