平铺（可扩展）堆叠算法

Question

问题就在这里。我有尺寸为 1 的矩形画布。因此它的坐标系为 (0.0 ... 1.0 - x 和 0.0 ... 1.0 - y)。

我也有一些瓷砖。瓷砖也是矩形的。它们具有不同的尺寸，并且瓷砖的数量是可变的。

我想在矩形画布中堆叠图块，从0.0到1.0（从左到右，从上到下）：

1）图块必须适合画布（但填充尽可能多的空间）

2）必须缩放图块（如果它们不适合），每个图块应缩放相同的量（它们必须保持相同的比例）。

3) 想象你手里有这个“图块”，然后将它们一个接一个地放入画布中

4) 它几乎像“TreeMap 算法”，但是 - 图块的形状必须相同（矩形）并且我不需要填充画布的所有空间

有没有人可以向我展示任何类似 C 的语言（C、C++、Java、C#）的算法？

*我尝试过这个。

1）我计算了瓷砖的面积，然后我计算了瓷砖面积的总和（例如：我有两个瓷砖，一个面积为2，另一个面积为1，它们意味着我的总和为3）

2）然后我计算每个图块在“面积总和”中的“比例”（例如：2/3 和 1/3）

3) 然后通过 Math.sqrt(x) 计算矩形图块的大小（例如：Math.sqrt( 2/3))

4) 然后一张一张地绘制图块...

但这并不总是有效。有时我的瓷砖会脱离画布..*

Answer 1

我不确定这是否是您想要的，但您可以查看 TreeMap 算法。

维基百科定义

C++ 实现

Answer 2

这可能看起来是一个包装问题，但是如果我们尝试完全按照它所描述的方式解决这个问题，则事实并非如此。换句话说，没有解决方案，因为问题的描述再次没有问题。如果我们只有一个盒子和一组固定的瓷砖，并且要求它们都必须适合盒子，那么就没有优化的空间。
我可以看到几个相关的优化问题：

1. 给定一组固定的瓷砖，必须将其包装到相同或不同尺寸的盒子中，找到最佳包装顺序，以便使用最少数量的盒子。

2. 给定任意大小的单个盒子和一组图块，找到可以放入盒子中的最佳（最大）图块集。

3. 给定一个盒子和一组瓷砖 - 回答问题是否可以将它们放入盒子中。

您想解决其中哪一个问题？

现在设置问题的方式是没有意义的，因为无论你以哪种顺序将瓷砖放入盒子中，它们总是会使用相同的空间，无论它们如何排列，当然，只要它们全部适合。

Answer 3

尝试蒙特卡罗算法：

Repeat until result is good enough or until you aren't seeing any improvement
  Select (with removal) a random first tile
  Place the first tile at a random position
  Repeat until no remaining tiles
    Select (with removal) a random tile
    Place it adjoining to the existing "tile blob" 
      (you might have to do a search here to find the best place to plug it in)
  Check to see if you have a new best filled-area percentage

所有随机图块选择都应按图块面积进行加权，以便您倾向于首先放置较大的图块。

Answer 4

我不认为这是一个（装箱）装箱问题，因为我为一维装箱问题编写了一个问题。我认为这里的问题是通过 2D-cutting-stock 问题解决的，也许还有 2D-bin-packing 问题。您想要的也是尝试背包问题。这个问题很难解（NP），无解。这有点像旅行推销员问题，解决方案的数量与城市的数量呈指数关系。如果您可以将复杂度降低为一维问题，您可以尝试我在 phpclasses.org 上的装箱算法。

Answer 5

正如其他人指出的那样 - 问题描述不是很清楚。但我假设您可以根据需要缩放每个图块（至少您的示例表明图块缩放是可能的）。所以我的解决方案很简单（但可能不是您想要的也不是最佳的）：

• 按因子缩放每个图块：

  EDGEspace / (EDGEtile * N ½)

• 将每个图块放置在当前行中，如果图块超出空间限制 - 前进到下一行。

这里N是最接近完全平方大于或等于总数的瓷砖。

ps 如果您需要在图块之间留出一些间距 - 只需将上述比例因子设置得小一点即可。

希望有帮助。