4

假设我定义了一些抽象形状，每个形状都有宽度和高度（为简单起见，我们将它们设为矩形）。如何将它们中的尽可能多的放置在定义宽度和高度的单个画布（只是一个术语，不一定是 HTML5 画布）上？

显然这是某种约束满足问题，但我真的不知道从哪里开始（除了蛮力）。谷歌搜索只会出现不相关的结果（可能是因为我不知道要搜索什么）。什么是一个好的算法，或者什么是创建一个算法来做到这一点的好方法？

菲兹就是一个很好的例子。形状（在本例中为圆形）以组的形式出现，并且不会相互重叠，并且不会相互干扰。我的用例更像是一次性定位交易。另一个例子是SpriteRight，它尽可能有效地放置在某些边界内。

4

3 回答 3

1

您的问题可以从有限域（）上的约束逻辑编程中受益。

考虑Prolog 约束处理的问题和答案：Packing squares。它展示了几种方法，其中一种方法使用专用的放置约束来查找 2D 中非重叠矩形的布局。

clpfd 还使您能够强制执行除打包约束之外的其他约束。有支持 clpfd 的免费（例如，和YAP ）和商业（例如，SICStus）实现。

于 2015-04-15T09:43:15.977 回答
0

我找到了一个带有 JavaScript 和 HTML5 画布的开源示例。矩形是随机生成的，然后打包。然而，作者并没有声称效率。

我还发现了一篇看起来很有希望的文章。

于 2012-02-14T14:48:31.427 回答
0

您还可以查看 http://www.aimms.com/downloads/application-examples/circle-packing。这里使用数学规划/建模来解决圆包装问题。也可以定义其他变体。约束编程中存在特殊的装箱约束，http://www.aimms.com/cp。

一般来说，数学规划是解决此类问题的好方法。

于 2012-02-17T11:15:20.423 回答