How to distribute rectangles with minimum overlap

Question

Basically I need to distribute various rectangles in a bigger rectangle randomly. So:

1. While there is enough space, rectangles don't overlap or overlap just a bit.
2. When there is not enough space rectangles overlap but still trying to overlap as little as possible (so they all stack in one place).

I don't need classical ideal top-left to bottom-right packing. The point is that I need random spread.

At first I tried to brute-force it by randomly selecting position for a rectangle and then comparing collision with all rectangles that were already placed. Not ideal, obviously.

Then I tried to assign "points" to the space and place rectangles near these points. The closer rectangle was to a point the more "pressure" it applied to it. And that pressure stacked for each rectangle that was placed. Algorithm tried to place rectangles near points with minimal pressure. Unfortunately this resulted in rectangles stacking near top-left and bottom-right corners.

(If you'll close this one too I don't even know what more info do you need).

Answer 1

Assuming you don't want any overlap you can use method called sweeping to find all possible spots for middle of new rectangle. It can be divided into rectangles, then calculate area of each one and choose one randomly with respective ratios. If that is good solution ask for more details.

And if they can overlap, let's say 10% then just make rectangles smaller than 10%, distribute them and them inflate back.

Answer 2

Maybe you can divide the screen and randomly distribute the rectangles on the divided area. If they overlap, remove the last step, find another area randomly on screen and start to distribute.

Divide the screen n parts and randomly select a part from it and store it. If it recures again, neglect it and move on and continue to fill it with rectangles. You can shape this shapes similar to shapes of rectangles and write another algorithm for it. Like puzzle you will find the pieces from your collect of rectangles in try to fit every figure fit approximate figure to the puzzle. So, transforming problem to that way may help. You can turn the problem a random fitting to pieces to puzzle problem. Good luck.

• Step 1: randomly select and area,
• Step 2: distribute the rectangle,
• Step 3: If overlap ,remove the last step,
• Step 4: If overlap , select new area randomly,

You can loop this process.