如何随机的在一个矩形区域内放置多个大小不同的矩形？

Question

在一个大的矩形里随机的分布多个大小不同的矩形，这些矩形不能重叠。（可能子矩形还未放完，大矩形剩余的空间就不够放下一个小矩形了，但得知道当前到了第几个）

像这样随机分布的小矩形切不重叠，这样子的算法该如何实现。

Answer 1

二维物理引擎了解下, 估计会对你有帮助:

https://github.com/erincatto/...

Answer 2

实现了个取巧简单版的，但不完美。有个完美的解决方案但暂时还没想到怎么实现，这里说下完美的解决方案，希望有高手实现下！

思路：对大矩形中的空间进行切割，在放入第一个小矩形时，大矩形里是空的，那么可以直接放进去，放入第二个小矩形前需要对大矩形的空间进行切割如下图：

在切割完成之后对每个切割后的矩形分块判断是否可以容纳下个小矩形，可以则随机的取一块空间放入，以此类推在放入每个小矩形前都对大矩形进行分割，然后去取一个可以容纳的矩形分块空间放入下个小矩形，如果所有矩形分块都无法放入下个小矩形那么结束该过程。