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

Question

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

3

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

所有矩形在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：如何处理更高复杂度的提示，也将不胜感激：

- deblocker

矩形集合的初始状态是什么？在初始状态下，有些矩形会重叠吗？ - sarasvati

@sarasvati：请看我的编辑 - 没有一个矩形可以重叠。 - deblocker

如果我理解你的问题正确，听起来你需要实现一个布局约束求解器。你可能值得一看Grid Style Sheets。 - sarasvati

通常会有多少个矩形？ - m69 ''snarky and unwelcoming''

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，

- m69 ''snarky and unwelcoming'' · Accepted Answer

将矩形按照它们最左边的坐标从左到右排序，如下图所示：

然后，从左到右迭代每个矩形，看看它们与哪些在它们左侧的矩形在垂直方向上重叠（即，如果将它们向左移动，它们会碰到哪些矩形）。 A 和 B 到达左边窗户而不会碰到任何其他矩形。
C 碰到了 A。
D 碰到了 B。
E 碰到了 A、C 和 D。
F 碰到了 B、D 和 E。
G 碰到了 D、E 和 F。
H 碰到了 A、C 和 E。
I 碰到了 B、D 和 F。
J 碰到了 D、E、F 和 G。使用这些信息构建如下所示的图形。当一个矩形碰撞到多个其他矩形时，例如 E 碰到了 A、C 和 D，并且这些矩形本身属于同一个分支，例如 A 和 C，则只将其连接到最右侧的矩形，即矩形 C。

然后，将每个矩形的宽度以像素为单位存储在图表中。然后我们将尝试找到边的权重X，它表示矩形之间空白的宽度。为此，我们需要在图表中找到多条路径。首先，我们搜索最长的路径，即不考虑它们的宽度的路径，例如：左窗口边缘 → A → C → E → F → G → J 左窗口边缘 → B → D → E → F → G → J 然后，我们检查哪一条路径具有最大的组合宽度：左窗口边缘 → A → C → E → F → G → J = 240 然后，我们查看较短的路径，看看它们是否具有更大的宽度：左窗口边缘 → A → C → E → F → I = 230 左窗口边缘 → B → D → E → F → I = 220 左窗口边缘 → A → C → E → H = 168 左窗口边缘 → B → D → E → H = 158 在这个例子中，没有任何一条更短的路径具有更大的宽度。如果有一些路径具有更大的宽度，我们也必须考虑每个长度的最宽路径。现在，我们只需要看这条路径：左窗口边缘 → A → C → E → F → G → J = 240 将这条路径连接到右窗口边缘，使其多出一条边；现在有7条宽度为X的边。矩形的总宽度为240像素，因此，如果窗口宽度为450像素，则X = (450-240) / 7 = 30像素。如果有几条路径需要考虑，您将选择X的最小值。

路径中具有最小结果的矩形将恰好在它们之间有X像素的空间；其他矩形则有一些余地。您可以将X输入为图中最长路径中边的权重，然后使用图来进一步计算其他矩形的等距离间距。或者，您可以将它们与它们的左侧或右侧邻居相距X。

对于更复杂的情况，假设在示例中矩形I宽90像素，矩形H宽120像素。这些将是路径： 6个矩形：左窗口边缘 → A → C → E → F → G → J = 240 左窗口边缘 → B → D → E → F → G → J = 230 5个矩形：左窗口边缘 → A → C → E → F → I = 254 左窗口边缘 → B → D → E → F → I = 244 4个矩形：左窗口边缘 → A → C → E → H = 250 左窗口边缘 → B → D → E → H = 240 然后要考虑的路径是：左窗口边缘 → A → C → E → F → G → J = 240 因为它是拥有最多（6）矩形的最宽路径，以及：左窗口边缘 → 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像素。