用于在某个区域拟合2D多边形的算法？

说：我有10个不同大小的多边形。我有一个特定大小的区域。

我想知道如何填充该区域中最多边形以及它们如何安装。

注意：根据限制设置可以旋转多边形。

2009-12-01 Atlas

您可以通过http试试你的运气来看待：//mathoverflow.net – Graviton 2009-12-01 08:18:26

多边形可以旋转吗？ – 2009-12-01 10:06:06

一个可能的名字是Packing Problem。它与Knapsack Problem有关。这些问题往往是NP难题，许多需要启发式。如果您可以限制允许的多边形和区域形式，则可能存在针对您的特殊情况的更有效的算法。

2009-12-01 08:19:44

如果所有的多边形都是矩形，并且它们所适合的区域也是一个矩形，那么这将被称为bin-packing，Google会用这些信息压倒你。如果他们不是，那么我想你正在寻找一个bin-packing的变体，而且我想你还有更多的问题是你正在进入一个NP问题，其中“尝试和测试”就是围绕着最好的算法。

2009-12-01 08:24:28

你可以看看在维基百科“舞蹈链”为高德纳的解决精确覆盖问题 - 包括平铺 - 你的问题可以作为铺砖问题

2009-12-01 08:30:13

回答