javascript - 如何水平分布不同大小的矩形？

Question

我有一组不同大小的矩形:

所有矩形都被约束在Y方向，即Y坐标是固定的，只能沿X轴移动。现在，我想以相等的分布间距水平排列所有这些矩形，但其中一些(图片中的灰色矩形)受到左右邻居(红色矩形)的约束，但也受到下面的矩形和以上也是。

编辑:矩形的初始位置按行顺序定义。此外，在我的第一次实现尝试中，我还在每一行中存储了垂直矩形的存在，它们与两行或更多行重叠，如下所示:

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}

我正在寻找一种算法来水平分布所有这些矩形，以便每个最近的矩形的左右间距相同，如图所示。

编辑 2:任何提示如何处理更高的复杂性，也将不胜感激:

Answer 1

使用最左边的坐标从左到右对矩形进行排序，如下图所示:

然后，从左到右遍历每个矩形，并查看它们左侧的哪些矩形与它们垂直重叠(即，如果您将它们向左移动，它们会碰到哪些矩形)。

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.

使用此信息构建如下图所示的图表。当一个矩形碰到其他几个矩形时，例如E 撞到 A、C 和 D，这些矩形本身是同一分支的一部分，例如A 和 C，然后只将它连接到最右边的矩形，即矩形 C。

然后，将每个矩形的宽度(以像素为单位)存储在图中。然后我们将尝试找到边的权重 X，它表示矩形之间空间的宽度。

为此，我们需要找到许多通过图形的路径。首先，我们搜索最长的路径，即具有最多矩形的路径，而不考虑它们的宽度；在这个例子中是:

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

然后我们检查这些路径中哪一个具有最大的组合宽度:

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

然后我们查看较短的路径，看看它们是否具有更大的宽度:

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

在示例中，较短的路径都没有更大的宽度。如果他们中的一些人这样做了，我们也必须考虑每个长度的最宽路径。事实上，我们只需要查看路径:

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

将这条路径连接到右窗口边缘，使其多出一条边；现在有 7 个宽度为 X 的边。矩形的组合宽度为 240 像素，因此如果窗口是例如450 像素宽，则 X = (450 - 240)/7 = 30 像素。如果要考虑多条路径，您将采用 X 的最小结果。

路径中 X 的最小结果的矩形之间将正好有 X 个像素的空间；其他矩形有一些回旋余地。您可以输入 X 作为图中最长路径的边的权重，然后使用该图进一步计算其他矩形的等间距。或者，您可以将它们放置在距其左侧或右侧邻居 X 处。

---

对于更复杂的情况，假设在示例中矩形 I 的宽度为 90 像素，矩形 H 的宽度为 120 像素。这些将是路径:

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

那么要考虑的路径是:

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

因为它是具有最多 (6) 个矩形的路径中最宽的，并且:

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

因为它是具有 5 个矩形的路径中最宽的，并且比 6 个矩形路径更宽。

(最宽的4矩形路径比6矩形路径宽，但不比5矩形路径宽，可以忽略。)

这给出了条件:

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

所以对于窗口宽度 290，这将给出:

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

因此路径 A → C → E → F → I 确定空格的宽度，为 6 个像素。

但是对于宽度为 390 的窗口，这将给出:

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

所以现在路径 A → C → E → F → G → J 决定了空格的宽度，为 21 像素。