I think you should take a step back and think about this problem from a different perspective. Instead of randomly choosing the width and height of the rectangles and then try to optimize their positions to be tightly packed, you can successively split the domain into smaller and smaller rectangles. This way, the rectangles are already positioned and tightly packed as you might expect.
Algorithm
Our general algorithm can be as follows:
- Create a loop that takes an initial list of rectangles as input. The list could initially contain a single big rectangles which we could consider our boundary.
- For each iteration in the loop, we choose a rectangle at random and split it at a random position to produce two smaller rectangles. We then remove that rectangles from the list and add the two produced rectangles.
- We could add a condition that skips the rectangles that have an area less than some threshold value. This ensures rectangles don't get too small. We could also add a condition for the areas of the resulted rectangles, but we shall not do this in this instance.
We shall define each rectangles by two 2D vectors, a vector representing the location of the lower left corner, and another representing the location of the upper right corner. Let those two vectors be $(x_1, y_1)$ and $(x_2, y_2)$. We have two ways to split a rectangle into two smaller ones, horizontal splitting and vertical splitting. This diagram demonstrate how one can compute the two smaller rectangles from the original rectangle using vertical splitting:
First, a random float $\delta \in [y_1, y_2]$ is chosen as the $y$ location of the splitting. Then the two rectangles are defined as:
- $(x_1, y_1)$, $(x_2, \delta)$.
- $(x_1, \delta)$, $(x_2, y_2)$.
Similarly, horizontal splitting can be done by choosing a random $\delta \in [x_1, x_2]$ and forming the two rectangles based on it.
Implementation
We shall define each rectangle using a struct of four floats. Our initial rectangle list will be composed of a single struct representing a rectangle defined using an empty in the scene. The loop will output a list of structs, those structs can then easily be used to construct quad meshes which can be output and used. The high level node tree look like this:
With the Generate Rectangles loop defines as:
As for the Compute Rectangles loop, we first get the index of some random rectangles from the list. We use that index to get the rectangle and delete it from the list:
Then we compose the four rectangles (Two for each split type) based on the formula above. A random number is used to determine if the type is horizontal or or vertical by switching between rectangles. Finally, the two rectangles are combined with the rest of the rectangles and are reassigned if the area condition is met:
And by adding some value to the seed for seed control, we get:
Which gives the following result:
Blend file:
The animation should be easy, so I will let you do that on your own.
