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

Question

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

有算法可以实现吗？

编辑：所有N个矩形在开始时都已知，并且可以以任何顺序选择。这是否改变了程序？

- Scott Evernden

---

http://gamedev.stackexchange.com/questions/6730/how-to-randomly-place-rectangle-inside-a-larger-bounding-rectangle-without-inter - Ciro Santilli OurBigBook.com

Answer 1

您可以通过一组“自由”矩形来建模，从一个单独的坐标为0,0、大小为（x,y）的矩形开始。每次需要添加一个矩形时，选择其中剩余的“自由”矩形之一，生成一个新的矩形（其左上角坐标和大小使其完全被包含），并将该矩形以及任何重叠的“自由”矩形都分割开，以便子矩形表示出剩余的自由空间。这将导致0到4个新矩形（如果新矩形恰好是旧自由矩形的大小，则为0；如果位于中间等，则为4）。随着时间的推移，您将获得越来越多的更小的自由区域，因此您创建的矩形也会变得越来越小。

好的，这不是非常详细的解释，最好在白板上展示。但是，这种模型是我用于找到新剪切并粘贴的GUI组件的起始位置的模型；很容易跟踪屏幕上可用的区块，并选择（例如）最左边或最上方的这样的区域。

- StaxMan

---

我已经实现了这个功能，它运行得非常好。我还添加了合并自由矩形的功能，以避免出现越来越小的问题。 - Tomer Pintel

@TomerPintel，你是如何合并这些自由矩形的？我可以很容易地在视觉上完成它，但无法找出从算法上开始的位置。 - dataduck

@dataduck，对于每个空闲矩形，请遍历所有其他的空闲矩形。检查它们的左侧、宽度是否相等，以及一个矩形的底部是否等于另一个矩形的顶部——如果所有条件都成立，则表示我们有两个上下相邻的空闲矩形。创建一个新的矩形，包含这两个矩形，宽度相同，高度为现有两个矩形的高度之和。从列表中删除旧的矩形，并添加新的矩形代替。 - Tomer Pintel

Answer 2

这是一篇有关2D装箱算法的不错文章：http://www.devx.com/dotnet/Article/36005

通常，您需要使用启发式算法来实现良好的结果。一个简单（但非最优）的解决方案是第一适合算法。

- Jeremy Stanley

---

很遗憾，这篇文章似乎已经下线了，返回了404错误页面。如果有人知道如何找到更新，请编辑回答！ - JBCP

Answer 3

我在我的一个应用程序中使用了这个矩形装箱算法，它的C#源文件可供使用。

该算法以面板的大小初始化，然后您遍历所有矩形并获取它们的位置。矩形的顺序可能会影响结果，具体取决于装箱器。

- devio

Answer 4

我建议你使用StaxMan的建议。

这是我的建议：

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

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

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

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

- Rusty Rob

Answer 5

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

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

- Cyril Gupta

---

每当有人说“应该不难”的时候，他们应该展示代码。 - willc2