c++ - “移动家具”：二维空间中的碰撞分辨率（非旋转可收缩二维矩形）

Question

在二维空间中，我们有一组矩形。

这是一张图片：

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

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

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

有两个问题：

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

其他并发症：

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

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

我该怎么做？

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

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 平行的空间，并且可以缩小那么多。