“移动家具”：2d空间中的碰撞分辨率（非旋转可收缩2d矩形）

Question

在2d空间中，我们有一组矩形。

这是一张图片：

右边的垂直线是不可移动的“墙”。左侧的箭头表示移动方向。我需要向左移动最左边的矩形。

1. 矩形不能旋转。
2. 不允许矩形水平重叠。
3. 矩形可以（水平）缩小到某个最小宽度（分别设置为每个矩形）
4. 矩形只能水平移动（左/右）并水平收缩。
5. 最左边的矩形（箭头指向）不能缩小。
6. 宽度和坐标存储为整数。

我需要将最左边的矩形向右移动X个单位，将所有东西推向右边。

有两个问题：

1. 我需要确定我可以向左移动最左边的矩形到多远（可能无法移动X单位）。
2. 将矩形移动X个单位（或者如果无法移动X个单位，移动最大可能的数量，小于X）并获得系统中每个矩形的新坐标和大小。

其他并发症：

您不能将Y坐标和矩形高度用于任何事物，而是每个矩形都有一个矩形列表（实现为指针），如果您继续向右移动它将会击中它，您只能检索x坐标，宽度和最小宽度。此数据模型无法更改。 （从技术上讲，在2d中将其重新表示为一组矩形是简化）

重要提示：来自不同级别和分支的子项可以在“潜在冲突”列表中具有相同的矩形。这是初始图片，指针显示为红线：

我该怎么做？

我知道一种愚蠢的方式（这会起作用）来解决这个问题：迭代地。即

1. 记住系统的当前状态。如果系统的状态已经被记忆，则忘记先前记忆的状态。
2. 将最左边的矩形按下1个单位。
3. 递归解决冲突（如果有的话）。
4. 如果无法解决碰撞，则返回系统的记忆状态。
5. 如果可以解决冲突，并且我们已经被X单位移动，则返回系统的当前状态。
6. 否则，请转到1。

这将解决问题，但如果X很大，这种迭代解决方案可能会很慢。有没有更好的方法来解决它？

Answer 1

想到一个可能的解决方案：

你说每个矩形都有指向它向右移动时会击中的所有物体的指针。我建议，从大矩形（箭头所指的那个）中取出指针列表，取出它所有的节点（它会碰撞的矩形），找到最小宽度，然后对所有子节点做同样的事情，添加递归地每个分支的宽度。像树深度问题一样对待问题。每个节点都有一个最小宽度值，因此您的问题的答案将是墙与大矩形右边缘的x值之间的距离减去矩形最小宽度的最大总和。创建一个向量，其中存储树的每个分支的深度（最小宽度的总和）并找到最大值。距离减去最大值是你的答案。

用4个盒子想象相同的图片。一个在左边，一个在右边，然后在墙上。我们将它们命名为方框1，方框2（中间顶部），方框3（中间底部）和最后一个方框4（右侧）。每个盒子的宽度都是4.除了左边的盒子外，所有盒子都可以收缩。框2可以缩小2，框3可以缩小1，框4可以缩小2.计算2个分支给*分支1：2 + 2 = 4 *分支2：3 + 2 = 5 *仅关注分支2因为分支1比分支2少，因此将适合与分支2平行的空间，并且可以缩小那么多。