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

3

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

enter image description here

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

更多图表


矩形集合的初始状态是什么?在初始状态下,有些矩形会重叠吗? - sarasvati
@sarasvati:请看我的编辑 - 没有一个矩形可以重叠。 - deblocker
如果我理解你的问题正确,听起来你需要实现一个布局约束求解器。你可能值得一看Grid Style Sheets - sarasvati
通常会有多少个矩形? - m69 ''snarky and unwelcoming''
1个回答

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

rectangles

然后,从左到右迭代每个矩形,看看它们与哪些在它们左侧的矩形在垂直方向上重叠(即,如果将它们向左移动,它们会碰到哪些矩形)。
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。

rectangle graph

然后,将每个矩形的宽度以像素为单位存储在图表中。然后我们将尝试找到边的权重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的最小值。

rectangle graph 2

路径中具有最小结果的矩形将恰好在它们之间有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像素。

侵蚀我的大脑的是如何找到图中的所有路径... - deblocker
@deblocker 寻找图中的路径是一个经过深入研究的主题;在这里你会发现成千上万个关于此的问题和答案。 - m69 ''snarky and unwelcoming''
1
我必须承认,你的解释是我在网上搜索中找到的最好、最详细的。 - deblocker
我花了将近24小时才完全消化你的解释... 你能否请检查我的第二次编辑? - deblocker
1
@deblocker 实际上,第二个例子并不比第一个更复杂,因为它由三个独立的区域组成:上半部分(原始示例),中间的小块线和下半部分。每当您可以画一条水平线,从左窗口边缘到右窗口边缘,而不触及任何矩形时,这将把矩形划分为可独立解决的单独问题。 - m69 ''snarky and unwelcoming''
显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接