Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Algorithm needed for distributing rectangles evenly within another rectangle

I am looking for an algorithm that can help distribute different sized rectangles within a larger rectangle while minimizing overlapping.

I have looked at bin packing algorithms, but they seem to minimize the amount of space between rectangles (in my case the all of the items being packed will be squares).

I guess I want to maximize the distance between all squares and the border of the outer rectangle.

Here is an example of what I am trying to do:

Example of what I am saying

like image 377
howardr Avatar asked Nov 26 '22 11:11

howardr


1 Answers

What if you packed them as tightly as possible, using an algorithm like the one described here, then expanded evenly to match the target enclosing rectangle?

For example, say you can pack the 3 rectangles above into a 3x2 box, and your outer box is 7x5. Then take the vector from the center of the box to the center to each rectangle, and multiply the x component by (7/3), and the y component by (5/2), and that gives the new center.

like image 71
AShelly Avatar answered Dec 10 '22 11:12

AShelly