将正多边形装入正方形

Question

我正在研究这些限制条件下是否可以简化常规的2D装箱问题。您有n个正则的s边形，其中s介于3到12之间。它们的边长都相同。我们需要最小化边框正方形的面积。

我认为，所有边长相同的正则多边形会使装箱更容易，因为某些配置总是可以完美地贴合在一起。但我不确定这个特性是否有用，因为局部最小值可能无法转化为全局最小值。

- robert3005

---

这是一个令人惊讶的难题——例如，对于4x6瓶啤酒，正则网格不是最密集的配置。我会采用模拟退火/遗传算法... http://en.wikipedia.org/wiki/Circle_packing_in_a_square - Aki Suihkonen

我认为你对解决方案的初步构想很不错，但我觉得你可能无法简化程序——相反，你可能需要在最终算法中尝试多种方法来克服局部最小值问题。 - pattivacek

当你说“填充”时，我们可以如何填充？我们需要让多边形的边完全接触其他多边形的边吗？还是我们可以让多边形自由浮动？或者我们可以让三角形多边形的单个点接触另一个多边形的点或边，而不是让整个三角形边接触另一个多边形的整个边？此外，边界“正方形”或矩形，因为它们可能是不同的！ - trumpetlicks

装箱问题不要求物体彼此接触或接触边缘。你可能在想“平铺”。当然，唯一能够平铺正方形的正多边形就是正方形本身。 - Sneftel

在我看来，如果你有不规则或边长不同的多边形，其中一些仍然可以铺砌。只有凹多边形会使任务更加困难。我会从将两个凸多边形放置在另一个凸多边形中开始。这个任务可以用于归纳的起点和步骤。 - Gangnus

@trumpetlicks，多边形之间没有接触或浮动的要求。任何对齐方式都可以接受。我想要最小化边界正方形的面积。所有具有3至12个边的正多边形都是凸的。困难在于你仍然可以有许多不同的配置，并且要探索的可能性数量呈指数增长。 - robert3005

Answer 1

根据您的描述，这些多边形是拥有相同长度的正规多边形。

这意味着每个多边形的边缘都可以连接成一个圆，该圆可以完美地嵌入一个大小为 2r ^ 2 的子正方形中。

因此，一个简单的解决方案是将N个多边形对齐放置在一个 size> = N * 2r ^ 2 的正方形中，尽管这不是最优解，但当你只有正方形时它能完美工作。

下面是一张说明图片：

首先，假设所有多边形的边长都是m 该多边形可以完美地嵌入一个比例为r的圆中

该圆可以完美地嵌入一个大小为2r ^ 2的正方形中

因此，我们通过将它们平铺在一个M x M的矩阵中，其中M * M> = N来将适合的正方形合并到一个大正方形中。

- Khaled.K