我有一个 X x Y 大小的面板。我想在这个面板上放置最多 N 个随机大小的矩形,但我不希望它们中的任何一个重叠。我需要知道这些矩形的 X、Y 位置。
算法,有人吗?
编辑:所有 N 个矩形一开始都是已知的,可以按任何顺序选择。这会改变程序吗?
您可以通过一组“自由”矩形对此进行建模,从坐标为 0,0、大小 (x, y) 的单个矩形开始。每次您需要再添加一个矩形时,选择剩余的“空闲”矩形之一,生成新矩形(具有左上角的坐标和大小,以便完全包含),然后拆分该矩形以及任何其他重叠的“ free”矩形,这样孩子们就可以表达剩余的可用空间。这将产生 0 到 4 个新矩形(如果新矩形正好是旧的空闲矩形的大小,则为 0;如果它在中间,则为 4,依此类推)。随着时间的推移,您将获得越来越小的空闲区域,因此您创建的矩形也会越来越小。
好的,不是很详细的解释,在白板上显示更容易。但是该模型是我用来寻找新剪切粘贴的 gui 组件的起始位置的模型;跟踪可用的屏幕块很容易,并选择(例如)左侧或最上方的此类区域。
这是一篇关于 2d 打包算法的不错的文章:http: //www.devx.com/dotnet/Article/36005
您通常需要某种使用启发式的算法来获得不错的结果。一个简单(但非最佳)的解决方案将是首次拟合算法。
我在我的一个应用程序中使用了这个Rectangle Packing 算法,以 C# 源文件的形式提供。
该算法使用面板的大小进行初始化,然后遍历所有矩形并获取它们的位置。矩形的顺序可能会影响结果,具体取决于打包程序。
我建议你使用 StaxMans 的建议。
这是我的2c:
随机添加一大堆矩形(相互重叠)。删除重叠的矩形:
for rectangle in list of rectangles:
if rectangle not deleted:
delete all rectangles touching rectangle.
要查找接触特定矩形的所有矩形,您可以使用四叉树或基于 x1,y1 x2,y2 值的不等式。
编辑:事实上,大多数游戏引擎(如 pygame 等)都包含矩形碰撞检测,这是一个常见问题。
或者维护一个已经添加的矩形列表,并创建一个算法,根据该列表确定新矩形的放置位置。您可以创建一个基本的 Rectangle 类来保存有关您的矩形的信息。
创建自定义算法不应该那么难。