我一直在七个互联网上进行广泛搜索，但无济于事。最接近我需要的似乎是切割库存问题，仅在 2D 中（这令人失望，因为 Wikipedia 没有提供有关如何解决该问题的任何说明）。另一个相似的问题是UV 展开。那里有解决方案，但仅限于您从各种 3D 软件的附加组件中获得的解决方案。
长话短说-我想要的是：给定一个已知宽度和高度的矩形，我必须找出可以在该矩形内放置多少个已知尺寸（可以随意旋转）的形状（多边形）。
例如，我可以选择一个 T 形块并在同一个矩形中以一种有效的方式将它们打包，从而每个矩形有 4 个形状
以及根据它们的边界框平铺它们，在这种情况下我只能适合 3
但是，当然，这只是一个例子……我认为解决这个特殊情况并没有多大用处。我现在能想到的唯一方法要么是回溯它们的复杂性，要么只解决这个问题的特定情况。所以......有什么想法吗？
通过将 t 放入正方形来考虑另一个答案所说的内容，但不要将其保留为正方形，而是将形状设置在列表中。然后使用 True 和 False 将嵌套列表填充为形状，即 [[True,True,True],[False,True,False]] 用于您的 T 形状。然后使用函数将形状放在网格上。要优化结果，请创建一个跟踪器，该跟踪器将注意新形状中有多少错误与先前形状的网格中已有的正确重叠。该函数会将形状放置在重叠最多的位置。必须进行修改以创建越来越高的优化，但这是您正在寻找的一般前提。
有人愿意玩俄罗斯方块游戏（你的问题的一个子集）吗？
这被称为包装问题。在不知道您可能提前面对什么样的形状的情况下，即使不是不可能，也很难想出一个可以为您提供最佳答案的算法。除非您的多边形是“漂亮”的多边形（圆形、正方形、等边三角形等），否则您很可能不得不接受一种启发式方法，在大多数情况下为您提供近似的最佳解决方案。
一种通用的启发式方法（尽管远非最佳取决于输入多边形的形状）是通过在多边形周围绘制一个矩形来简化问题，这样矩形就足以覆盖多边形。（作为下图中的示例，我们在蓝色多边形周围绘制了一个红色矩形。）
完成此操作后，我们可以获取该矩形并尝试将尽可能多的该矩形放入大矩形中。这将问题简化为一个矩形包装问题，更容易解决和绕开你的脑袋。以下链接提供了一个算法示例：
现在显然，当所讨论的多边形与矩形的形状不接近时，这种启发式方法并不是最佳的，但它确实为您提供了一个最小的基线，尤其是如果您对多边形的外观不太了解时像（或者多边形看起来会有很大差异）。使用这个算法，它会像这样填充一个大矩形：
这是没有中间矩形的相同图像：
对于这些 T 形多边形的情况，启发式算法并不是最好的（事实上，对于这个提议的近似来说，它可能几乎是最坏的情况），但它对于其他类型的多边形效果很好。