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

我有一个大小为X的面板Y.我想放置N个矩形,随机大小,在这个面板上,但我不希望它们中的任何一个重叠.我需要知道这些矩形的X,Y位置.

算法,有人吗？

编辑:所有N个矩形在开始时都是已知的,可以按任何顺序进行选择.这会改变程序吗？

您可以通过一组"自由"矩形对此进行建模,从单个坐标为0,0,大小(x,y)开始.每次需要再添加一个矩形时,选择剩余的"自由"矩形之一,生成新的矩形(左上角坐标和大小,使其完全包含),并拆分该矩形以及任何其他重叠"免费的"矩形,让孩子们表达剩余的自由空间.这将导致0到4个新的矩形(如果新的矩形正好是旧的自由矩形的大小,则为0;如果它在中间,则为4,依此类推).随着时间的推移,您将获得越来越多越来越小的自由区域,因此您创建的矩形也将更小.

好的,不是一个非常精细的解释,它更容易在白板上显示.但是这个模型是我用来寻找新切割的gui组件的起始位置的模型; 可以很容易地跟踪可用的屏幕块,并选择(例如)左侧或最顶层的区域.

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

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