将网格分割成随机大小的矩形。

Question

我有一个500 x 400像素的正方形，在里面有一个100像素的网格。现在我想用随机大小的小正方形填充该正方形，并使其与网格对齐。这意味着小正方形的大小可以是100、200、300或400像素。它们的大小和位置需要是随机的，所以每次运行时输出都会不同。

下图显示了大正方形、它的网格和可能的小正方形输出。

我是用DIV在Ruby / Sinatra中生成的，但我想问题更普遍一些，实际上是使用什么算法来实现的。

有没有建议如何用最少的代码完成此操作？

- Ronze

---

给定一个正方形，可以放置它的位置是有限的。如果您不担心速度：生成随机正方形大小，最大值为某个值；获取所有可能的放置位置；随机选择一个位置并将其放置。如果没有可行的位置，则减小最大尺寸。 - Timbits

Answer 1

一个简单的递归方法可以产生相当好的随机分布，具体做法如下：作为基本情况，任何100x100的网格必须填充一个100x100的正方形。否则，如果网格是n x n（其中n足够小以容纳一个正方形），则可以选择使用该大小的正方形平铺它。否则，选择矩形的某个不是100大小的边，选择某个是100的倍数的随机位置，然后将其分成两半并递归平铺两个部分。

这种方法的主要优点是您永远不必跟踪您放置旧矩形的位置以避免撞到它们。您始终使用空矩形并以确保区域永远不重叠的方式递归地细分问题。

这种方法可能并不总是产生良好的结果，但很容易编写代码（我估计总共可能需要15-25行代码），并且可以轻松调整以更改输出。

希望这有所帮助！

- templatetypedef

Answer 2

这个方法可能需要很多代码，但我想我会使用唐纳德·克努斯（Donald Knuth）的Dancing Links算法（DLX）（或其他算法）来找到所有可能的正方形排列。您可以提前计算这些排列，然后在需要时快速/随机地选择其中一个。

您可以在此处阅读他关于该算法及其应用于五格拼图（与您的问题非常相似）的论文：

http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz

http://en.wikipedia.org/wiki/Dancing_Links

- David Grayson