Filling a rectangle with randomly chosen rectangles of specific size?

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 this post

Link to post
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 this post

Link to post
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 this post

Link to post
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

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now