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

可以通过一组“自由”矩形对此进行建模,从坐标为0,0、大小(x,y)的单个矩形开始。每次需要再添加一个矩形时,选择剩余的一个“空闲”矩形,生成新的矩形(左上角的坐标和大小使其完全包含),并拆分该矩形以及任何其他重叠的“空闲”矩形,以便子级表示剩余的可用空间。这将导致0到4个新矩形(如果新矩形正好是旧的自由矩形的大小,则为0;如果新矩形在中间,则为4,依此类推)。随着时间的推移,你会得到越来越小的自由区域,所以你创建的矩形也会越来越小。

好吧,不是很详细的解释,在白板上更容易显示。但是这个模型是我用来寻找新剪切粘贴的GUI组件的起始位置的;它很容易跟踪可用的屏幕块,并选择(例如)最左边或最上面的区域。

下面是一篇关于二维打包算法的好文章: http://www.devx.com/dotnet/Article/36005

您通常需要一些使用启发式的算法来获得好的结果。一个简单的(但非最优的)解决方案将是第一个适合的算法。

我用过这个 Rectangle Packing algorithm 在我的一个应用程序中,作为C源文件提供。

算法是用面板的大小初始化的,然后遍历所有的矩形并得到它们的位置。矩形的顺序可能会影响结果,具体取决于封隔器。

我建议你使用斯塔克曼的建议。

这是我的2C:

随机添加大量的矩形(相互重叠)。 删除重叠的矩形:

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

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

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

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

创建一个自定义算法不应该那么困难。