在另一个矩形内均匀分布矩形所需的算法

Question

我正在寻找一种算法，可以在最小化重叠的同时，在较大矩形内分配不同大小的矩形。

我已经查看了装箱算法，但它们似乎最小化了矩形之间的空白空间（在我的情况下，所有要打包的项都是正方形）。

我想要最大化所有正方形与外部矩形边界之间的距离。

以下是我正在尝试做的示例：

- howardr

---

"最小化重叠"，这意味着它们可以重叠吗？ - Nanne

我猜你想要最大化正方形与外部矩形边界之间的最小距离。 - vitaut

@Nanne 我并不太担心是否存在一些重叠。我假设可能有一个算法可以工作，但无法处理可变大小的正方形。在这种情况下，我会针对中位数或平均大小进行优化。 - howardr

@vitaut 是的，我认为这就是我想做的。即使每个正方形与外部矩形边界之间的“最小距离”最大化。 - howardr

我喜欢这个问题，很想看看其他的解决方法。@howardr，你有这样一个分配的使用案例吗？ - Lazer

@Lazer 这个使用案例是为了工作中的一个项目。我们要在一个大区域内展示一堆名人照片。照片的大小取决于最近关于这位名人的推特引用数量。基本上，我们想确保图像不重叠。随着照片尺寸的变化，我们希望重新安排工作区中的照片。 - howardr

Answer 1

如果您使用像此处描述的算法一样的算法将它们尽可能紧密地打包，然后均匀地扩展以匹配目标包围矩形，会怎样呢？

例如，假设您可以将上面的3个矩形打包到一个3x2的盒子中，而您的外部盒子是7x5。然后取从盒子中心到每个矩形中心的向量，并将x分量乘以(7/3)，y分量乘以(5/2)，这就给出了新的中心点。

- AShelly

Answer 2

这似乎是背包问题的概括。

动态规划将在接近多项式时间内解决它。

- javanix

---

在发布之前，我查看了背包问题，并且认为解决它的一些算法可能会起作用。我想我不知道要优化哪些变量以满足我的主要需求，即在外部矩形内均匀分布正方形（对于我描述问题的非专业术语，我感到抱歉）。 - howardr