Calculating # or Rows and Columns

Question

I have a # of images that I'm stitching together into a sprite sheet, how can I calculate the number of rows and columns to fit equally in an even rectangle (no blank spaces)?

Some examples:

6 images should become 2 rows, 3 columns

7 images should become 1 row, 7 columns

8 images should become 2 rows, 4 columns

9 images should become 3 rows, 3 columns

10 images should become 2 rows, 5 columns

Hopefully that helps explain it.

Ideas?

This is just simple factorisation, although you'll need some kind of way of determining the best choice of factors when there is more than one option, e.g. 6 could be 2 x 3 or 3 x 2. BTW: s/square/rectangle/ — Paul R, Jun 16 '11 at 19:23
What about 12? Should it be 2x6 or 3x4? You need to specify a way to compare the possible results (when there are more than one) — Andrei, Jun 16 '11 at 19:25
I'd say for 12 it should be 3x4, I'd want the resulting image to be as small as possible width and height wise (to prevent running into image size limits in the framework I'm using). — Amber Mac, Jun 16 '11 at 19:27
@Paul R: I think means the squarest rectangle he can get (that will give the right total, of course). — Jerry Coffin, Jun 16 '11 at 19:27
There was an answer here with steps 1.4 on how to make it work and the code he gave is working great but the answer is gone -- what should I do? — Amber Mac, Jun 16 '11 at 19:45
@Amber: that was posted by @Mannimarco but he has subsequently deleted it - I'm guessing he found a problem with it ?... — Paul R, Jun 16 '11 at 20:16
@Jerry The "squarest rectangle" would be the one with the smallest perimeter I think. — Voo, Jun 16 '11 at 23:33
@Voo: Yes. Looking at it slightly differently, it would be the one with the factors the closest to the square root of the area (equal to it if it was a perfect square, otherwise one smaller and the other larger than the square root). — Jerry Coffin, Jun 16 '11 at 23:40

score 14 · Accepted Answer · answered Jun 16 '11 at 19:48

14

Here's a very fast and easy algorithm (where N is the number of images)

rows = floor(sqrt(N))
while(N % rows != 0)
     rows = rows - 1

And rows will be the number of rows needed. Columns can obviously be found with N / rows.

I hope this helps!

answered Jun 16 '11 at 19:48

smackcrane

1,379
2
10
17

score 0 · Answer 2 · answered Jun 16 '11 at 19:29

Seems like you have to find all factor pairs of the number, then pick the pair the gives you the most 'desirable' row:column ratio.

So for example:

bestRows = 1
bestRatio = ((double) 1) / N;
for (int i : 1 to N) {
  if ((N % i) == 0) {
    r = N % i
    c = N / i
    ratio = ((double) r) / N;
    if (firstIsBetter(ratio, bestRatio)) {
      bestRows = r;
      bestRatio = ratio;
    }
  }
}

score 0 · Answer 3 · answered Jun 16 '11 at 19:29

Well looking at it if the number is prime you want to have 1 row with x columns where x is the prime number. Else if the number is a perfect square the rows would be the square root of the number by the square root of the number (9 == 3x3) . Else factor the remainder.

score 0 · Answer 4 · answered Jun 16 '11 at 19:31

What's your priority? Do you want it to have the difference between height, width to be minimum, or anything like that?

Given the number n of images. You should take every number i from 1 to sqrt(n). If n can be divided by i (n%i ==0), divide and increment an array power[i] each time it divides. If n cannot be divided any more by i (aka n%i != 0) increment i else divide again.

You should get all the divisors and their biggest power in a given number n.

Make combinations of these and you will get the dimensions of your square.

score 0 · Answer 5 · edited May 23 '17 at 12:04

Since it's unlikely you'll have a large number to begin with there are a lot of ways you can proceed in factoring it.

See Best way to find all factors of a given number in C# for some of them.

The simplest is: - Loop from 1 to the square root of the number, call the index "i".

if number mod i is 0, add i and number / i to the list of factors.

This will give you all the integers that divide your number N. The "other" number is, of course, obtained by dividing N by that integer.

Then, you need to pick the best pair according to some rule. You can chose the ones with the smallest difference: if a * b = N, choose the ones with the smallest absolute value of (a-b)

score -1 · Answer 6 · answered Jun 16 '11 at 19:24

-1

Take a look into Integer Factorization

Maybe that is what you need.

answered Jun 16 '11 at 19:24

Vinicius Kamakura

7,665
1
29
43

@discipulus: if you follow the Wikipedia link in @hexa's answer the article contains descriptions of algorithms for factorisation – Paul R Jun 16 '11 at 20:18
@Paul of course, but presumably Amber knows the problem involves factors; this answer is about as useful as a google search. (It wasn't that I don't understand the answer, if that's what you meant. I was explaining why I voted it down.) – smackcrane Jun 16 '11 at 20:28
@discipulus: ah, OK - I thought maybe you'd missed the fact that there was a link in the answer, but you make a fair point – Paul R Jun 16 '11 at 20:34
1

a Google search is only useful if you are searching for the write keywords, maybe he did not know what they keywords were (since he didn't say anything about factorization). – Vinicius Kamakura Jun 16 '11 at 21:04

Calculating # or Rows and Columns

6 Answers6

Linked