Crayz92

Filling a rectangle with randomly chosen rectangles of specific size?

Recommended Posts

Crayz92    173

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:

4d810bc144.png

 

I need it to look more like this:

556e838f0f.png

Share this post


Link to post
Share on other sites
Alberth    9529

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
Lactose    11471

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
Crayz92    173

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:

271c0c8417.png

 

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