What's the best way to calculate the size needed to fit an array of pixels into an image as close as possible to a rectangle/square shape without losing or adding unnecessary pixels?

Using an image of 100 pixels as an example, the best size to fit all pixels would be 10x10, because 10*10 is 100, that is, it adds the least amount of extra pixels (in this case 0). 100x1 also fits all pixels, but it sure is much less rectangular than 10x10.

And in order to fit 101 pixels the best size is 8x13, although 8*13 is 104, it's the only multiplication that doesn't lose any pixels, adds few extra pixels (3), and has the most rectangular shape.

So far I have been able to solve this problem with the following rules:

• Dividing width by height must result in a value greater than 0.5 and less than 1.5. (This will ensure that only the most rectangular values ​​are kept).
• Multiplying width by height must result in a value greater than or equal to the number of pixels.

By applying these rules I end up with a variety of possibilities, the best one being the one that, when multiplied, most closely approximates the number of pixels.

Here's what my code looks like currently:

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)

What it does is keep a variable holding the smallest result of (width*height)-pixels, which is the difference between the found values ​​and the number of pixels.

Although it works fine for small amounts of pixels, with huge values (which would likely return 1000x1000 sizes), it's ultra slow.

Is there a specific reason for such slowness? and would it be possible to get the same result without using nested for loops?

CodePudding user response：

The following code can be made more efficient but it is very descriptive. It takes a pixel count (n) and a k value which denotes the best k matches.

Lets try 68M pixels for some resonable aspect ratios.

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