在面板上随机放置不重叠的矩形

Question

我有一个尺寸为 X x Y 的面板。我想在此面板上放置最多 N 个大小随机的矩形，但我不希望它们中的任何一个重叠。 我需要知道这些矩形的 X、Y 位置。

算法，有人吗？

编辑：所有N个矩形一开始都是已知的，可以按任何顺序选择。 这会改变程序吗？

Answer 1

您可以通过一组“自由”矩形对其进行建模，从坐标为 0,0、大小为 (x, y) 的单个矩形开始。 每次您需要再添加一个矩形时，请选择剩余的“自由”矩形之一，生成新矩形（具有左上角坐标和大小，以便将其完全包含在内），然后拆分该矩形以及任何其他重叠的“自由”矩形，以便孩子们表达剩余的自由空间。 这将产生 0 到 4 个新矩形（如果新矩形与旧的空闲矩形的大小完全相同，则为 0；如果它位于中间，则为 4，依此类推）。 随着时间的推移，您将获得越来越小的自由区域，因此您创建的矩形也会越来越小。

好吧，不是很详细的解释，在白板上更容易显示。 但该模型是我用来查找新剪切和粘贴的 GUI 组件的起始位置的模型； 跟踪可用的屏幕块并选择（例如）左侧或最上面的此类区域很容易。

Answer 2

这是一篇关于 2d 打包算法的不错的文章： http://www.devx.com/dotnet/Article /36005

您通常需要某种使用启发式的算法来获得不错的结果。 一个简单（但非最佳）的解决方案是第一个拟合算法。

Answer 3

我使用了这个 矩形打包算法 在我的一个应用程序中，可作为 C# 源文件使用。

该算法使用面板的大小进行初始化，然后迭代所有矩形并获取它们的位置。 矩形的顺序可能会影响结果，具体取决于打包程序。

Answer 4

我建议你使用 StaxMans 的建议。

这是我的 2c：

随机添加大量矩形（彼此重叠）。
删除重叠矩形：

for rectangle in list of rectangles:
    if rectangle not deleted:
        delete all rectangles touching rectangle.

要查找接触特定矩形的所有矩形，您可以使用四叉树或基于 x1,y1 x2,y2 值的不等式。

编辑：事实上，大多数游戏引擎（例如 pygame 等）都包含矩形的碰撞检测，这是一个常见问题。

Answer 5

或者维护已添加的矩形列表，并创建一个算法，根据该列表计算出新矩形的放置位置。 您可以创建一个基本的 Rectangle 类来保存有关矩形的信息。

创建自定义算法应该不难。