包装正多边形成方形

我想弄清楚是否给予这些约束普通2D装箱问题可以简化。对于3到12之间的s，您有n个规则的s边多边形。它们都具有相同的边长。我们需要最小化边界平方的面积。包装正多边形成方形

我认为，让所有正规的具有相同的边长的包装可以更容易，因为一些配置总是会伏贴彼此相邻。虽然我不确定这个属性是否有用，因为本地最小值可能不会转化为全局最小值。

2014-02-28 robert3005

这是相当困难的问题平铺它们合并配件广场变成一个大广场常规格子不是4x6瓶啤酒最密集的配置。我会去模拟退火/遗传算法... http://en.wikipedia.org/wiki/Circle_packing_in_a_square –

我认为你有一个解决方案的第一刀是个好主意，但我不认为你”将能够简化程序 - 您可能需要做相反的事情，并在最终算法中尝试几件事来克服局部最小问题。 – patrickvacek

当你说加满，我们如何让填补，我们需要双方是其他多边形的充分接触另一侧，或者我们可以有多边形自行浮动的，或者我们可以有一个单点从可以说，一个三角形的聚感人另一个聚合物的点或侧面没有完整的三面接触另一个完整的聚合面？此外，边界“方形”或矩形，因为那些可能会不同！ – trumpetlicks

从您的描述中，多边形是用具有相同长度

这意味着，每个多边形边可以连接以形成可配合到的2r^2完美

大小的子正方形的圆所有侧面正多边形

所以一个简单的解决方案是安装在方形排列的多边形ň，这不是一个最佳的解决方案，但完美的作品时，你只有方块。

这里是说明它的图：

enter image description here

首先，知道所有多边形的边具有m

长度多边形完美地融入比的圆r

这圈完美地融入尺寸的正方形2r^2

例如 -

enter image description here

因此，我们终于通过在M x M方块矩阵，其中M * M >= N

2014-03-25 08:58:31

回答