CODEWITHSUNDEEP
algorithmoverlaprectanglespacking
user64675
user64675

Reputation: 356

How to distribute rectangles with minimum overlap

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.

enter image description here

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

Upvotes: 3

Views: 890

Answers (2)

Barış Can Tayiz
Barış Can Tayiz

Reputation: 87

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.

Upvotes: -1

miszcz2137
miszcz2137

Reputation: 914

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.

Upvotes: 2

Related Questions