获取最适合图像中大量像素的矩形宽度和高度值

Question

在不丢失或添加不必要的像素的情况下，计算使像素阵列尽可能接近 rectangle/square 形状所需的大小的最佳方法是什么？

以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的最小结果，也就是找到的值与像素个数的差

虽然它适用于少量像素但具有巨大的值（可能 return 1000x1000 大小），但速度非常慢。

这种缓慢有什么具体原因吗？不使用嵌套 for 循环是否可以得到相同的结果？

Answer 1

以下代码可以提高效率，但它的描述性很强。它需要一个像素数 (n) 和一个表示最佳 k 匹配的 k 值。

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

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));

获取最适合图像中大量像素的矩形宽度和高度值

Getting the most rectangular width and height values that can fit a large amount of pixels in an image

javascript

math

获取最适合图像中大量像素的矩形宽度和高度值

Getting the most rectangular width and height values ​that can fit a large amount of pixels in an image

javascript

math

Getting the most rectangular width and height values that can fit a large amount of pixels in an image