有这方面的标准吗？算法名称？
说：我有 10 个不同大小的多边形。我有一个特定大小的区域。
我想知道如何填充该区域中最多的多边形，以及它们是如何安装的。
注意：多边形可能会根据限制设置旋转。
问问题
2223 次
3 回答
6
一个可能的名称是Packing Problem。它与背包问题有关。这些问题往往是 NP 难的，并且许多需要启发式。如果您可以限制允许的多边形和区域形式，则可能存在针对您的特殊情况的更有效的算法。
于 2009-12-01T08:19:44.710 回答
2
您可以查看 Wikipedia 中的“Dancing Links”，了解 Donald Knuth 对确切封面问题的解决方案 - 包括平铺 - 您的问题可以视为平铺问题
于 2009-12-01T08:30:13.783 回答
1
如果（如果）你所有的多边形都是矩形，并且它们要适应的区域也是一个矩形，那么这将被称为装箱，谷歌会用有关这方面的信息来压倒你。如果不是，那么我猜您正在寻找装箱的变体，并且我猜您更多的是陷入 NP 问题，其中“尝试和测试”是最好的算法。
于 2009-12-01T08:24:28.087 回答