algorithm - 将正多边形打包成正方形

Question

我试图弄清楚在给定这些约束的情况下是否可以简化常规的 2D 打包问题。对于 3 到 12 之间的 s，您有 n 个规则的 s 边多边形。它们都具有相同的边长。我们需要最小化边界正方形的面积。

我认为让所有具有相同边长的常规包装可以更容易，因为某些配置将始终完美地贴合在一起。虽然我不确定这个属性是否有用，因为局部最小值可能不会转化为全局最小值。

Answer 1

根据您的描述，多边形是正多边形，所有边的长度都相同

这意味着每个多边形的边都可以连接形成一个圆，该圆可以完美地放入一个大小2r^2为

因此，一个简单的解决方案是将 N 个多边形对齐在 的正方形中size >= N * 2r^2，这不是最佳解决方案，但是当您只有正方形时可以完美地工作。

这是一个解释它的插图：

首先，知道所有多边形边的长度为m

多边形完全适合比例圆r

那个圆圈完全适合一个正方形2r^2

所以我们最终通过将拟合的正方形平铺在一个正方形矩阵中，将它们合并成一个大M x M正方形，其中M * M >= N