获取最多的矩形宽度和高度值​其可以在图像中拟合大量像素

Question

在不丢失或添加不必要像素的情况下，计算将像素阵列放入尽可能接近矩形/正方形的图像所需的大小的最佳方法是什么？

以100个像素的图像为例，适合所有像素的最佳尺寸为10x10，因为10*10是100，也就是说，它添加了最少的额外像素(在这种情况下为0(。100x1也适用于所有像素，但它肯定比10x10的矩形小得多。

为了适应101个像素，最佳尺寸是8x13，尽管8*13是104，但这是唯一一个不损失任何像素、添加很少额外像素(3(、形状最矩形的乘法。

到目前为止，我已经能够用以下规则解决这个问题：

• 宽度除以高度必须得到大于0.5的值，并且小于1.5。(这将确保只有最矩形的值​​保留(
• 宽度与高度相乘的值必须大于或等于像素的数量

通过应用这些规则，我最终得到了各种可能性，最好的是当相乘时，最接近像素数的可能性。

以下是我的代码当前的样子：

function loopPixels(pixels, callback) {
    for (let x = 2; x < pixels; x++) {
        for (let y = 2; y < pixels; y++) {
            callback(x, y);
        }
    }
}
function getRectangle(pixels) {
    let result = {extraPixels: pixels};
    loopPixels(pixels, (left, right) => {
        let half = (left/right);
        let total = (left*right);
        if (Math.round(half) == 1 && total >= pixels) {
            if (total-pixels < result.extraPixels) {
                result = {size: [left, right], extraPixels: total-pixels}; 
            }
        }
    })
    return result;
}
getRectangle(101) // must return [[8, 13], 3] (width, height and additional pixels)

它所做的是保持一个变量包含(width*height)-pixels的最小结果，即所找到的值之间的差​​以及像素的数量。

尽管它适用于少量像素，具有巨大的值(可能返回1000x1000大小(，但它的速度非常慢。

如此缓慢有什么具体原因吗？在不使用嵌套for循环的情况下，有可能得到同样的结果吗？

Answer 1

下面的代码可以提高效率，但它具有很强的描述性。它采用像素计数(n(和表示最佳k匹配的k值。

让我们尝试68M像素以获得一些合理的纵横比。

function getReasonableDimensions(n,k){
  var max = ~~Math.sqrt(n);
  return Array.from({length: max}, (_,i,a) => [n%(max-i),max-i])
              .sort((a,b) => a[0] - b[0])
              .slice(0,k)
              .map(t => [Math.floor(n/t[1]), t[1]]);
}
var res = getReasonableDimensions(68000000,10)
console.log(JSON.stringify(res));