algorithm - 在大小可变的平面上随机分布各种大小的矩形(考虑密度)

Question

我正在寻找一种算法，该算法在容器矩形内随机分布多个矩形(由它们的宽度和高度定义)。后者不是由大小定义的，而是由纵横比定义的。 必须还有一个变量决定结果的密度，或者说:两个矩形的平均距离。 所有的矩形都要放，这是可以的，因为容器没有大小限制。并且任何矩形都不能重叠。

最终结果应该是每个矩形的确定位置以及使用的平面本身的大小。

不幸的是，直到现在我都找不到执行此操作或其中一部分的算法。如果有任何建议、评论或引用，我将不胜感激!事实证明，主要问题是跟踪“空闲空间”列表，该列表在每次放置后相应地更新。

在我需要这个的实际情况下，给定的矩形不是完全随机形状的。它们具有几乎相同的高度，并且往往比高度更宽:它们只是从文本中提取的单词，应该像“云”一样分布在平面上。

Answer 1

这里有一些关于如何设计算法的想法:

• 由于实际矩形的大小相似，您可以将它们分组成行并将多行堆叠起来以获得最终布局
• 使用 rowCount * colCount == totalCount 和 colCount/rowCount == aspectRatio 来估算每行和每列中的矩形数量
• 要确定放置矩形后剩余的可用空间，请计算所有矩形边界框的面积并减去各个矩形面积的总和。这是可行的，因为矩形不重叠。
• 也许 totalFreeSpace 与 boundingBoxArea 的比率可以为您提供所需的密度。如果不是，则 O(n^2) 算法应该有助于根据问题描述计算密度(假设总矩形数不太大)。
• 完成上述工作后，您可以调整一些东西来改善云的形状。例如，对每一行进行排序，使最大的矩形位于中心。