Divide rectangular image into fixed number of random sized rectangles + 1 fixed size rectangle

Question

I'm trying to divide a rectangular image into a fixed number of smaller rectangular image parts (of random but bounded width / height), with the exception of 1 rectangle which is predefined in position and size.

So, for example:

My first thought was:

• Generate list of possible points
• From this list remove all points in the fixed size rect
• From this list remove all points that can't possibly meet the other requirements (e.g. points close to the image edges that wouldn't meet the required bounded min / max rect size)
• Then randomly pick a point, generate a random bounded width / height, see if this intersects any current rect, until we find one that doesn't
• Record rect, remove all points in rect from list
• Repeat

However this seems slow, overly-complex and still results in holes because sometimes there's no more room for the minimum size of rect to fill the last bit of space.

I've looked into algorithms involving squaring the square, packing routines and such like, but nothing I've found helps with the additional constraint that one rectangle is predefined and the rest can be random.

Not looking necessarily for a full algorithm, but hints at an approach would be appreciated.

Answer 1

I would say... start with the fixed rectangle. Extend either the vertical or horizontal sides to the edges of the area; this gives you 5 rectangles (including the fixed one). Randomly choose any of the N non-fixed rectangles, cut it in half vertically or horizontally, giving you N+1 rectangles. Repeat until you have the number of rectangles you want.

Answer 2

I suspect that positioning rectangles completely randomly could let to a lot of failed solutions, and no clear idea why a solution failed.

My suggestion would be to start at the fixed rectangle and randomly generate adjacent rectangles. In a similar manner to a search such as A*, you would end up with a closed list and an open list, e.g. closed contains rectangles which are completely surrounded and open contains rectangles with at least one free edge. Because they would be generated adjacently, there would be readily available data on potential clashes that may lead to no solution, and at that point you could backtrack. You may also find some heuristics that help the search, e.g. process the open list in order of shortest free edge.

Answer 3

I would suggest a sweep approach. Starting from the origin, choose one axis (for example y, which I will consider as the columns axis) and generate random sizes for the rects until you reach the end of the axis. This will setup column[0]. For each rect[i] in column[j], you should save rect[i].finalX as the final x coordinate of this rect.

To generate the next column[j + 1] you should, for each rect[i] in column[j], create new rects starting from column[j].rect[i].finalX until you fill all y interval of column[j].rect[i]. The algorithm finishes when one column cannot insert more rects.

It is important to note that this algorithm will create rects with smaller y size as the sweep proceeds. To fix that you could randomly create adjacent rects with same finalX. In the next column you can consider these adjacent rects as one, boosting the y size to work on.

If the procedure is not clear, ask me and I edit the answer with a formal algorithm.