无重叠随机放置的矩形 [英] random placement of rectangles with no overlaps
问题描述
我要寻找一个完善的算法，将随机放置相同大小的矩形给定数量变成一个更大的矩形（画布）。
I am looking for a sound algorithm that would randomly place a given number of rectangles of the same size into a bigger rectangle (canvas).
我看到两种方法可以做到这一点：
I see two ways to do it:
-
创建一个空的数组将包含已放置在画布上的矩形。先从空白的画布。在一个循环中，选择一个位置随机一个新的矩形放置。检查数组有一个新的矩形重叠的矩形。如果不是这样，就把新的矩形在至阵列，并重复循环。否则，选择一个新的位置，并重新运行检查。等等。这可能永远无法终止（理论上），我认为。我不喜欢它。
create an empty array that will contain the rectangles already placed on canvas. start with the empty canvas. in a loop, pick a position at random for a new rectangle to be placed. check if the array has a rectangle that overlaps with the new rectangle. if it does not, put the new rectangle in to the array and repeat the loop. otherwise, pick a new position, and rerun the check again. and so on. This might never terminate (theoretically) I think. I do not like it.
使用网格和地点矩形进入细胞随机。这可能仍然看起来像一个网格布局。我不喜欢它。
use a grid and place rectangles into the cells randomly. This might still look like a grid placement. I do not like it either.
什么更好的方式来做到这一点？ 更好的意思更高效，更直观地随机比格的做法。在任何方面更好。
any better ways to do it? "better" meaning more efficient, or more visually "random" than the grid approach. better in any respect.
谢谢 康斯坦丁
推荐答案
下面是一个简单的规则。这将是不重叠的和随机的。
Here is a simple heuristic. It will be non-overlapping and random.
将一个矩形随机。然后，计算与画布的边缘所述第一矩形的两个平行的边缘的延伸部分的交叉点。您将获得四个凸形空区。将其他矩形在这些空地区的一个接一个独立计算类似部门的展示位置。并尝试把剩余的矩形空区。
Place a rectangle randomly. Then, calculate the intersections of extensions of the the two parallel edges of the first rectangle with the edges of the canvas. You will obtain four convex empty regions. Place other rectangles in these empty regions one-by-one independently and calculate the similar divisions for placements. And try to put the remaining rectangles in empty regions.
您可以尝试不同的策略。你可以尝试把靠近角落的矩形。或者，你可以把它们周围的区域的中心。我们不能讨论最优，因为你介绍随机性。
You can try different strategies. You can try to place the rectangles close to the corners. Or, you can place them around the center of the regions. We cannot discuss optimality because you introduced randomness.
这篇关于无重叠随机放置的矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
