在面板上放置随机的非重叠矩形 [英] Place random non-overlapping rectangles on a panel

问题描述

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

I've a panel of size X by Y. I want to place up to N rectangles, sized randomly, upon this panel, but I don't want any of them to overlap. I need to know the X, Y positions for these rectangles.

算法，有人吗?

编辑:所有 N 个矩形一开始都是已知的，可以按任意顺序选择.这会改变程序吗?

Edit: All the N rectangles are known at the outset and can be selected in any order. Does that change the procedure?

推荐答案

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

You can model this by a set of "free" rectangles, starting with single one with coordinates of 0,0, size (x, y). Each time you need to add one more rectangle, choose one of remaining "free" rectangles, generate new rectangle (with top-left coordinate and size such that it will be fully contained), and split that rectangle as well as any other overlapping "free" rectangle, such that children express remaining free space. This will result in 0 to 4 new rectangles (0 if new rectangle was exactly the size of old free rectangle; 4 if it's in the middle and so on). Over time you will get more and more smaller and smaller free areas, so rectangles you create will be smaller as well.

好吧，不是很详细的解释，在白板上显示更容易.但该模型是我用来为新剪切的 gui 组件查找起始位置的模型；跟踪可用的屏幕块并选择(例如)左侧或最顶部的此类区域很容易.

Ok, not a very elaborate explanation, it's easier to show on whiteboard. But the model is one I used for finding starting location for newly cut'n pasted gui components; it's easy to keep track of available chunks of screen, and choose (for example) left or topmost such area.

这篇关于在面板上放置随机的非重叠矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！