将网格分割成随机大小的矩形
我有一个 500 x 400 像素的正方形，里面有一个 100 像素的网格。现在我想用与网格对齐的较小的随机大小的正方形填充该正方形。这意味着较小的正方形的大小可以是 100、200、300 或 400 像素。它们的大小和位置需要是随机的，因此每次运行时输出看起来都会不同。
该图像显示了大正方形、其网格以及我尝试创建的较小正方形的可能输出。
我正在 Ruby / Sinatra 中用 DIV 生成这个，但我想这个问题对于实际算法来说更普遍使用。
关于如何用最少的代码来做到这一点有什么建议吗？
I have a 500 x 400px square with a 100px grid inside it. Now I want to fill that square with smaller random sized square that snap to the grid. This means that the smaller squares can be either 100, 200, 300 or 400 pixels in size. Their size and position needs to be random, so the output will look different every time it runs.
This image shows the large square, its grid, and a possible output with the smaller squares that I'm trying to create.
I'm generating this in Ruby / Sinatra with DIV's, but I guess the question is more general towards the actual algorithm to use.
Any suggestions on how to do this with the least amount of code?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（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
This method would take a lot of code, but I think what I would do is using Donald Knuth's Dancing Links algorithm (DLX) (or some other algorithm) to find all possible arrangements of squares. You can compute the arrangements ahead of time, then you can quickly/randomly pick one later when you need them.
You can read his paper about the algorithm and its application to pentominoes (which is very similar to your problem) here:
http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz
http://en.wikipedia.org/wiki/Dancing_Links
您可以采用一种简单的递归方法来产生相当好的随机分布，其工作原理如下：作为基本情况，任何 100x100 的网格都必须填充 100x100 的正方形。否则，如果某个 n 的网格为 nxn，且足够小以容纳一个正方形，则您可以选择用该大小的正方形对其进行平铺。否则，选择大小不是 100 的矩形的某些边，选择一些 100 倍数的随机位置，然后将其分成两半并递归平铺两半。
这种方法的主要优点是您永远不必跟踪旧矩形的放置位置以避免碰到它们。您始终使用空矩形，并以确保区域永远不会重叠的方式不断递归地细分问题。
这可能并不总是给出好的结果，但它很容易编写代码（我假设总共可能有 15-25 行代码）并且可以轻松地进行调整以更改输出。
希望这有帮助！
One simple recursive approach you could take that would produce a fairly good random distribution works like this: as a base case, any grid that is 100x100 must be filled with a 100x100 square. Otherwise, if the grid is n x n for some n that's small enough to hold a square, you may choose to tile it with a square of that size. Otherwise, pick some side of the rectangle that isn't of size 100, pick some random place that's a multiple of 100, then split it in half and recursively tile both halves.
The main advantage of this approach is that you never have to keep track of where you've put older rectangles to avoid hitting them. You always work with empty rectangles and keep recursively subdividing the problem in a way that ensures that the regions never overlap.
This may not always give good results, but it's very easy to code up (I'd assume maybe 15-25 lines of code total) and can easily be tweaked to change the output.
Hope this helps!