algorithm - 有障碍物的二维包装

Question

有人知道在包含障碍物的正方形中移动矩形的有效算法吗？

矩形：

• 可以旋转
• 可以移动/传送
• 不得与障碍物碰撞（黑色方块）

障碍：

• 无法移动
• 可以在任何地方添加

目标：当添加障碍物时，尝试移动矩形，使其不会与任何障碍物发生碰撞。

Answer 1

看看这个：动态编程 - 最大方块
基本上，给定矩形，您添加一个障碍物，然后移除障碍物干扰的正方形。
然后，运行链接算法（“限制器”是障碍物和现有正方形），如果找到可以容纳 NxN 大小的正方形（N 是矩形的大部分）的地方，并添加矩形） .
这可以进一步优化，我委托你这样做。（基本上 - 矩形并不总是放在最佳位置。至少在某种程度上可以补救）
该解决方案将为您添加的每个障碍物提供 O(n) 时间和空间。
您还应该考虑可能的修改：不要为每个障碍物重建阵列，而是为 void-of-obstacles 阵列构建它，并在进行时对其进行修改。这将节省每个障碍物通过整个阵列。