0

If I have n number of pixels, what's the best way to get the factor of n that most resembles a square shape when using it as a dimension of an image?

Using n == 512 as an example, its factors are:

1, 2, 4, 8, 16, 32, 64, 128, 256, 512

The values that most resembles a square in this list of factors would be 16 or 32, precisely both. I don't know if this type of "middle" factor has a specific name, but is there a formula to get it, or is this more of a programming problem than a math problem?

And if n is prime, what would be the best way to fit all the pixels while keeping a square-like shape? (no problem if extra pixels need to be added).

Luna
  • 11

1 Answers1

1

After a long discussion in the comments I think we've come to a conclusion that deals with both composite and prime numbers.

Using two images as an example: image A has 100 pixels and image B has 101, what are the best width and height values for image A and the best width and height values for image B?

We can find the answer by following two rules:

  1. Dividing $width$ by $height$ must result in a value greater than $0.5$ and less than $1.5$.
  2. Multiplying $width$ by $height$ must result in a value greater than or equal to the number of pixels.

By following these rules you may get multiple possible combinations, the best one being the one that, when multiplied, most closely approximates the number of pixels. (if you want, you can reduce the number of values ​​by determining that $width * height$ must be equal to or less than the number of pixels multiplied by 2).

In short, it's just a matter of checking all possible combinations of width and height up to the number of pixels, separating those that comply with both rules, and from them getting the smallest possible result of their division, which must be greater than or equal to the number of pixels.

This image shows some of the values ​​that meet both rules for 100 pixels, and as you can see, 10x10 seems to be the best choice between them because it's the multiplication that adds the least extra pixels ($0$) when subtracted from the original number of pixels ($(10*10)-100$).

And this image also shows some of the values ​​that meet both rules, but this time for 101 pixels, and it tells us that 8x13 is the best choice (with the addition of 3 extra pixels).

So we come to the conclusion that the squaredest size for image A that adds the least amount of pixels (or none at all) is 10x10, and for image B it is 8x13.

Below I'll leave a dirty JavaScript that implements these rules, if you're interested in testing them:

function loopPixels(pixels, callback) {
    for (let x = 2; x < pixels; x++) {
        for (let y = 2; y < pixels; y++) {
            callback(x, y);
        }
    }
}

let pixels = 100;
let diff = pixels;
loopPixels(pixels, (left, right) => {
    if ((Math.round(left/right) == 1) && (leftright >= pixels) && (leftright < pixels2)) {
        if ((leftright)-pixels < diff) {
            diff = (leftright)-pixels;
            console.log(`w: ${left}, h: ${right}, (${left}${right})-${pixels} = ${diff}`);
        }
    }
})
Luna
  • 11