Splitting the remaining space of rectangles into rectangles

Question

Given some rectangles inside of a larger rectangle, is there any algorithm to split the remaining space into rectangles, and preferably as few as possible?

Answer 1

One way to solve the problem is to reduce the rectangles to a mesh. Each rectangle corner becomes a vertex (x,y) and each rectangle's side is a line that references two vertices. Vertices that are on a line (eg two rectangle are touching) must split the line at that vertex. There may only be one line joining any two vertices. The bounding rectangle is included.

Once you have the rectangles converted to a mesh then for each vertices count the number of lines that use that vertex.

If a vertex has only 2 lines joining it and is not a bounding corner, then it must be extended, it will have two optional directions, horizontal and vertical. There is no rule in which direction is the best so pick a random direction. In that direction and moving away from the lines coming to the vertex add a vertex to the closest intersecting line. Continue the process until no vertices (apart from the bounding corners) have less than 3 lines connected to it.

Now start at the top left most vertex and trace the lines in a clockwise direction, each 4 lines is a rectangle when you get back to the starting vertex you have a new rectangle Use the min and max vertex coordinates in the x and y direction to define the size of the rectangle. For each line decrease its vertices line count by 1. When a vertex has a line count of zero remove the vertex; When all vertices are removed you are done.

This will create the minimum number of rectangles possible.

To know if a solution is the minimum rectangle count check that each vertex has ONLY 3 lines joining it (Your example image is the minimum number of rectangle because no vertex has more than 3 lines joining it)

The only exception to this rule is if the existing rectangles are touching at a corner. Only existing vertices may have 4 lines joining.

Answer 2

Using a bsp tree: insert each rectangle edge in the tree. This will partition the space into convex subsets. Since your input are rectangles, the convex subsets can only be rectangles (https://en.wikipedia.org/wiki/Binary_space_partitioning).

Note that the partition depends on the order in which you insert the edges.

I'm not sure though that this will give you the minimum number of rectangles, but you will get close.