# Filling a rectangle with randomly chosen rectangles of specific size?

This topic is 392 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

The size of my root rectangle will be power of 2 and the size of the children rectangles will always be divisible by 4.

Say I have a rectangle of size 128x128, is there an algorithm that can fill it with rectangles who's size is randomly chosen from an array (i.e. [(8, 8), (8, 16), (16, 16), (16, 24), (24, 24)]).  There should be no gaps

My first attempt involved splitting the root rectangle recursively, but this result is uniform to a grid and won't work:

I need it to look more like this:

##### Share on other sites

I don't know any algorithm, but my first thought is to start with the entire rectangle, and repeatedly split one rectangle in two, with a direction (horizontal / vertical), and an offset from eg top-left corner.

You can play with several parameters, like throwing smaller rectangles out, or give priority to larger rectangles, or cut the longest direction. Hopefully you'll find a setup that gives nice results.

##### Share on other sites

My first thoughts were opposite to Alberth's idea. Note that this is all untested.

Fill a grid cells that are all the same size (smallest size wanted). In your example image, it looks like there could be 8x8.

Randomly select a cell, and merge it with an adjacent cell if the dimensions match.

Alternatively, mark all cells as unused. Then select x of them and give their own identifier. Grow them to merge with adjacent cells if they are unused.

At the end loop over and deal with e.g. non-rectangles and any potential other cases.

##### Share on other sites

Offsetting improved the result though I think I'm going about it wrong with splitting as it always results in seams which are separating areas from the rest

I'm gonna give Lactose's idea a try now and see how it works out

Edit: Final result:

I can work with this.  Thanks for the ideas

Edited by Crayz92

1. 1
Rutin
19
2. 2
3. 3
JoeJ
16
4. 4
5. 5

• 26
• 20
• 13
• 13
• 17
• ### Forum Statistics

• Total Topics
631700
• Total Posts
3001782
×