适应空间的算法

Question

我有一组不同大小的正方形和矩形，想要使用PHP组合在一起，形成一个大的正方形/矩形。这些正方形通常是图像，我想将它们制作成蒙太奇 - 但有时它们只是数学对象。

是否有任何PHP算法可以实现这个功能？这种类型的问题叫什么？

更新：在进一步搜索后，我认为我想要的是称为装箱问题的东西。然而，对于某些类型的装箱问题（如图像），我还想添加一定量的随机性，以增加人类兴趣。

- Xeoncross

---

这些对象的大小是否固定不变...即您想找到适合定义的“框”的图像范围。还是您想将这些图像按比例缩放到预定义的框中？ - diagonalbatman

我认为这个问题非常接近我所需要的内容：https://dev59.com/lW445IYBdhLWcg3wWZAU - Xeoncross

有算法，也有为特定编程语言（如PHP）实现这些算法的版本。我建议将这个问题设计成与编程语言无关的形式，因为它非常有趣。 - Karoly Horvath

如果你需要一些数学方面的帮助，可以去math.stackexchange.com上寻求数学专家的建议。 显然他们也已经讨论了一段时间了：math.stackexchange.com搜索装箱问题。 - Andresch Serj

看看服装行业，那里优化地将不同尺寸的图案拼接在布料上是一项重要任务，还有木材行业，他们将切割件嵌入原木中。 - Patrick Hughes

Answer 1

2D装箱问题是NP难问题。然而，存在近似算法。

看看这段代码（和解释）。它包含多个算法，并且有一个GUI： 解决2D装箱问题

- Petar Ivanov

---

抱歉得分减一，但链接的网站要求您注册并登录才能查看内容，这通常不是问题，但他们要求填写地址、公司、公司规模等信息。这些信息对于一个答案来说是无必要的。 - Loktar

Answer 2

我在PHP中编写了一个一维装箱算法。你可以寻找最佳适配，首次适配等方案。但这不适用于二维问题，也许你应该考虑背包问题？

- Micromega

---

我找到了一个PHP版本的背包问题，但我还不确定它如何与填充2D区域相关。 - Xeoncross

@Xeon：至少你有一个包含两个变量，重量和成本的算法。也许你可以修改它？另一个应用是drools-planer。 - Micromega

问题在于该公式仅使用一个约束条件和一个优先级，因此它只是一个华丽的一维算法。我需要处理两个约束条件（可选优先级）的算法。 - Xeoncross

@Xeon：我明白了，你尝试过 Floyd-Warshall 算法或 Edmond 最大匹配算法吗？ - Micromega

@Xeon：也许可以使用空间索引或四叉树？空间索引可以将二维复杂度降低到一维复杂度。 - Micromega

@Xeon：你想要看一下Nick关于空间索引四叉树希尔伯特曲线的博客。 - Micromega

Answer 3

我认为你可以使用模拟退火算法。我曾经用它来填充矩形广告在矩形报纸页面上。正如你所说，你可以从随机解开始，然后慢慢地达到一个好的解决方案。请参见这里http://codetuner.blogspot.com/2010/03/simulated-annealing-approach-to.html。我曾经用它来解决分页问题。我认为你也可以将其用于你的需求。

- Jayantha Lal Sirisena