How to horizontally distribute rectangles with different sizes?

Question

I have a set of rectangles with different sizes:

All rectangles are constrained in the Y-direction, i.e. Y-coordinates are fixed, they can be moved only along the X-axis. Now, i would like to horizontally arrange all this rectangles with an equal distributed spacing, but some of them (the grey rectangles in the picture) are constrained by the left and right neighbors (the red rectangles), but also by the rectangles below and above as well.

EDIT: The initial position of the rectangles is defined sequentially, by rows. Moreover, in my first implementation attempt, i'm storing also in each row the presence of the vertical rectangles, which overlaps two or more rows, like as follows:

Row 1: {id:1,w:15,h:10},{id:2,w:10,h:40},{id:3,w:10,h:40},{id:4,w:20,h:10}
Row 2: {id:2,w:10,h:40},{id:5,w:10,h:40},{id:3,w:10,h:40},{id:6,w:10,h:10},{id:7,w:10,h:10}
Row 3: {id:8,w:10,h:10},{id:9,w:18,h:10},{id:5,w:10,h:40},{id:10,w:10,h:10}

I'm searching an algorithm to horizontally distribute all this rectangles so that the left and right spacing of each with the nearest is the same, like in the picture.

EDIT 2: Any hint how to handle higher complexity, would be also appreciated:

Answer 1

Sort the rectangles from left to right, using their leftmost coordinate, as in the image below:

Then, iterate over every rectangle from left to right, and see which rectangles to the left of them they overlap vertically with (i.e. if you moved them left, which rectangles would they bump into).

A and B reach the left window edge without bumping into any other rectangles.
C bumps into A.
D bumps into B.
E bumps into A, C and D.
F bumps into B, D and E.
G bumps into D, E and F.
H bumps into A, C and E.
I bumps into B, D and F.
J bumps into D, E, F and G.

Use this information to build a graph as shown below. When a rectangle bumps into several other rectangles, e.g. E bumps into A, C and D, and these rectangles are themselves part of the same branch, e.g. A and C, then only connect it to the rightmost rectangle, i.e. rectangle C.

Then, store every rectangle's width in pixels in the graph. We will then try and find the weight X of the edges, which represents the width of the space between the rectangles.

To do this, we need to find a number of paths through the graph. First, we search the longest path, i.e. the path with the most rectangles, without taking their width into account; in the example that is:

left window edge → A → C → E → F → G → J
left window edge → B → D → E → F → G → J

We then check which of these paths has the greatest combined width:

left window edge → A → C → E → F → G → J = 240

Then we look at shorter paths, and see if they have a greater width:

left window edge → A → C → E → F → I = 230
left window edge → B → D → E → F → I = 220
left window edge → A → C → E → H = 168
left window edge → B → D → E → H = 158

In the example, none of the shorter paths have a greater width. If some of them did, we'd have to take the widest path for every length into account too. As it is, we only have to look at the path:

left window edge → A → C → E → F → G → J = 240

Connect this path to the right window edge, so that it has an extra edge; there are now 7 edges of width X. The combined width of the rectangles is 240 pixels, so if the window is e.g. 450 pixels wide, then X = (450 - 240) / 7 = 30 pixels. If there were several paths to take into account, you'd take the minimum result for X.

The rectangles in the path with the minimum result for X will have exactly X pixels of space between them; the other rectangles have some wiggle room. You could enter X as the weight of the edges in the longest path in the graph, and then use the graph to further calculate the equal spacing of the other rectangles. Or you could just put them at distance X from their left or right neighbour.

---

For a more complicated case, imagine that in the example rectangle I is 90 pixels wide, and rectangle H is 120 pixels wide. These would be the paths:

6 rectangles:
left window edge → A → C → E → F → G → J = 240
left window edge → B → D → E → F → G → J = 230

5 rectangles:
left window edge → A → C → E → F → I = 254
left window edge → B → D → E → F → I = 244

4 rectangles:
left window edge → A → C → E → H = 250
left window edge → B → D → E → H = 240

Then the paths to take into account would be:

left window edge → A → C → E → F → G → J = 240

because it is the widest of the paths with the most (6) rectangles, and:

left window edge → A → C → E → F → I = 254

because it is the widest of the paths with 5 rectangles, and is wider than the 6-rectangle path.

(The widest 4-rectangle path is wider than the 6-rectangle path, but not wider than the 5-rectangle path, so it can be ignored.)

This gives the conditions:

240 + 7 × X = W
254 + 6 × X = W

So for window width 290, that would give:

240 + 7 × X = 290 → X = 7
254 + 6 × X = 290 → X = 6

So path A → C → E → F → I determines the width of the spaces, at 6 pixels.

But for window width 390, that would give:

240 + 7 × X = 390 → X = 21
254 + 6 × X = 390 → X = 22

so now path A → C → E → F → G → J determines the width of the spaces, at 21 pixels.