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?

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.

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.

Answer 3

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.

Answer 4

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.