Shape fitting algorithm

General
1

Fitting rectangles.

Let’s say I have placed a number of Rectangles on screen. Now I want to randomize their placement. How do I do that?

I know how to rotate them, but will not need to do that. Only shuffle them up.

Here are my assumptions.
Loop over the rectangles and get the size of each, and place that into an array:
Rect 1, Height, Width
Rect 2, Height, Width
…
Rect n, Height, Width

Now there may be only one way to fit them, but let’s assume not for a moment.

  1. Sort the array by area, we’ll place the largest item first.
  2. Start with the largest shape.
  3. Loop over the space to see where we can place the largest shape by Width,
    4) Then check to see the if the shape fits by Height.
  4. If both are true, then move on to the next shape.

I assume I need to keep track of the filled space somehow, but I should be able to do that by looping over the X/Y of the area to see if there would be a collision with place shapes.

In my main loop, if I can’t fit all the shapes, then I have a failed solution, and move on to another but insure the first shape does not start at any failed starting location.

Having said all that, I suspect there may be a solution to this problem elsewhere.

Any suggestions?

Thanks Eric

2

OK, I see these are known as “Packing” problems. And are of NP complexity. So, to simplify my shuffle, I’ll do this …

With the largest shape, there are only so many places in the area that it can be placed. So a 1000 x 1000 pixel area, with a 100 x 100 pixel, largest rectangle has a limited number of solutions. AND I don’t need every solution, so once I place the 100 x 100 pixel rectangle, I’ll only consider further solutions where the largest shape is 10 pixels lower. Or maybe only lower by the number of pixels of the smallest shape. Same goes for the width. Doing this limits the number of possible solutions.

Notice I am not looking to tight-fits, or other optimizations. I just want some shuffles.
Once I have nine variations, I’m done.

3

In fact, if I divide the area into nine sub-areas, then place the largest shape starting point into each of the nine (randomized, yet allowing all other shapes to potentially fit), I reduce the problem even further.

The number of rectangles would be less than 10.

Maybe once the largest shape is placed, I can calculate the remaining space, and IF the area of all the other rectangles could fit, then this is a potential solution.

To know the area remaining after the largest rectangle is placed, I need to see if there is enough contiguous space for the next shape. Subtract that, the continue through all the shapes.

4

This looks like the ticket!

Now I can rotate their solution into nine variations. One where the starting shape is starting positon is changed.

Let’s see how I code this now.

5

Like a tic-tac-toe board, the left and right are symmetrical. So solving for the largest rectangle in the upper left, middle left and lower left, the right version is the same, but X is flipped. And the top-middle, and bottom-middle are the same but flipped Y. So if I simplify the problem, where the largest shape is in one of nine positions, then I need to solve 3(left positions) +1(upper middle) +1(center) times. Or 5 recursive runs. All the other shapes will be handled the same way.

We’ll see how this works out …