Place random non-overlapping rectangles on a panel

Question

I've a panel of size X by Y. I want to place up to N rectangles, sized randomly, upon this panel, but I don't want any of them to overlap. I need to know the X, Y positions for these rectangles.

Algorithm, anyone?

Edit: All the N rectangles are known at the outset and can be selected in any order. Does that change the procedure?

Merrilee

gamedev.stackexchange.com/questions/6730/… – Wash

Answer 1

You can model this by a set of "free" rectangles, starting with single one with coordinates of 0,0, size (x, y). Each time you need to add one more rectangle, choose one of remaining "free" rectangles, generate new rectangle (with top-left coordinate and size such that it will be fully contained), and split that rectangle as well as any other overlapping "free" rectangle, such that children express remaining free space. This will result in 0 to 4 new rectangles (0 if new rectangle was exactly the size of old free rectangle; 4 if it's in the middle and so on). Over time you will get more and more smaller and smaller free areas, so rectangles you create will be smaller as well.

Ok, not a very elaborate explanation, it's easier to show on whiteboard. But the model is one I used for finding starting location for newly cut'n pasted gui components; it's easy to keep track of available chunks of screen, and choose (for example) left or topmost such area.

Oligarch

I implemented this and it works really well. I also added merging of the free rectangles to avoid the smaller and smaller problem. – Vadose

@TomerPintel, how did you merge the free rectangles? I can do it visually very easily but cannot figure out where to start doing it algorithmically. – Florenceflorencia

@dataduck, for every free rectangle, go over all the other free rectangles. Check if their Left, Width are equal and if the Bottom of one equals the Top of the other - If all are true it means we have two free rectangles one above the other. Create a new rectangle that contains both of these rectangles with the same width but with the combined height of the existing two. Remove the old rectangles from the list and add new new one instead. – Vadose

Answer 2

Here is a decent article on 2d packing algorithms: http://www.devx.com/dotnet/Article/36005

You'll generally want some sort of algorithm using heuristics to achieve decent results. A simple (but non-optimal) solution would be the first fit algorithm.

Column

Sadly this article seems to be offline, it returns a 404. If anyone know how to find an update, please edit the answer! – Carilyn

Answer 3

I used this Rectangle Packing algorithm in one of my applications, available as C# source files.

The algorithm is initialized with the size of the panel, then you iterate through all rectangles and get their position. The order of the rectangles may influence the result, depending on the packer.

Heall

Answer 4

I would advise you use StaxMans suggestion.

Here is my 2c:

Add a whole lot of rectangles randomly (overlapping each other). delete overlapping rectangles:

for rectangle in list of rectangles:
    if rectangle not deleted:
        delete all rectangles touching rectangle.

to find all the rectangles touching a particular rectangle, you can use a quad tree or inequalities based on x1,y1 x2,y2 values.

Edit: In fact, most game engines such as pygame etc include collision detection of rectangles which is a common problem.

Tetracaine

Answer 5

Or maintain a list of rectangles already added and create an algorithm that figures out where to place the new rectangle based on that list. You can create a basic Rectangle class to hold the information about your rectangles.

Shouldn't be so hard to create a custom algorithm.

Jena

every time someone says "shouldn't be so hard", they should show code. – Peck