将区域分成给定数量的正方形

Question

我有一个可以被用户调整大小的DIV元素。在这个DIV中，我想画出给定数量的正方形。现在我需要找出正方形的完美边长，使得它们全部适合DIV而不会溢出。

目前我已经做到了以下几点：

function CalcSize (){
    var number = 23; // Example-Number
    var area = jQuery('#container').height() * jQuery('#container').width();
    var elementArea = parseInt(area / number);
    var sideLength = parseInt(Math.sqrt(elementArea));
    return sideLength;
}

这使得正方形太大，因为它没有“丢弃”无法用正方形填充的空间。搜索此问题时，我发现了装箱问题和树状图，但两者都没有帮助我解决我的问题，因为老实说，我缺乏数学技能，并且据我所知，这些解决方案允许非正方形和旋转。

谢谢！

更新:

我目前使用一种非常粗糙的方法来调整正方形的大小，即不断调整它们的大小并查看是否溢出。这种方法可以给出正确的结果，但性能很差。我相信可以通过计算来实现这一点。

- Fjonan

---

你的父级 div 的宽度和高度是否相等？ - Prasath K

还有，“perfect side length”是什么意思？是指最大的边长吗？你意识到并不总是可能的，例如当数字=5时，你将无法用两行正方形填充矩形。 - ile

如果 jQuery('#container').height() 返回一个像 997 这样的质数，会怎么样？ - Tom Chung

我更新了帖子，并附上了屏幕截图的链接。我所说的“丢弃”是指我的当前不起作用的解决方案似乎没有考虑到有未填充的空间。关于质数：在我的计算中，我是否可以通过将高度/宽度的数字减一来考虑质数？ - Fjonan

我觉得你仍然需要一个循环，虽然肯定比暴力破解好。 - ile

Answer 1

这里有一个算法，它将使用整个宽度，所有未使用的空间将在底部。这并不总是会给出最大可能的正方形，但它将以一致的方式运行并且应该看起来很好。

请注意，while循环通常不应超过一到两次迭代。

function CalcSize (){
    var number = 23; // Example-Number
    var width = jQuery('#container').width();
    var height = jQuery('#container').height();
    var area = height * width;
    var elementArea = parseInt(area / number);

    // Calculate side length if there is no "spill":
    var sideLength = parseInt(Math.sqrt(elementArea));

    // We now need to fit the squares. Let's reduce the square size 
    // so an integer number fits the width.
    var numX = ceil(width/sideLength);
    sideLength = width/numX;
    while (numX <= number) {
        // With a bit of luck, we are done.
        if (floor(height/sideLength) * numX >= number) {
            // They all fit! We are done!
            return sideLength;
        }
        // They don't fit. Make room for one more square i each row.
        numX++;
        sideLength = width/numX;
    }
    // Still doesn't fit? The window must be very wide
    // and low.
    sideLength = height;
    return sideLength;
}

- Klas Lindbäck

---

非常好用！底部未使用的空间实际上非常适合我的（在问题中没有明确说明的）使用情况，在运行时添加元素非常方便。非常感谢所有帮助我的人。 :) - Fjonan

Answer 2

根据图片，我做了一个假设，即只要长度最大化，您可以接受垂直和水平未使用的空间。

基本上这是一个线性规划问题（实际上是整数规划问题）。我们有以下不等式，我们想要最大化长度。

行、列和长度是未知数；而 n、宽度和高度是已知的：

rows >= 1
cols >= 1
rows*cols >= n
rows*length <= height
cols*length <= width
maximize length

从最后三个方程式中，您得到了正确的估计值：长度 <= sqrt(height*width/n)。但是，您仍需要循环遍历可能的范围以获取整数值。不过，您可以使用二分查找来加快速度。

- ile

---

我必须琢磨这个想法。Klas的答案非常接近我想要的。现在关键是看个人需求。上面的答案没有使用很多循环运行，而且 - 在视觉上 - 将正方形适配到了宽度。我现在采用那个方法，但你的答案也接近我目前使用的方法。非常感谢您的反馈！ - Fjonan